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的智能实现，最坏的情况非常不可能发生。