set 中的哈希表在 python 中如何工作？

据我所知，set在python中通过哈希表来实现O(1)查找复杂度。虽然它是哈希表，但其中的每个条目set必须是可散列的（或不可变的）。 所以这种和平的代码引发了异常：

>>> {dict()}
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'

Because dict不可散列。但是我们可以创建我们自己的类继承自dict并实施__hash__魔法方法。我以这种方式创建了自己的：

>>> class D(dict):
...     def __hash__(self):
...             return 3
...

我知道它不应该正常工作，但我只是想尝试一下。所以我检查了我现在可以在中使用这种类型set:

>>> {D()}
{{}}
>>> {D(name='ali')}
{{'name': 'ali'}}

到目前为止一切顺利，但我认为这种实施方式__hash__魔术方法会搞砸查找set。因为每一个对象的D具有相同的哈希值。

>>> d1 = D(n=1)
>>> d2 = D(n=2)
>>> hash(d1), hash(d2)
(3, 3)
>>> 
>>> {d1, d2}
{{'n': 2}, {'n': 1}}

但令我惊讶的是：

>>> d3 = D()
>>> d3 in {d1, d2}
False

我预计结果是True，因为散列d3 is 3目前我们的集合中存在具有相同哈希值的值。如何set内部工作？

为了可以在集合和字典中使用，__hash__方法必须保证如果x == y, then hash(x) == hash(y)。但这是一种片面的暗示。根本不需要如果hash(x) == hash(h) then x == y一定是真的。事实上，这通常是不可能实现的（例如，有无限数量的不同 Python 整数，但只有有限数量的哈希码 - 那里must是具有相同哈希值的不同整数）。

你的哈希值全部相同就很好。他们只告诉 set/dict 去哪里start看着。然后，将容器中具有相同哈希值的所有对象一一进行比较，以确保相等，直到成功，或者直到尝试了所有此类对象均未成功。

然而，虽然使所有哈希值相同不会损害正确性，但这对性能来说是一场灾难：它有效地将 set/dict 变成了一种异常缓慢的方式来执行O(n)线性搜索。