Quand hash (n) == n en Python?

Question

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

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

Je ne suis pas surpris, je comprends de hachage prend une gamme finie de valeurs. Quelle en est la portée?

J'ai essayé d'utiliser les binaires de recherche pour trouver le plus petit nombre 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

Ce qui est spécial au sujet de 2305843009213693951? Je remarque, c'est moins de sys.maxsize == 9223372036854775807

Edit: je suis à l'aide de Python 3. J'ai couru le même binaire de recherche sur le langage Python 2 et j'ai 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)] à estimer la portée de la fonction de hachage. Le max est constamment au-dessous de n au-dessus. La comparaison de la min, il semble Python 3 de hachage est toujours évaluée positivement, alors que Python 2 hachage peut prendre des valeurs négatives.

Answer 1

2305843009213693951 est 2^61 - 1. C'est le plus grand nombre de Mersenne premier qui s'adapte en 64 bits.

Si vous devez faire un hash juste en prenant la valeur mod certain nombre, puis un grand nombre de Mersenne premier est un bon choix, c'est facile à calculer et assure une répartition uniforme de possibilités. (Même si personnellement je ne fais jamais de hachage de cette façon)

C'est particulièrement pratique pour calculer le module des nombres à virgule flottante. Ils ont une exponentielle composant qui multiplie l'ensemble nombre en 2^x. Depuis 2^61 = 1 mod 2^61-1, vous avez seulement besoin de considérer l' (exponent) mod 61.

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

Answer 2

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

Pour les types numériques, le hash d'un nombre x est basée sur la réduction des de x modulo, le premier P = 2**_PyHASH_BITS - 1. Il est conçu de sorte 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 un 64/32 bits de la machine, la réduction sera de 2 ^_PyHASH_BITS - 1, mais qu'est - _PyHASH_BITS?

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

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

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

>>> 2**61 - 1
2305843009213693951

Aussi, Vous pouvez utiliser math.frexp afin d'obtenir la mantisse et l'exposant de sys.maxint , pour une machine 64 bit montre que max int est de 2⁶³:

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

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

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

Lire l'intégralité de la documentation à propos de python algorithme de hachage 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 séquence de paramètres utilisés pour le calcul de la les tables de hachage.

>>> 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)
>>> 

Parallèlement, le module que j'ai décrit dans les lignes précédentes, vous pouvez également obtenir de l' inf de la valeur comme suit:

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

Answer 3

Fonction de hachage retourne plaine int qui signifie que la valeur de retour est supérieure à -sys.maxint et inférieur sys.maxint, ce qui signifie que si vous passez sys.maxint + x à il en résulterait -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**200 est n fois plus grande que l' sys.maxint - ma conjecture est que de hachage irait plus -sys.maxint..+sys.maxint n fois jusqu'à ce qu'il s'arrête sur un nombre entier dans la plage, comme dans les extraits de code ci-dessus..

Donc, généralement, pour tout n <= sys.exemple 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.

Answer 4

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

Il renvoie simplement la valeur, à l'exception de -1 , qu'il 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;
}