set_title Quand est-ce que hash(n)== n est en Python?




seaborn title (4)

Basé sur la documentation de 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 premier P = 2**_PyHASH_BITS - 1 . Il est conçu pour que hash(x) == hash(y) quand x et y sont numériquement égaux, même si x et y ont des types différents.

Donc, pour une machine 64/32 bit, la réduction serait 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 a été défini pour 61 pour une machine 64 bits (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, il est basé sur votre plate-forme, par exemple dans ma plate-forme Linux 64 bits, la réduction est de 2 61 -1, ce qui est 2305843009213693951 :

>>> 2**61 - 1
2305843009213693951

Vous pouvez également utiliser math.frexp pour obtenir la mantisse et l'exposant de sys.maxint qui, pour une machine 64 bits, montre que max int est 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 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)
>>> 

À côté du module que j'ai décrit dans les lignes précédentes, vous pouvez également obtenir la valeur d' inf suivante:

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

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

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

Je ne suis pas surpris, je comprends que hash prend une gamme de valeurs finie. 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 note que c'est moins que sys.maxsize == 9223372036854775807

Edit: J'utilise Python 3. J'ai exécuté la même recherche binaire sur Python 2 et j'ai obtenu un résultat différent 2147483648, que je note 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 hash de Python 3 soit toujours évalué positivement, alors que le hash de Python 2 peut prendre des valeurs négatives.


2305843009213693951 est 2^61 - 1 . C'est le plus gros Prime Mersenne qui s'adapte à 64 bits.

Si vous devez faire un hachage juste en prenant la valeur mod un certain nombre, alors un grand Mersenne prime est un bon choix - il est facile à calculer et assure une répartition égale des possibilités. (Bien que personnellement je ne ferais jamais un hachage 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


La fonction de hachage renvoie plain plain, ce qui signifie que la valeur renvoyée est supérieure à -sys.maxint et inférieure à sys.maxint , ce qui signifie que si vous transmettez sys.maxint + x à ce résultat, cela sera -sys.maxint + (x - 2) .

hash(sys.maxint + 1) == sys.maxint + 1 # False
hash(sys.maxint + 1) == - sys.maxint -1 # True
hash(sys.maxint + sys.maxint) == -sys.maxint + sys.maxint - 2 # True

Pendant ce temps 2**200 est un n fois plus grand que sys.maxint - je suppose que ce hash irait sur la plage -sys.maxint..+sys.maxint n fois jusqu'à ce qu'il s'arrête sur un entier simple dans cette plage, comme dans les extraits de code au dessus..

Donc généralement, pour tout n <= sys.maxint :

hash(sys.maxint*n) == -sys.maxint*(n%2) +  2*(n%2)*sys.maxint - n/2 - (n + 1)%2 ## True

Note: ceci est vrai pour python 2.






python-internals