Fonction Python hash() intégrée

Question

Windows XP, Python 2.5 :

hash('http://stackoverflow.com') Result: 1934711907

Google App Engine ( http://shell.appspot.com/ ) :

hash('http://stackoverflow.com') Result: -5768830964305142685

Comment cela se fait-il ? Comment puis-je avoir une fonction de hachage qui me donnera les mêmes résultats sur différentes plateformes (Windows, Linux, Mac) ?

Answer 1

A priori, AppEngine utilise une implémentation 64 bits de Python (-5768830964305142685 ne rentre pas dans 32 bits) et votre implémentation de Python est 32 bits. Vous ne pouvez pas compter sur le fait que les hachages d'objets soient significativement comparables entre différentes implémentations.

Answer 2

Il s'agit de la fonction de hachage que Google utilise en production pour python 2.5 :

def c_mul(a, b):
  return eval(hex((long(a) * b) & (2**64 - 1))[:-1])

def py25hash(self):
  if not self:
    return 0 # empty
  value = ord(self[0]) << 7
  for char in self:
    value = c_mul(1000003, value) ^ ord(char)
  value = value ^ len(self)
  if value == -1:
    value = -2
  if value >= 2**63:
    value -= 2**64
  return value

Answer 3

Qu'en est-il du bit de signe ?

Par exemple :

Valeur hexagonale 0xADFE74A5 représente une valeur non signée 2919134373 et signé -1375832923 . La valeur correcte doit être signée (bit de signe = 1) mais Python la convertit en non signée et nous avons une valeur de hachage incorrecte après la conversion de 64 à 32 bits.

Attention à l'utilisation :

def hash32(value):
    return hash(value) & 0xffffffff

Answer 4

Hachage polynomial pour les chaînes de caractères. 1000000009 y 239 sont des nombres premiers arbitraires. Il est peu probable qu'il y ait des collisions par accident. L'arithmétique modulaire n'est pas très rapide, mais pour éviter les collisions, elle est plus fiable que le calcul modulo une puissance de 2 . Bien sûr, il est facile de trouver une collision intentionnelle.

mod=1000000009
def hash(s):
    result=0
    for c in s:
        result = (result * 239 + ord(c)) % mod
    return result % mod

Answer 5

La valeur de PYTHONHASHSEED peut être utilisé pour initialiser les valeurs de hachage.

Essayez :

PYTHONHASHSEED python -c 'print(hash('http://stackoverflow.com'))'