奇怪的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

你有一个哈希冲突.在哈希冲突时,集合使用==运算符来检查它们是否真正相互相等.

Answer 2

理解hash和==如何一起工作很重要,因为两者都是由集合使用的.对于两个值x和y,重要的规则是:

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

(x等于y意味着x和y的散列相等).但是,反之亦然:两个不相等的值可以具有相同的哈希值.

集合(和dicts)将使用散列来获得相等的近似值,但是将使用实数相等操作来确定两个值是否相同.

Answer 3

你应该总是定义两者__eq__(),__hash__()如果你需要至少其中一个.如果两个对象的哈希值相等,则进行额外__eq__()检查以验证唯一性.