奇怪的Python集合和哈希行为 - 这是怎么回事？

Question

我有一个叫做 GraphEdge 的类，我希望在一个集合（就是内置的 set 类型）中，能够通过它的 tail 和 head 属性来唯一识别每个元素，这两个属性是在 __init__ 方法中设置的。

如果我不定义 __hash__ 方法，我会看到以下情况：

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('A', 'B')
>>> hash(E)
139731804758160
>>> hash(H)
139731804760784
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B'), ('A', 'B')])

集合无法知道 E 和 H 是我定义的同一个东西，因为它们的哈希值不同（据我所知，集合类型是通过哈希值来判断元素是否唯一的），所以它把这两个元素当作不同的元素添加进集合。因此，我为 GraphEdge 定义了一个比较简单的哈希函数，如下所示：

def __hash__( self ):
    return hash( self.tail ) ^ hash( self.head )

现在，上面的代码按预期工作：

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('A', 'B')
>>> hash(E)
409150083
>>> hash(H)
409150083
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B')])

但很明显，('A', 'B') 和 ('B', 'A') 在这种情况下会返回相同的哈希值，所以我本以为不能把 ('B', 'A') 添加到已经包含 ('A', 'B') 的集合中。但实际上并不是这样：

>>> E = GraphEdge('A', 'B')
>>> H = GraphEdge('B', 'A')
>>> hash(E)
409150083
>>> hash(H)
409150083
>>> S = set()
>>> S.add(E)
>>> S.add(H)
>>> S
set([('A', 'B'), ('B', 'A')])

那么集合类型到底是使用哈希值还是不使用？如果使用的话，最后的情况怎么会发生？如果不使用，为什么第一种情况（没有定义 __hash__）又不奏效？我是不是漏掉了什么？

编辑：为了方便未来的读者，我已经定义了 __eq__ 方法（也是基于 tail 和 head）。

Answer 1

如果你需要使用到 __eq__() 或 __hash__() 中的至少一个，那么你应该同时定义这两个。因为如果两个对象的哈希值相同，系统会额外检查一次 __eq__() 来确认它们是否真的不同。

Answer 2

理解哈希和==是如何一起工作的很重要，因为它们都是集合（sets）使用的。对于两个值x和y，有一个重要的规则：

x == y ==> hash(x) == hash(y)

如果x等于y，那么x和y的哈希值也必须相等。但反过来说并不成立：两个不相等的值也可能有相同的哈希值。

集合（和字典）会用哈希值来大致判断两个值是否相等，但最终还是会用真正的相等操作来确认这两个值是否完全相同。

Answer 3

你遇到了哈希冲突。哈希冲突发生时，集合会使用==运算符来检查它们是否真的相等。