为什么 Python 字典可以有多个具有相同哈希值的键？

问题描述：

我正在尝试了解 Pythonhash函数的底层原理。我创建了一个自定义类，其中所有实例都返回相同的哈希值。

class C:
    def __hash__(self):
        return 42

我只是假设在任何时候上述类只有一个实例可以存在于 a 中dict，但实际上 adict可以有多个具有相同哈希值的元素。

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可以拥有具有相同哈希值的多个元素。

解决方案 1：

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

• Python 字典以哈希表的形式实现。

• 哈希表必须允许哈希冲突，即，即使两个键具有相同的哈希值，表的实现也必须具有一种策略来明确地插入和检索键和值对。

• Python dict 使用开放寻址来解决哈希冲突（如下所述）（参见dictobject.c:296-297）。

• Python 哈希表只是一块连续的内存块（有点像数组，因此您可以O(1)通过索引进行查找）。

• 表中的每个槽位只能存储一个条目。这一点很重要

• 表中的每个条目实际上是三个值的组合 -. 这是作为 C 结构实现的（参见dictobject.h:51-56）

• 下图是 Python 哈希表的逻辑表示。下图中，左侧的 0、1、...、i、... 是哈希表中槽的索引（它们仅用于说明目的，显然不与表一起存储！）。

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

• 当初始化一个新的字典时，它以 8 个槽开始。（参见dictobject.h:49）

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

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

• 如果插槽已被占用，CPython（甚至 PyPy）会将插槽中条目的哈希值和键（比较是指==比较而不是比较）与要插入的当前条目的键（ dictobject.c:337、344-345）进行比较。如果两者匹配，则它会认为该条目已经存在，放弃并转到下一个要插入的条目。如果哈希值或键不匹配，它会开始探测。is

• 探测只是意味着它会逐个搜索槽位以找到一个空槽位。从技术上讲，我们可以一个接一个地搜索，i+1、i+2......并使用第一个可用的槽位（这是线性探测）。但由于注释中详细解释的原因（参见dictobject.c:33-126），CPython 使用随机探测。在随机探测中，下一个槽位以伪随机顺序挑选。该条目将添加到第一个空槽位。对于本次讨论，选择下一个槽位的实际算法并不重要（有关探测算法，请参阅dictobject.c:33-126）。重要的是探测槽位，直到找到第一个空槽位。

• 查找也会发生同样的事情，只是从初始槽位 i 开始（其中 i 取决于密钥的哈希值）。如果哈希值和密钥都不匹配槽位中的条目，它就会开始探测，直到找到匹配的槽位。如果所有槽位都已用尽，它会报告失败。

• 顺便说一句，如果字典已满三分之二，则会调整大小。这可以避免减慢查找速度。（请参阅dictobject.h:64-65）

就是这样！Python 的 dict 实现在插入项目时会检查两个键的哈希相等性和==键的正常相等性 ()。因此，总而言之，如果有两个键，a和b和hash(a)==hash(b)，但a!=b，那么它们可以和谐地存在于 Python dict 中。但如果hash(a)==hash(b) 和 a==b，那么它们就不能同时存在于同一个 dict 中。

因为我们必须在每次哈希碰撞之后进行探测，所以过多哈希碰撞的一个副作用是查找和插入会变得非常慢（正如 Duncan 在评论中指出的那样）。

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

虽然知道这一点很好（为了获得极客积分？），但我不确定如何在现实生活中使用它。因为除非你试图明确破坏某些东西，否则为什么两个不相等的对象会有相同的哈希值？

解决方案 2：

有关 Python 散列工作原理的详细描述，请参阅我的回答“为什么早期返回比其他方法慢？”

基本上，它使用哈希值在表中选择一个位置。如果位置中有值并且哈希值匹配，它会比较项目以查看它们是否相等。

如果哈希匹配但项不相等，则它会尝试另一个槽位。有一个公式可以做到这一点（我在参考答案中描述了这一点），它会逐渐拉入哈希值中未使用的部分；但是一旦它用完了所有部分，它最终会遍历哈希表中的所有槽位。这保证了我们最终要么找到匹配项，要么找到一个空槽位。当搜索找到一个空槽位时，它会插入值或放弃（取决于我们是添加还是获取值）。

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

解决方案 3：

编辑：下面的答案是处理哈希冲突的可能方法之一，但这不是Python处理它的方式。下面引用的 Python wiki 也是不正确的。@Duncan 下面给出的最佳来源是实现本身：https://github.com/python/cpython/blob/master/Objects/dictobject.c我为混淆道歉。

它在哈希中存储元素列表（或存储桶），然后遍历该列表，直到找到列表中的实际键。一张图片胜过千言万语：

在这里你可以看到John Smith和Sandra Dee都哈希到152。桶152包含它们两个。查找时，Sandra Dee它首先在桶中找到列表152，然后循环遍历该列表，直到Sandra Dee找到并返回521-6955。

以下内容是错误的，仅用于上下文：在Python 的 wiki上，您可以找到 Python 如何执行查找的（伪？）代码。

实际上，这个问题有几种可能的解决方案，请查看维基百科文章以获得更好的概述：http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

解决方案 4：

哈希表通常必须允许哈希冲突！您可能会不走运，两个东西最终会哈希到同一个东西。在下面，项目列表中有一组具有相同哈希键的对象。通常，该列表中只有一个东西，但在这种情况下，它会继续将它们堆叠到同一个东西中。它知道它们不同的唯一方法是通过等号运算符。

当发生这种情况时，您的性能会随着时间的推移而下降，这就是为什么您希望哈希函数尽可能“随机”。

解决方案 5：

在线程中，我没有看到当我们将用户定义类的实例作为键放入字典中时，python 究竟如何处理这些实例。让我们阅读一些文档：它声明只有可哈希对象才能用作键。可哈希的都是不可变的内置类和所有用户定义类。

用户定义的类默认具有 __cmp__() 和 __hash__() 方法；使用它们，所有对象比较不相等（与它们自身除外）并且 x.__hash__() 返回从 id(x) 派生的结果。

因此，如果您的类中有一个常量 hash__，但没有提供任何 __cmp 或 eq 方法，则您的所有实例对于字典而言都是不平等的。另一方面，如果您提供任何 cmp 或 eq 方法，但没有提供 __hash__，您的实例在字典方面仍然不平等。

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

输出

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}