Python中的hash(n)== n是什么时候？

Question

我一直在玩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的散列可以取负值.

Answer 1

2305843009213693951是2^61 - 1.它是最大的Mersenne素数,适合64位.

如果你只需要通过取值mod来制作一个哈希值,那么一个大的梅森素数是一个不错的选择 - 它很容易计算并确保均匀分布的可能性.(虽然我个人不会这样做哈希)

计算浮点数的模数特别方便.它们具有指数成分,将整数乘以2^x.既然如此2^61 = 1 mod 2^61-1,你只需要考虑(exponent) mod 61.

请参阅:https://en.wikipedia.org/wiki/Mersenne_prime

Answer 2

基于文件中的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 ⁶¹ -1,即2305843009213693951:

>>> 2**61 - 1
2305843009213693951

你也可以使用math.frexp它来获得sys.maxint64位机器的尾数和指数,表明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

Answer 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.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来说是正确的.