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

Ответ 1

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

Для числовых типов хэш числа x основан на сокращении    х по модулю простого 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-битной машины показывают, что max int равно 2 ⁶³:

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

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

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

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

Как уже упоминалось в комментарии, вы можете использовать sys.hash_info (в python 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

Ответ 2

2305843009213693951 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

Ответ 3

Функция хеширования возвращает plain 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 n раз, пока он не остановится на простое целое в этом диапазоне, например, в фрагментах кода выше..

Как правило, для любого n <= sys.maxint:

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

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

Ответ 4

Реализация для типа int в cpython находится здесь.

Он просто возвращает значение, за исключением -1, чем возвращает -2:

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