python - python中整数的哈希

Question

我知道不可变对象(immutable对象)的哈希值是该对象的整数表示形式，它在进程的生命周期内是唯一的。

整数对象的哈希值与整数所持有的值相同。例如，

>>> int(1000).__hash__()
1000

但是当整数增长到足够大时，上述原则似乎会在某个阈值后失效。它的值(value)似乎在某种程度上受到限制。

>>> int(10000000000000000).__hash__()
10000000000000000
>>> int(100000000000000000).__hash__()
100000000000000000
>>> int(1000000000000000000).__hash__()
1000000000000000000
>>> int(10000000000000000000).__hash__()
776627963145224196

两个问题:

1. 限制是多少？哈希表覆盖的整数空间是多少？
2. 如何计算超过上述限制的整数的哈希值？

系统信息:

Linux lap-0179 5.13.0-44-generic #49~20.04.1-Ubuntu SMP Wed May 18 18:44:28 UTC 2022 x86_64 x86_64 x86_64 GNU/Linux

Python 解释器:

Python 3.8.10 (default, Mar 15 2022, 12:22:08) 
[GCC 9.4.0] on linux

Answer 1

虽然这取决于机器和实现，但对于 64 位机器上的 CPython，非负整数 n 的 hash() 计算为 n % k 与 k = (2 ** 61 - 1) (= 2305843009213693951) 因此值在 0 和 之间>k - 1 保持原样。

这里有经验证明:

k = 2 ** 61 - 1
for i in range(k - 2, k + 2):
    print(i, hash(i), i % k)
# 2305843009213693949 2305843009213693949
# 2305843009213693950 2305843009213693950
# 2305843009213693951 0
# 2305843009213693952 1

有关完整的规则集，请参阅 documentation .