Python 字典是如何解决哈希冲突的

一起来探索 Python 字典的奥妙吧

本文主要翻译自 so 上面的问题 Why can a Python dict have multiple keys with the same hash? 下 Praveen Gollakota 的答案

Python 字典是通过哈希表实现的

哈希表必然存在哈希冲突。比如：就算两个键存在相同的哈希值，哈希表必须要有策略用来明确两个值插入和读取

Python 字典使用开放寻址法解决哈希冲突（下面展开讲）（源码：dictobject.c:296-297）

Python 的哈希表仅仅是一块连续的内存（类似于数组，因此可以使用索引进行 O(1) 的查找）

表里的每个插槽只能存储一个 entry，这是很重要的

表里的每个 entry 实际上存储了三个值，这是由 C 结构实现的（详见 dictobject.h:51-56）

下面是 Python 哈希表的逻辑示例图，0，1，...，i，... 这些数是对插槽的索引（仅仅只是为了说明，实际上它们并没有与表格一起存放）

新字典初始化时拥有 8 个插槽（见 dictobject.h:49）

当往哈希表中添加 entry 时，我们以一些插槽开始，比如 i，它是基于对键的哈希。Cpython 使用 <code>i = hash(key) &amp; mask</code> 初始化（这里 <code>mask = PyDictMINSIZE - 1</code>，但这不是重点），注意初始值 i 取决于对键的哈希

如果该插槽是空的，entry 将会被添加到插槽中（entry 即 <code>&lt;hash|key|value&gt;</code>），如果插槽已经被占用时怎么办呢？这常常是由于其它的 entry 拥有相同的哈希值（即哈希冲突）

如果插槽被占用，CPython（包括 PyPy）会对比已占用的和将被插入的 entry 的哈希值和键（使用 <code>==</code> 对比而不是 <code>is</code>）（见：dictobject.c:337,344-345），如果两个都相同，则认为这个 entry 已经存在，继而转向下一个被插入的 entry。如果存在哈希和键中某一个不匹配，则会开始查找

查找意味它会一个一个的查看插槽是否为空，以找到一个空的插槽。技术上来说，我们可以通过不断加 1，如 i+1，i+2，...一旦找到可用的就停止（即线性查找）。但是，因为某些原因（源代码的注释非常漂亮的阐明了这些原因，见 dictobject.c:33-126），CPython 使用了随机查找。在随机查找中，下一个插槽的位置是一个伪随机数，而 entry 也会被添加到找到的第一个空的插槽中。具体的算法对于本次讨论来说并不太重要（具体可以查看 dictobject.c:33-126）。重要的是当第一个空插槽被找到时，查找则停止

同样的事情也发生在索引的时候，它始于初始化的值 i（i 取决于键的哈希值），如果对应的插槽所在的 entry 哈希值和键都不匹配，则会开始查找，直到找到一个匹配的插槽。如果所有的插槽都找遍了也没有找到匹配的，则会报告错误

另外，字典将会在占用了 2/3 的时候重新调整大小，这会避免降低查找的速度（见 dictobject.h:64-65）

实际测试效果如下：