set_title - Quand hash(n)== n en Python?




seaborn title (3)

J'ai joué avec la fonction de hachage de Python. Pour les petits entiers, il apparaît hash(n) == n toujours. Cependant, cela ne concerne pas les grands nombres:

>>> hash(2**100) == 2**100
False

Je ne suis pas surpris, je comprends que le hash prend une gamme finie de valeurs. Quelle est cette gamme?

J'ai essayé d'utiliser la recherche binaire pour trouver le plus petit nombre de hash(n) != n

>>> import codejamhelpers # pip install codejamhelpers
>>> help(codejamhelpers.binary_search)
Help on function binary_search in module codejamhelpers.binary_search:

binary_search(f, t)
    Given an increasing function :math:`f`, find the greatest non-negative integer :math:`n` such that :math:`f(n) \le t`. If :math:`f(n) > t` for all :math:`n \ge 0`, return None.

>>> f = lambda n: int(hash(n) != n)
>>> n = codejamhelpers.binary_search(f, 0)
>>> hash(n)
2305843009213693950
>>> hash(n+1)
0

Quelle est la particularité de 2305843009213693951? Je remarque que c'est moins que sys.maxsize == 9223372036854775807

Edit: J'utilise Python 3. J'ai effectué la même recherche binaire sur Python 2 et obtenu un résultat différent, 2147483648, que je remarque est sys.maxint+1

J'ai aussi joué avec [hash(random.random()) for i in range(10**6)] pour estimer la plage de la fonction de hachage. Le maximum est toujours inférieur à n ci-dessus. En comparant le min, il semble que le hachage de Python 3 soit toujours valorisé, alors que celui de Python 2 peut prendre des valeurs négatives.


Basé sur la documentation python dans le fichier pyhash.c :

Pour les types numériques, le hachage d'un nombre x est basé sur la réduction de x modulo le nombre premier P = 2**_PyHASH_BITS - 1 . Il est conçu pour que hash(x) == hash(y) lorsque x et y sont numériquement égaux, même si x et y ont des types différents.

Donc, pour une machine 64/32 bits, la réduction serait de 2 _PyHASH_BITS - 1, mais qu’est-ce que _PyHASH_BITS ?

Vous pouvez le trouver dans le fichier d'en-tête pyhash.h qui, pour un ordinateur 64 bits, a été défini sur 61 (vous pouvez lire plus d'explications dans le fichier pyconfig.h ).

#if SIZEOF_VOID_P >= 8
#  define _PyHASH_BITS 61
#else
#  define _PyHASH_BITS 31
#endif

Donc tout d’abord, cela 2305843009213693951 votre plate-forme. Par exemple, dans ma plate-forme Linux 64 bits, la réduction est de 2 61 -1, ce qui correspond à 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

Vous pouvez aussi utiliser math.frexp pour obtenir la mantisse et l'exposant de sys.maxint qui, pour une machine 64 bits, indique que max int est math.frexp à 2 63 :

>>> import math
>>> math.frexp(sys.maxint)
(0.5, 64)

Et vous pouvez voir la différence par un simple test:

>>> hash(2**62) == 2**62
True
>>> hash(2**63) == 2**63
False

Lisez la documentation complète sur l'algorithme de hachage python https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Comme mentionné dans le commentaire, vous pouvez utiliser sys.hash_info (en python 3.X) qui vous donnera une séquence de structure de paramètres utilisés pour calculer les hachages.

>>> sys.hash_info
sys.hash_info(width=64, modulus=2305843009213693951, inf=314159, nan=0, imag=1000003, algorithm='siphash24', hash_bits=64, seed_bits=128, cutoff=0)
>>> 

En plus du module que j'ai décrit dans les lignes précédentes, vous pouvez également obtenir la valeur inf comme suit:

>>> hash(float('inf'))
314159
>>> sys.hash_info.inf
314159


2305843009213693951 est 2305843009213693951 2^61 - 1 . C'est le plus gros prime de Mersenne qui s'intègre dans 64 bits.

Si vous devez faire un hachage simplement en prenant la valeur mod un nombre, un grand nombre premier de Mersenne est un bon choix - il est facile à calculer et garantit une répartition uniforme des possibilités. (Bien que personnellement je ne ferais jamais un hash de cette façon)

Il est particulièrement pratique de calculer le module pour les nombres à virgule flottante. Ils ont une composante exponentielle qui multiplie le nombre entier par 2^x . Puisque 2^61 = 1 mod 2^61-1 , il suffit de considérer le (exponent) mod 61 .

Voir: https://en.wikipedia.org/wiki/Mersenne_prime





python-internals