在Python中对整数进行哈希。

Question

我了解到不可变对象的哈希值是该对象的整数表示形式，在进程生命周期内是唯一的。

整数对象的哈希值与该整数所包含的值相同。例如，

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

但是，当整数变得足够大时，在某个阈值之后上述原则就会被打破。它的值似乎在某个限制范围内滚动。

>>> 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

- Saad

---

@chepner，不同的对象应该有不同的哈希值，为什么其他int对象具有相同的哈希值？ - sahasrara62

除了“阅读文档”之外，我不知道该说什么...... - Kelly Bundy

因为所有可能的对象都没有足够的哈希值。 - chepner

根据文档，@sahasrara62：__hash __()方法应返回一个整数。唯一必需的属性是比较相等的对象具有相同的哈希值。 - buran

一旦Python切换到无限哈希表的dict实现，Hilbert的解决方案将会很有用。 - chepner

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

完整的规则集，请参考文档。

（该文档与数字类型哈希有关。）

- norok2

---

只有模数是实现细节。 - Kelly Bundy