python如何计算元组的哈希值

新手上路,请多包涵

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

在这个例子中,

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

它错误地指出 list is unhashable。所以我猜它不是由 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

似乎 bc 的内容用于哈希计算。

我应该如何理解这些例子?

原文由 nos 发布,翻译遵循 CC BY-SA 4.0 许可协议

阅读 624
2 个回答

如果我有一个包含许多元素的元组,它的哈希值是根据元素的 ID 还是元素的内容计算的?

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


基础知识:为什么按原样使用散列

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

某些东西是否可散列,以及如何散列,取决于其 __hash__() 方法的实现。就其本身而言,Python 并不知道对象的可变性。它的实现有望提供适当的机制并避免陷阱。

散列可用于识别对象。例如,它加快了从 dict 中检索数据的速度,通过有限区间中的单个数值(键的哈希值)识别键的任意值。

在对象的整个生命周期中,散列应保持不变。 否则,一个对象可能会映射到 dict 中的两个不同值,或者一旦其哈希值发生变化,就会两次包含到 set 中。

仅通过哈希比较两个对象是不够的:在一天结束时,您可能仍需要执行相等性检查, 因为两个不同对象的哈希之间可能存在冲突。这就是为什么 可哈希对象需要实现 __eq__() 的原因。

这与可变性有关:如果可哈希对象发生变异,从而改变 了与 hashables 的相等性比较,尤其是那些具有相同哈希的对象——它会破坏契约,并可能导致与变异哈希相同的怪异。 可散列对象不应改变它们之间的比较。

彼此相等的可散列对象 具有相同的散列。 这是一个使其他一切都变得更简单的一般合同——很自然地假设 x == y 意味着 xy 映射到相同的值 dict


元组的哈希

考虑你的第一个例子。 tuple 根据其元素对自身进行散列,而其第二个元素 list 根本没有散列 - __hash__ 方法是没有为它实施。因此 tuple.__hash__ 方法失败。

这就是为什么一个 tuple 里面有一个 list 对象是不可哈希的。正如您所见,因此说 tuple 散列基于其元素的 ID 也是不正确的。

请注意,如果 list 在这里是可散列的,并且散列是基于其元素的,更改它们将更改外部 tuple 的散列,从而违反合同。


为什么我的自定义类不需要 __hash__()

让我们看看 python 数据模型文档,以及它对这个主题的看法:

用户自定义类默认有 __eq__()__hash__() 方法; 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() 之间的关系涉及随机化。这可以防止某些形式的 拒绝服务攻击,在这种情况下,创建任意哈希冲突可能会显着降低 Web 应用程序的速度。请参阅 PEP-456


它实际上如何散列自身?

虽然细节相当复杂并且可能涉及一些高等数学,但元组对象的哈希函数的实现是用 C 语言编写的,可以在 此处查看(参见 static Py_hash_t tuplehash(PyTupleObject *v) )。

计算涉及将一个常量与每个元组元素的哈希值进行异或运算。负责元素散列的行是这一行:

 y = PyObject_Hash(*p++);


所以,回答你最初的问题:它用它 的每个元素的散列 做了一堆 XOR hokus-pocus。是否考虑这些元素的内容和属性取决于它们特定的哈希函数。

原文由 Błażej Michalik 发布,翻译遵循 CC BY-SA 4.0 许可协议

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


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

在您的第二个示例中,变异 a0 不会影响元组的散列,因为它不会影响相等性比较。 a0 仍然只等于它自己,它的散列没有改变。

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


这一切都意味着元组不能(直接)使用 id 作为散列。如果他们这样做了,具有不同但相等元素的相等元组可能会以不同方式散列,从而违反散列契约。如果没有特殊的元素类型,元组唯一可以用来计算它们自己的散列的是它们元素的散列,所以元组的散列基于它们元素的散列。

原文由 user2357112 发布,翻译遵循 CC BY-SA 3.0 许可协议

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题