Python set() 和 __hash__ 混淆

Question

我定义的其中一个类在 set() 中用于过滤掉相等的对象。但它并没有像我预期的那样工作，所以我显然理解错了。

class Foo(object):

    def __hash__(self):
        return 7

x = set()
x.add(Foo())
assert len(x) == 1
x.add(Foo())
assert len(x) == 1    # AssertionError

我希望集合只包含一个元素，但它有两个。这是为什么？

Answer 1

散列冲突已知发生在集合(散列映射)中，没有任何散列算法足够好，可以为每个项目都有一个唯一的散列，否则将花费很长时间来计算。当确实发生冲突时，python 回退到使用 __eq__ 检查值的相等性以确保它们不相同。

class Foo(object):

    def __hash__(self):
        return 7
    def __eq__(self, other):
        return True

>>> x = set()
>>> x.add(Foo())
>>> assert len(x) == 1
>>> x.add(Foo())
>>> assert len(x) == 1
>>> 

这就是为什么您在 here 上看到可怕的运行时间的原因但请注意，即使它们有 O(N) 最坏情况(一切都是散列冲突)，您也可以期望 O(1) 分摊成员资格检查。由于 Python 的智能实现，最坏的情况非常非常不可能发生。