python如何计算元组的哈希值

Question

在python中,如果我有一个包含许多元素的元组,它的哈希值是根据元素的元素id还是元素的内容计算的？

在这个例子中,

a = (1, [1,2])
hash(a)

它错误地说列表是不可用的.所以我猜它不是由id计算的,或者可能是检查元素是否可变.

现在看这个例子

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

事实证明,散列ta不随其元素的修改而改变,即a0.那么也许a0用于哈希计算的id？被a0莫名其妙地认为是不可变的？python如何知道类型是否可变？

现在考虑这个案例

b = (1, 2)
id(b)  # 3980742764
c = (1, 2)
id(c)  # 3980732588
tb = (1, b)
tc = (1, c) 
hash(tb)  # -1383040070
hash(tc)  # -1383040070

似乎哈希计算的内容b和c用于哈希计算.

我该如何理解这些例子？

Answer 1

都不是.它是根据这些元素的散列计算的,而不是内容(值).

在python的文档词汇表中查看这一段.

某些东西是否可以清洗,以及它是如何散列的,取决于其.__hash__()方法的实现.Python本身并不知道对象的可变性.

在你的第一个例子中,tuple恰好基于其元素散列自身,而a list根本没有散列 - 该.__hash__()方法没有为它实现(并且有充分的理由).这就是为什么tuple有list它内部的对象不是哈希的.

现在,考虑到这一点,让我们看看python数据模型文档,以及它对该主题的看法:

用户定义的类默认具有__eq__()和__hash__()方法; 与它们相比,所有对象都比较不相等(除了它们自己)并x.__hash__()返回一个适当的值,这x == y意味着它x is y和hash(x) == hash(y).

这就是为什么你不必.__hash__()为你的类定义- 在这种情况下python为你做的.默认实现不会考虑实例字段.这就是为什么您可以在不更改其哈希值的情况下更改对象内部的值.

在这方面你是对的 - 自定义类的哈希函数的默认(CPython)实现依赖于id()一个对象,而不是它内部的值.它是一个实现细节,但它在Python版本之间有所不同.在更新的Python版本中,hash()和之间的关系id()涉及一些随机化.

但是它实际上如何散列呢？

虽然细节十分复杂,可能涉及到一些先进的数学,对于元组对象的散列函数的实现是用C语言编写,并且可以看到这里(见static Py_hash_t tuplehash(PyTupleObject *v).

计算涉及使用每个元组元素的哈希对常量进行异或运算.负责元素散列的行是这样的:

y = PyObject_Hash(*p++);

所以,回答你原来的问题:它有一堆XOR hokus-pocus和它的每个元素的哈希.是否使用这些元素的内容取决于它们的特定散列函数.

Answer 2

哈希的核心契约是等对象具有相等的哈希值.特别是,散列并不直接关注可变性或突变; 它只关心影响平等比较的突变.

你的第一个元组是不可取的,因为改变嵌套列表会改变元组在相等比较中的行为方式.

a0在第二个示例中进行变换不会影响元组的散列,因为它不会影响相等比较.a0仍然只等于它自己,它的哈希值不变.

tb并且tc在您的第三个示例中具有相等的哈希值,因为它们是相等的元组,无论它们的元素是否是相同的对象.

这一切都意味着元组不能(直接)id用于散列.如果他们这样做了,具有不同但相同元素的相等元组可以不同地散列,违反散列合同.如果没有特殊的外壳元素类型,元组可以用来计算它们自己的哈希的唯一东西是它们的元素的哈希,所以元组将它们的哈希基于它们的元素的哈希.

Answer 3

问题“元组的哈希是根据身份还是值计算的？”的答案 是：都不是。

正确答案是元组的哈希值是根据元素的哈希值计算的。如何计算这些哈希值（或多或少）无关紧要。

证明这一点的一个简单方法是查看将列表放入元组时会发生什么：

>>> hash( (1, 2) )
3713081631934410656
>>> hash( (1, []) )
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'

因为列表不可散列，所以包含列表的元组也不可散列。

让我们仔细看看你带来的这个例子：

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

为什么设置不a0.x = 20影响元组的哈希？好吧，如果我们修改此代码以输出 的哈希值a0，您将看到该设置a0.x = 20对a0的哈希值没有影响：

a0 = A()
print(hash(a0))  # -9223363274645980307
a0.x = 20
print(hash(a0))  # -9223363274645980307

这样做的原因是 python 为你实现了一个默认的哈希函数。从文档：

用户定义的类默认有__eq__()和__hash__()方法；与它们相比，所有对象都比较不相等（除了它们自己）并 x.__hash__()返回一个适当的值，以便同时x == y暗示x is y和hash(x) == hash(y)。

默认哈希函数会忽略对象的属性并根据对象的 id 计算哈希。无论您对 进行什么更改a0，其哈希值都将始终保持不变。（虽然可以A通过实现自定义__hash__方法为类的实例定义自定义哈希函数。）

附录：列表不可散列的原因是因为它们是可变的。从文档：

如果一个类定义了可变对象并实现了一个__eq__()方法，它不应该实现__hash__()，因为可散列集合的实现要求键的散列值是不可变的（如果对象的散列值发生变化，它将在错误的散列桶中）。

列表属于这一类。