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

125 投票

5 回答

46447 浏览

提问于 2025-04-17 11:05

我正在尝试理解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是怎么能有多个哈希值相同的元素的。

字典哈希值自定义类实例相等性哈希冲突

5 个回答

编辑: 下面的回答是处理哈希冲突的一种可能方法，但这并不是Python的实际做法。下面提到的Python维基百科也不准确。@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的维基百科上，你可以找到（伪？）代码，说明Python是如何进行查找的。

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

回答于 2025-04-17 由 Python大师

分享举报

159

这里是我能整理出来的关于Python字典的所有信息（可能比任何人想知道的都要多，但答案是全面的）。特别感谢Duncan，他让我意识到Python字典使用了槽，并引导我深入了解这个话题。

Python字典是通过哈希表来实现的。
哈希表必须处理哈希冲突，也就是说，即使两个键有相同的哈希值，表的实现也必须有策略来明确地插入和检索键值对。
Python字典使用开放寻址法来解决哈希冲突（下面会解释）(参见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使用初始的i = hash(key) & mask。其中mask = PyDictMINSIZE - 1，但这并不重要）。只需注意，检查的初始槽i取决于键的哈希。
如果那个槽是空的，就把条目添加到这个槽中（这里的条目是指<hash|key|value>）。但如果那个槽已经被占用呢！？很可能是因为另一个条目有相同的哈希（哈希冲突！）
如果槽被占用，CPython（甚至PyPy）会比较哈希和键（这里的比较是指==比较，而不是is比较）槽中条目的哈希和当前要插入的条目的键（参见dictobject.c:337,344-345）。如果两个都匹配，那么就认为这个条目已经存在，放弃插入，继续下一个条目。如果哈希或键有一个不匹配，就开始探测。
探测就是逐个搜索槽，找到一个空槽。技术上我们可以一个一个地检查，i+1, i+2, ...，使用第一个可用的槽（这叫线性探测）。但由于评论中解释得很清楚（参见dictobject.c:33-126），CPython使用随机探测。在随机探测中，下一个槽是以伪随机的顺序选择的。条目被添加到第一个空槽。对于这个讨论，选择下一个槽的实际算法并不重要（参见dictobject.c:33-126了解探测算法）。重要的是，槽会被探测，直到找到第一个空槽。
查找时也是同样的过程，只是从初始槽i开始（i取决于键的哈希）。如果哈希和键都不匹配槽中的条目，就开始探测，直到找到一个匹配的槽。如果所有槽都被用完，就会报告失败。
顺便提一下，如果字典的使用率达到三分之二，它会被调整大小。这是为了避免查找变慢。（参见dictobject.h:64-65）

就是这样！Python字典在插入项目时会检查两个键的哈希是否相等以及键的正常相等性（==）。所以总结一下，如果有两个键a和b，并且hash(a)==hash(b)，但a!=b，那么它们可以和谐共存于一个Python字典中。但如果hash(a)==hash(b) 并且 a==b，那么它们不能同时存在于同一个字典中。

因为在每次哈希冲突后都需要探测，太多的哈希冲突会导致查找和插入变得非常慢（正如Duncan在评论中指出的）。

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

虽然知道这些信息（为了炫耀？）是好的，但我不确定它在现实生活中如何使用。因为除非你想故意破坏某些东西，否则为什么两个不相等的对象会有相同的哈希值呢？

回答于 2025-04-17 由 Python大师

分享举报

想了解Python的哈希是怎么运作的，可以看看我在为什么早期返回比else慢？中的回答。

简单来说，哈希值用来在一个表格中选择一个位置。如果这个位置已经有值，并且哈希值匹配，那么就会比较这两个值，看它们是否相等。

如果哈希值匹配但值不相等，程序就会尝试另一个位置。选择这个位置有个公式（我在之前的回答中有提到），它会逐渐使用哈希值中未用到的部分；但一旦这些部分都用完了，程序就会逐个检查哈希表中的所有位置。这样可以确保最终要么找到匹配的值，要么找到一个空位置。当搜索到一个空位置时，就会插入新的值，或者放弃（这取决于我们是要添加值还是获取值）。

需要注意的是，这里没有列表或桶：只有一个哈希表，里面有一定数量的位置，每个哈希值用来生成一系列候选位置。

回答于 2025-04-17 由 Python大师

分享举报

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

5 个回答

撰写回答