python - 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
>>> 

这就是为什么您在这里看到可怕的运行时的原因，但请注意，即使它们有 O(N) 的最坏情况（一切都是哈希冲突），您也可以期待 O(1) 的集合中的摊销成员资格检查。由于 Python 的智能实现，最坏的情况不太可能发生。