Python dict如何在碰撞發生時存儲key，value？

Question

Python如何存儲字典鍵，在散列表中發生碰撞時的值？什麼是散列算法用來獲取散列值？

Answer 1

簡短版本：Python規範未指定字典實現，但CPython使用哈希映射並處理與開放尋址的衝突。

請參閱this answer to a similar question以及Wikipedia page on hash tables。

Answer 2

對於「正常」的Python，this great writeup由普利文Gollakota解釋非常好，這裏是重要的位：

• Python字典實現爲哈希表。散列表由插槽組成，密鑰通過散列函數映射到插槽。
• 散列表實現必須允許散列衝突，即使兩個鍵具有相同的散列值，表的實現必須具有明確插入和檢索鍵和值對的策略。
• Python字典使用開放尋址來解決散列衝突（請參閱dictobject.c：296-297）。
• 在開放尋址中，散列衝突通過探測來解決（如下所述）。
• 哈希表只是一個連續的內存塊（就像一個數組，因此您可以通過索引執行O(1)查找）。
• 散列表中的每個插槽可以存儲一個條目並且只存儲一個條目。這個很重要。
• 表中的每個條目實際上是三個條目的組合 - <hash, key, value>。這是作爲C結構實現的（請參見dictobject.h：51-56）。
• 當一個新的字典被初始化時，它從8個插槽開始。 （請參見dictobject.h：49）
• 將條目添加到表中時，我們從基於密鑰散列的某個插槽i開始。 CPython使用最初的i = hash(key) & mask，其中mask = PyDictMINSIZE - 1，但這並不重要。請注意，檢查的初始插槽i取決於密鑰的散列值。
• 如果該插槽爲空，則將該條目添加到插槽中（通過條目，我的意思是，<hash|key|value>）。但是如果那個插槽被佔用了！？很有可能是因爲另一個條目具有相同的散列（散列衝突！）
• 如果插槽被佔用，CPython（甚至PyPy）比較散列和鍵（通過比較我的意思是==比較不是是是比較） （dictobject.c 337,344-345）中的條目中的條目。如果兩者都匹配，則認爲該條目已經存在，放棄並移動到下一個要插入的條目。如果哈希或密鑰不匹配，則開始探測。
• 探測只是意味着它通過插槽搜索插槽來查找空插槽。從技術上講，我們可以一個接一個，i+1,i+2，...並使用第一個可用的（即線性探測）。但出於在評論中精美地解釋的原因（參見dictobject.c：33-126），CPython使用隨機探測。在隨機探測中，下一個時隙是以僞隨機順序選取的。該條目被添加到第一個空插槽。對於本次討論，用於選擇下一個時隙的實際算法並不重要（有關探測算法，請參閱dictobject.c：33-126）。重要的是插槽被探測直到找到第一個空插槽。
• 同樣的事情發生查找，只是從最初的插槽i（其中i取決於密鑰的散列）開始。如果散列和密鑰都與插槽中的條目不匹配，則會開始探測，直到找到一個匹配的插槽。如果所有插槽都耗盡，則報告失敗。
• 爲避免查找速度變慢，字典在三分之二滿時將被調整大小（請參閱dictobject.h：64-65）。