python - python如何计算元组的哈希值

Question

在 python 中，如果我有一个包含许多元素的元组，它的哈希值是从它的元素的 id 计算出来的s 或其元素的内容？

在这个例子中，

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

If I have a tuple with many elements, is its hash calculated from its elements' ids or its elements' content?

两者都不。它是根据这些元素的哈希值计算的，而不是它们的“内容”(值/属性)，也不是 ID。

基础知识:为什么使用散列的方式
查看 python 文档词汇表中的 this paragraph 。
某些东西是否可散列，以及如何散列，取决于其 __hash__() 方法的实现。 Python 本身并不知道对象的可变性。
散列对于识别对象很有用。例如，它加快了从 dict 检索数据的速度，通过有限间隔中的单个数值(键的哈希)识别键的任意值。
在对象的整个生命周期内，哈希值应该保持不变。 否则，一个对象可以映射到 dict 中的两个不同值，或者在其散列更改后立即被包含在 set 中两次。
仅通过哈希比较两个对象是不够的:在一天结束时，您可能仍需要执行相等性检查 because there may be a collision between the hashes of different objects 。这就是为什么需要 可散列对象来实现 __eq__()。
这与可变性有关:如果一个可散列对象发生变异，以至于它改变了与可散列对象的相等比较，尤其是具有相同散列的对象 - 它违反了契约，并且可能导致与变异散列相同的怪异。 Hashable 对象不应改变它们之间的比较。
彼此相等的可散列对象应该具有相同的散列。 这是一个使其他一切变得更简单的通用契约 - 很自然地假设 x == y 意味着 x 和 y 都映射到 dict 中的相同值。

元组的哈希
考虑你的第一个例子。 tuple 根据其元素对自身进行散列，而其第二个元素 list 根本没有散列 - __hash__ 方法并未为其实现。所以 tuple.__hash__ 方法失败了。
这就是为什么内部带有 tuple 对象的 list 不可散列的原因。如您所见，因此说 tuple 哈希基于其元素的 ID 也是不正确的。
请注意，如果 list 在这里是可散列的，并且散列是基于其元素的，那么更改它们将更改外部 tuple 的散列，从而破坏契约(Contract)。

为什么我的自定义类不需要 __hash__() ？
让我们来看看 python data model documentation ，以及它对这个话题的看法:

User-defined classes have __eq__() and __hash__() methods by default; with them, all objects compare unequal (except with themselves) and x.__hash__() returns an appropriate value such that x == y implies both that x is y and hash(x) == hash(y).

简单地说，默认实现比较对象身份，这与对象属性无关。这就是为什么您可以在不更改其散列的情况下更改自定义类对象“内部”的值。
这也是为什么您不必为您的类定义 __hash__() - 在这种情况下，python 会为您完成。
在这方面你是对的 - 自定义类的散列函数的默认(CPython)实现依赖于对象的 id() (而不是“内部”的值)。这是一个实现细节，它因 Python 版本而异。
在更新的 Python 版本中，hash() 和 id() 之间的关系涉及随机化。这可以防止某些形式的 denial of service attacks ，在这种情况下，创建任意哈希冲突可能会显着降低 Web 应用程序的速度。见 PEP-456 。

它实际上是如何散列自身的？
虽然细节相当复杂，可能涉及一些高级数学，但元组对象的哈希函数的实现是用 C 编写的，可以看到 here(参见 static Py_hash_t tuplehash(PyTupleObject *v) .
该计算涉及将一个常量与每个元组元素的散列进行异或运算。负责散列元素的行是这样的:

y = PyObject_Hash(*p++);

因此，要回答您的原始问题:它对其每个元素 的 哈希进行了一堆 XOR hokus-pocus。是否考虑这些元素的内容和属性取决于它们特定的哈希函数。