为什么Python dict会有多个具有相同散列的键？

Question

我试图了解Python hash的功能。我创建了一个自定义类，其中所有实例都返回相同的哈希值。

class C:
    def __hash__(self):
        return 42

我只是假设任何时候以上类的一个实例都可以在dict中，但是实际上dict可以有多个具有相同散列的元素。

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# note that the dict has 2 elements

[我进行了更多的实验，发现如果我重写__eq__方法，以使该类的所有实例都相等，则dict仅允许一个实例。

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# note that the dict only has 1 element

所以我很好奇知道dict如何具有多个具有相同散列的元素。

Answer 1

有关Python哈希的工作原理的详细说明，请参见我对Why is early return slower than else?的回答

基本上，它使用散列在表中选择一个插槽。如果插槽中有一个值并且哈希值匹配，它将比较各项以查看它们是否相等。

如果散列不匹配或项目不相等，则尝试另一个槽。有一个公式可以选择（我在引用的答案中对此进行了描述），它会逐渐提取哈希值的未使用部分；但是一旦将其全部用尽，它将最终在哈希表中的所有插槽中工作。这样可以保证最终我们找到匹配的项目或空的广告位。当搜索找到一个空插槽时，它会插入值或放弃（取决于我们是添加还是获取值）。

要注意的重要一点是，没有列表或存储桶：只有一个具有特定数量的插槽的哈希表，并且每个哈希用于生成一系列候选插槽。

Answer 2

这里是我能够整理的有关Python字典的所有内容（可能比任何人都想知道的要多；但是答案很全面）。向Duncan喊叫，指出Python字典使用插槽并将我引向这个兔子洞。

• Python字典被实现为哈希表。
• 哈希表必须允许哈希冲突，即即使两个键具有相同的哈希值，该表的实现也必须具有明确插入和检索键和值对的策略。
• Python dict使用开放地址解决哈希冲突（如下所述）（请参见dictobject.c:296-297）。>>
• Python哈希表只是一个连续的内存块（有点像数组，因此您可以按索引进行O(1)查找）。
• 表中的每个插槽只能存储一个条目。
这很重要表中的
• 每个entry
实际上是三个值的组合-。这是作为C结构实现的（请参见dictobject.h:51-56）

• 下图是python哈希表的逻辑表示。在下图中，左侧的0、1 、、 ...，i，...是哈希表中slots

的索引（它们仅用于说明目的，显然不与表一起存储！）。

# Logical model of Python Hash table
-+-----------------+
0| <hash|key|value>|
-+-----------------+
1|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
i|      ...        |
-+-----------------+
.|      ...        |
-+-----------------+
n|      ...        |
-+-----------------+

初始化新字典时，它以8 slots

开头。 （请参阅dictobject.h:49）

[向表添加条目时，我们从某个插槽开始，i基于键的哈希值。 CPython使用初始i = hash(key) & mask。 mask = PyDictMINSIZE - 1，但这并不重要）。只需注意，选中的初始插槽i取决于键的hash

。

[如果该插槽为空，则将条目添加到插槽中（我指的是<hash|key|value>）。但是，如果那个插槽被占用了呢？最可能是因为另一个条目具有相同的哈希（哈希冲突！）

如果插槽被占用，则CPython（甚至PyPy）将插槽中的项与键比较哈希和键

（通过比较，我的意思是==比较而不是is比较）当前要插入的条目的编号（dictobject.c:337，344-345）。如果both匹配，则认为该条目已存在，放弃并继续进行下一个要插入的条目。如果哈希或密钥不匹配，它将开始probing。

探测仅表示它按插槽搜索插槽以找到一个空插槽。从技术上讲，我们可以一个接一个地进行，i + 1，i + 2，...，然后使用第一个可用的（线性探测）。但是由于注释中详细解释的原因（请参见dictobject.c:33-126），CPython使用random probing

。在随机探测中，以伪随机顺序拾取下一个时隙。该条目将添加到第一个空插槽。对于此讨论，用于选择下一个时隙的实际算法并不十分重要（有关探测的算法，请参见dictobject.c:33-126）。重要的是对插槽进行探测，直到找到第一个空插槽为止。

查找时也会发生同样的事情，只是从初始插槽i（其中i取决于键的哈希值）开始。如果哈希和密钥都与插槽中的条目不匹配，则它将开始探测，直到找到具有匹配项的插槽。如果所有插槽都用完，则报告失败。

BTW，如果字典满了三分之二，将调整其大小。这样可以避免减慢查找速度。 （请参阅dictobject.h:64-65）

你去！ dict的Python实现在插入项目时检查两个键的哈希相等性和键的正常相等性[==）。因此，总而言之，如果有两个键a和b和hash(a)==hash(b)，但是a!=b，则两者可以在Python字典中和谐地存在。但是，如果hash(a)==hash(b) 和 a==b，则它们不能都位于同一字典中。

因为我们必须在每次哈希冲突之后进行探测，所以太多哈希冲突的副作用是查找和插入将变得非常慢（正如Duncan在comments中指出的那样。

我想我的问题的简短答案是，“因为这就是它在源代码中的实现方式；）”

虽然这很高兴（对于极客点？），但我不确定如何在现实生活中使用它。因为除非您试图显式破坏某些内容，否则为什么两个不相等的对象会具有相同的哈希值？

Answer 3

Edit

Answer 4

哈希表，通常必须允许哈希冲突！您会倒霉，并且有两件事最终会散布到同一件事上。在下面，具有相同哈希键的项目列表中有一组对象。通常，该列表中只有一件事，但是在这种情况下，它将继续将它们堆叠到同一列表中。它知道它们不同的唯一方法是通过equals运算符。

Answer 5

在线程中，当我们将其作为键放入字典中时，我没有看到python对用户定义类的实例有什么作用。让我们阅读一些文档：它声明仅可哈希对象可以用作键。散列是所有不可变的内置类和所有用户定义的类。