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的智能实现,最糟糕的情况非常不太可能发生.