Kiedy hash (n) == n w Pythonie?

Bawiłem się funkcją skrótu Pythona . W przypadku małych liczb całkowitych pojawia się hash(n) == nzawsze. Jednak nie dotyczy to dużych liczb:

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

Nie dziwię się, rozumiem, że hash przyjmuje skończony zakres wartości. Co to za zasięg?

Próbowałem użyć wyszukiwania binarnego, aby znaleźć najmniejszą liczbę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

Co jest specjalnego w 2305843009213693951? Zauważam, że to mniej niżsys.maxsize == 9223372036854775807

Edycja: używam Pythona 3. Przeprowadziłem to samo wyszukiwanie binarne w Pythonie 2 i otrzymałem inny wynik 2147483648, który, jak zauważam, to sys.maxint+1

Bawiłem się też, [hash(random.random()) for i in range(10**6)]aby oszacować zakres funkcji skrótu. Maksimum jest konsekwentnie poniżej n powyżej. Porównując min, wydaje się, że hash Pythona 3 jest zawsze pozytywnie oceniany, podczas gdy hash Pythona 2 może przyjmować wartości ujemne.

Na podstawie dokumentacji Pythona w pyhash.cpliku:

W przypadku typów liczbowych skrót liczby x jest oparty na redukcji x modulo liczby pierwszej P = 2**_PyHASH_BITS - 1. Został zaprojektowany w taki sposób, że hash(x) == hash(y)ilekroć x i y są liczbowo równe, nawet jeśli x i y mają różne typy.

Zatem dla maszyny 64/32 bitowej redukcja wyniosłaby 2 ^_PyHASH_BITS - 1, ale co to jest _PyHASH_BITS?

Możesz go znaleźć w pyhash.hpliku nagłówkowym, który dla maszyny 64-bitowej został zdefiniowany jako 61 (więcej informacji znajdziesz w pyconfig.hpliku).

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

Więc po pierwsze wszystko jest oparty na platformie, na przykład w moim 64-bitowej platformie Linux redukcja jest 2 ⁶¹ -1, który jest 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

Możesz również użyć math.frexp, aby uzyskać mantysę i wykładnik, sys.maxintktórego dla maszyny 64-bitowej pokazuje, że max int to 2 ⁶³ :

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

Różnicę widać po prostym teście:

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

Przeczytaj pełną dokumentację na temat algorytmu haszującego Pythona https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Jak wspomniano w komentarzu, możesz użyć sys.hash_info(w pythonie 3.X), co da ci struct sekwencję parametrów używanych do obliczania skrótów.

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

Oprócz modułu, który opisałem w poprzednich wierszach, można również uzyskać następującą infwartość:

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

2305843009213693951jest 2^61 - 1. To największa liczba pierwsza Mersenne'a, która mieści się w 64 bitach.

Jeśli musisz utworzyć hash, po prostu pobierając wartość mod pewnej liczby, to duża liczba pierwsza Mersenne'a jest dobrym wyborem - jest łatwa do obliczenia i zapewnia równomierny rozkład możliwości. (Chociaż osobiście nigdy nie zrobiłbym haszyszu w ten sposób)

Szczególnie wygodne jest obliczanie modułu dla liczb zmiennoprzecinkowych. Mają składnik wykładniczy, który mnoży liczbę całkowitą przez 2^x. Ponieważ 2^61 = 1 mod 2^61-1wystarczy wziąć pod uwagę tylko (exponent) mod 61.

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

Funkcja skrótu zwraca zwykły int, co oznacza, że ​​zwracana wartość jest większa -sys.maxinti mniejsza niż sys.maxint, co oznacza, że ​​jeśli sys.maxint + xdo niej przejdziesz , wynik będzie -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

Tymczasem 2**200jest nrazy większa niż sys.maxint- przypuszczam, że hash przejdzie przez zakres -sys.maxint..+sys.maxintn razy, aż zatrzyma się na zwykłej liczbie całkowitej w tym zakresie, jak we fragmentach kodu powyżej.

Generalnie dla każdego n <= sys.maxint :

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

Uwaga: dotyczy to Pythona 2.

Realizacja dla typu int w CPython można znaleźć tutaj.

Po prostu zwraca wartość, z wyjątkiem -1, niż zwraca -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;
}