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）

實際測試效果如下：