python - 奇怪的 Python 集合和散列行为 - 这是如何工作的？

Question

我有一个类(class)叫 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

你有一个哈希冲突。在散列冲突时，集合使用 == 运算符来检查它们是否真的彼此相等。