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

问题:

我一直在玩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
编辑:我使用Python 3.我在Python 2上运行相同的二进制搜索,得到不同的结果2147483648,我注意到sys.maxint+1
我也玩[hash(random.random()) for i in range(10**6)]来估计散列函数的范围。最大值始终低于n以上。比较最小,似乎Python 3的散列总是积极的价值,而Python 2的散列可以取负值。

回答:

基于pyhash.c文件中的python文档:

对于数字类型,数字x的散列基于素数P = 2**_PyHASH_BITS - 1的x模的减少。它的设计使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

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: When is hash(n) == n in Python?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

+ 55 = 61