Я играл с хеш-функцией 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 может принимать отрицательные значения.
источник
n+1 == 2**61-1
n
для всего 64-битного диапазона int.2147483647
равноsys.maxint
(неsys.maxint+1
), и если 'n = 0b111111111111111111111111111111111111111111111111111111111', то нетn+1 == 2**61
илиn == 2**61-1
(нетn+1 == 2**61-1
)?Ответы:
На основе документации python в
pyhash.c
файле:Итак, для 64- или 32-битной машины уменьшение будет 2 _PyHASH_BITS - 1, но что
_PyHASH_BITS
?Вы можете найти его в
pyhash.h
файле заголовка, который для 64-битной машины был определен как 61 (вы можете прочитать больше объяснений вpyconfig.h
файле).Итак, во-первых, он основан на вашей платформе, например, на моей 64-битной платформе Linux сокращение составляет 2 61 -1, что составляет
2305843009213693951
:Также вы можете использовать
math.frexp
для получения мантиссы и экспоненты,sys.maxint
которые для 64-битной машины показывают, что max int составляет 2 63 :И вы можете увидеть разницу простым тестом:
Прочтите полную документацию об алгоритме хеширования python https://github.com/python/cpython/blob/master/Python/pyhash.c#L34
Как упоминалось в комментарии, вы можете использовать
sys.hash_info
(в python 3.X), который даст вам структурную последовательность параметров, используемых для вычисления хэшей.Наряду с модулем, который я описал в предыдущих строках, вы также можете получить
inf
следующее значение:источник
sys.hash_info
для полноты картины.2305843009213693951
есть2^61 - 1
. Это самое большое простое число Мерсенна, которое умещается в 64 бита.Если вам нужно создать хэш, просто взяв значение по модулю некоторого числа, то хорошее простое число Мерсенна - хороший выбор - его легко вычислить и обеспечить равномерное распределение возможностей. (Хотя лично я бы никогда таким образом не сделал хеш)
Особенно удобно вычислять модуль для чисел с плавающей запятой. У них есть экспоненциальная составляющая, которая умножает целое число на
2^x
. Поскольку2^61 = 1 mod 2^61-1
вам нужно учитывать только расширение(exponent) mod 61
.См .: https://en.wikipedia.org/wiki/Mersenne_prime
источник
x == y
гарантии дляhash(x) == hash(y)
разных типов? (Такие числаDecimal('1e99999999')
особенно проблематичны, например: вы не хотите расширять их до соответствующего целого числа перед хешированием.)int
,float
,Decimal
иFraction
объекты , и чтоx == y
подразумевает ,hash(x) == hash(y)
даже еслиx
иy
имеют различные типы накладывает довольно жесткие ограничения. Если бы это был просто вопрос написания хеш-функции для целых чисел, не беспокоясь о других типах, это было бы совсем другое дело.Хеш-функция возвращает простой int, что означает, что возвращаемое значение больше
-sys.maxint
или меньшеsys.maxint
, что означает, что если вы передадитеsys.maxint + x
ей результат, будет-sys.maxint + (x - 2)
.Между тем,
2**200
это вn
раз больше, чемsys.maxint
- я предполагаю, что хеш будет выходить за диапазон-sys.maxint..+sys.maxint
n раз, пока не остановится на простом целом числе в этом диапазоне, как в фрагментах кода выше ..Итак, как правило, для любого n <= sys.maxint :
Примечание: это верно для python 2.
источник
sys.maxint
и который использует другую хеш-функцию).Реализацию для типа INT в CPython можно найти здесь.
Он просто возвращает значение, за исключением того
-1
, что возвращает-2
:источник
PyLong
а неPyInt
.