Когда hash (n) == n в Python?

Question

Я играл с Python hash function. Для маленьких целых чисел всегда отображается hash(n) == n. Однако это не распространяется на большие числа:

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

Я не удивлен, я понимаю, что хэш принимает конечный диапазон значений. Что это за диапазон?

Я попытался с помощью binary search найти наименьшее число 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 

Что особенного 2305843009213693951? Отмечу, что это меньше, чем sys.maxsize == 9223372036854775807

Edit: Я использую Python 3. Я запускал тот же самый бинарный поиск на Python 2 и получил другой результат 2147483648, который я отмечаю это sys.maxint+1

Я также играл с в оценить диапазон хэш-функции. Максимум последовательно ниже n выше. Сравнивая min, кажется, что хеш Python 3 всегда положительно оценивается, тогда как хэш Python 2 может принимать отрицательные значения.

Answer 1

основы питона документации в pyhash.c файле:

Для числовых типов, хэш числа й на основе сокращения из й по модулю простого P = 2**_PyHASH_BITS - 1. Он сконструирован так, что hash(x) == hash(y) всякий раз, когда x и y численно равны, даже если x и y имеют разные типы.

Так что для 64/32 битной машины, сокращение будет 2 ^_PyHASH_BITS - 1, но что _PyHASH_BITS?

Вы можете найти его в файле заголовка pyhash.h, который для 64-битной машины был определен как 61 (вы можете прочитать больше объяснений в файле pyconfig.h).

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

Так первый от всего она основана на вашей платформе, например, в моей 64-битной платформе Linux редукция 2 -1, который 2305843009213693951:

>>> 2**61 - 1 
2305843009213693951 

Также Вы можете использовать math.frexp в для получения мантиссы и показателя sys.maxint, который для 64-битной машины показывает, что максимальное значение int равно 2 :

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

И вы можете увидеть разницу с помощью простого теста:

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

Читайте полную документацию по алгоритму хеширования питон https://github.com/python/cpython/blob/master/Python/pyhash.c#L34

Как уже упоминалось в комментариях вы можете использовать sys.hash_info (в питона 3.X) который даст вам структурную последовательность параметров, используемых для вычисления хэшей .

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

Наряду с модулем, который я описал в предыдущих строк, вы можете также получить значение inf как следующее:

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

Answer 2

implementation for the int type in cpython can be found here.

Он просто возвращает значение, за -1 исключением, чем он возвращается -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; 
} 

Answer 3

Функция хеширования возвращает простой Int это означает, что возвращаемое значение больше, чем -sys.maxint и ниже чем sys.maxint, что означает, что если вы пройдете sys.maxint + x, то результатом будет -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 

Между тем 2**200 является n раз больше, чем sys.maxint - я думаю, что хэш-бы перейти на диапазон -sys.maxint..+sys.maxint п раз, пока он не остановится на простом целое число в этом диапазоне, как в фрагментах кода выше ..

Так в общем, для любого п < = sys.maxint:

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

Примечание: это справедливо для python 2.

Answer 4

2305843009213693951 is 2^61 - 1. Это самое большое Mersenne prime, которое вписывается в 64 бит.

Если вам нужно сделать хеш, просто взяв значение mod какое-то число, то большой выбор Mersenne - это хороший выбор - его легко вычислить и обеспечить равномерное распределение возможностей. (Хотя я лично никогда не делал бы хэши таким образом)

Особенно удобно вычислять модуль для чисел с плавающей запятой. Они имеют экспоненциальную составляющую, которая умножает целое число на 2^x. С 2^61 = 1 mod 2^61-1 вам нужно только рассмотреть (exponent) mod 61.

См: https://en.wikipedia.org/wiki/Mersenne_prime