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

100

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

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

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

Я пробовал использовать двоичный поиск, чтобы найти наименьшее число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

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

Я также поиграл, [hash(random.random()) for i in range(10**6)]чтобы оценить диапазон хэш-функции. Максимальное значение постоянно ниже n выше. Сравнивая min, кажется, что хеш Python 3 всегда положительно оценивается, тогда как хеш Python 2 может принимать отрицательные значения.

Полковник Паник
источник
9
Вы проверили двоичное представление числа?
John Dvorak
3
«0b111111111111111111111111111111111111111111111111111111111» любопытно! Итак n+1 == 2**61-1
Colonel Panic
2
кажется, зависит от системы. В моем питоне хеш предназначен nдля всего 64-битного диапазона int.
Дэниел
1
Обратите внимание на заявленную цель хеш-значения: они используются для быстрого сравнения ключей словаря во время поиска в словаре. Другими словами, определенные реализацией и в силу того, что они короче многих значений, которые могут иметь хэш-значения, вполне могут иметь коллизии даже в разумных пространствах ввода.
пользователь
2
Гм, не 2147483647равно sys.maxint(не sys.maxint+1), и если 'n = 0b111111111111111111111111111111111111111111111111111111111', то нет n+1 == 2**61или n == 2**61-1(нет n+1 == 2**61-1)?
phoog 03

Ответы:

73

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

Для числовых типов хеш числа x основан на уменьшении числа 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 61 -1, что составляет 2305843009213693951:

>>> 2**61 - 1
2305843009213693951

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

>>> 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
Касравнд
источник
3
Было бы неплохо упомянуть sys.hash_infoдля полноты картины.
Марк Дикинсон,
78

2305843009213693951есть 2^61 - 1. Это самое большое простое число Мерсенна, которое умещается в 64 бита.

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

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

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

Мэтт Тиммерманс
источник
8
Вы говорите, что никогда не сделаете хеш таким образом. Есть ли у вас альтернативные предложения о том, как это можно сделать таким образом, чтобы было достаточно эффективно вычислять целые числа, числа с плавающей запятой, десятичные дроби, дроби и гарантировать x == yгарантии для hash(x) == hash(y)разных типов? (Такие числа Decimal('1e99999999')особенно проблематичны, например: вы не хотите расширять их до соответствующего целого числа перед хешированием.)
Марк Дикинсон
@MarkDickinson Я подозреваю, что он пытается провести различие между этим простым молниеносным быстрым хешем и криптографическими хешами, которые также заботятся о том, чтобы вывод выглядел случайным.
Mike Ounsworth 03
4
@MarkDickinson Модуль - хорошее начало, но потом я бы еще немного его смешал, особенно смешивая некоторые высокие биты с низкими. Нередко можно увидеть последовательности целых чисел, делящихся на степень 2. Также нередко можно увидеть хеш-таблицы с емкостью, равной степени 2. В Java, например, если у вас есть последовательность целых чисел, которые делятся на 16, и вы используете их в качестве ключей в HashMap, вы будете использовать только 1/16 часть ведер (по крайней мере, в той версии источника, которую я просматриваю)! Я думаю, что хэши должны быть хотя бы немного случайными, чтобы избежать этих проблем
Мэтт Тиммерманс,
Да, хэши в стиле битового микширования намного превосходят те, которые основаны на математике. Инструкции по битовому микшированию настолько дешевы, что вы можете получить их по той же цене. Кроме того, в реальных данных, похоже, нет шаблонов, которые не работают при битовом смешивании. Но есть паттерны, которые ужасны для модуля.
usr
9
@usr: Конечно, но немного смешивания хэш неосуществимо здесь: требование о том , что хэш для работы int, float, Decimalи Fractionобъекты , и что x == yподразумевает , hash(x) == hash(y)даже если xи yимеют различные типы накладывает довольно жесткие ограничения. Если бы это был просто вопрос написания хеш-функции для целых чисел, не беспокоясь о других типах, это было бы совсем другое дело.
Марк Дикинсон
9

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

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

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

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

Андрей Иванейко
источник
8
Это может быть верно для Python 2, но определенно не для Python 3 (которого нет sys.maxintи который использует другую хеш-функцию).
Interjay 03
0

Реализацию для типа INT в CPython можно найти здесь.

Он просто возвращает значение, за исключением того -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;
}
Jieter
источник
6
Это не включает в себя большие значения, которые реализуются путем , PyLongа не PyInt.
Interjay 03