Quand est hash (n) == n en Python?

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

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

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

J'ai essayé d'utiliser la recherche binaire pour trouver le plus petit nombrehash(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é du 2305843009213693951? Je note que c'est moins quesys.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 également joué avec [hash(random.random()) for i in range(10**6)]pour estimer la plage de fonction de hachage. Le max est systématiquement inférieur à n ci-dessus. En comparant le min, il semble que le hachage de Python 3 a toujours une valeur positive, alors que le hachage de Python 2 peut prendre des valeurs négatives.

Basé sur la documentation python dans le pyhash.cfichier:

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)chaque fois que 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 c'est _PyHASH_BITS?

Vous pouvez le trouver dans le pyhash.hfichier d' en- tête qui pour une machine 64 bits a été défini comme 61 (vous pouvez lire plus d'explications dans le pyconfig.hfichier).

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

Donc, tout d'abord, c'est basé sur votre plate-forme par exemple dans ma plate-forme Linux 64 bits, la réduction est de 2 ⁶¹ -1, ce qui est 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

Vous pouvez également utiliser math.frexppour obtenir la mantisse et l'exposant sys.maxintdont pour une machine 64 bits montre que max int est 2 ⁶³ :

>>> 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 struct de paramètres utilisés pour le calcul des 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 infvaleur comme suit:

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

2305843009213693951est 2^61 - 1. C'est le plus grand Mersenne prime qui tient sur 64 bits.

Si vous devez faire un hachage simplement en prenant la valeur mod un certain nombre, alors un grand Mersenne prime est un bon choix - il est facile à calculer et assure une distribution uniforme des possibilités. (Bien que personnellement je ne ferais jamais de hasch 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. Depuis 2^61 = 1 mod 2^61-1, il vous suffit de considérer le (exponent) mod 61.

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

La fonction de hachage renvoie un entier simple, ce qui signifie que la valeur renvoyée est supérieure à-sys.maxint et inférieure à sys.maxint, ce qui signifie que si vous lui passez sys.maxint + xle résultat, ce serait -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

En attendant, 2**200c'est un nfois plus grand que sys.maxint- je suppose que le hachage dépasserait la plage -sys.maxint..+sys.maxintn fois jusqu'à ce qu'il s'arrête sur un entier brut dans cette plage, comme dans les extraits de code ci-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

Remarque: cela est vrai pour python 2.

L' implémentation du type int dans cpython peut être trouvée ici.

Il renvoie simplement la valeur, sauf pour -1, puis renvoie -2:

static long
int_hash(PyIntObject *v)
{
    /* XXX If this is changed, you also need to change the way
       Python's long, float and complex types are hashed. */
    long x = v -> ob_ival;
    if (x == -1)
        x = -2;
    return x;
}