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

我期望这个集合只有一个元素，但实际上它有两个。这是为什么呢？

- Niklas R

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

- jamylak

---

那我还需要重写__eq__方法，才能得到一个只包含唯一对象的集合？（当然是在我的上下文中唯一） - Niklas R

没有哈希算法足够好，可以为每个项提供唯一的哈希值，否则计算时间会很长。这并不是真的（例如Python的hash(x)，其中x是一个int，返回x，因此哈希值之间没有冲突），但是假设哈希表当前有N个桶 - 哈希表实现将执行类似于bucket = hash_value％N的操作来选择一个桶，而X，X + N，X + 2N等的哈希值都会在同一个桶上发生冲突。您可能已经知道这一点，但当前的措辞确实表达了相反的意思，可能会让读者感到困惑... - Tony Delroy