本文主要翻譯自 so 上面的問題 Why can a Python dict have multiple keys with the same hash? 下 Praveen Gollakota 的答案
Python 字典是通過哈希表實(shí)現(xiàn)的
哈希表必然存在哈希沖突崔涂。比如：就算兩個(gè)鍵存在相同的哈希值，哈希表必須要有策略用來明確兩個(gè)值插入和讀取
Python 字典使用開放尋址法解決哈希沖突（下面展開講）（源碼：dictobject.c:296-297）
Python 的哈希表僅僅是一塊連續(xù)的內(nèi)存（類似于數(shù)組始衅，因此可以使用索引進(jìn)行 O(1) 的查找）
表里的每個(gè)插槽只能存儲一個(gè) entry冷蚂，這是很重要的
表里的每個(gè) entry 實(shí)際上存儲了三個(gè)值，這是由 C 結(jié)構(gòu)實(shí)現(xiàn)的（詳見 dictobject.h:51-56）
-
下面是 Python 哈希表的邏輯示例圖汛闸，0蝙茶，1，...蛉拙，i尸闸，... 這些數(shù)是對插槽的索引（僅僅只是為了說明，實(shí)際上它們并沒有與表格一起存放）
# Logical model of Python Hash table -+-----------------+ 0| <hash|key|value>| -+-----------------+ 1| ... | -+-----------------+ .| ... | -+-----------------+ i| ... | -+-----------------+ .| ... | -+-----------------+ n| ... | -+-----------------+ 新字典初始化時(shí)擁有 8 個(gè)插槽（見 dictobject.h:49）
當(dāng)往哈希表中添加 entry 時(shí)孕锄，我們以一些插槽開始吮廉，比如 i，它是基于對鍵的哈希畸肆。Cpython 使用
i = hash(key) & mask初始化（這里mask = PyDictMINSIZE - 1宦芦，但這不是重點(diǎn)），注意初始值 i 取決于對鍵的哈希如果該插槽是空的轴脐，entry 將會被添加到插槽中（entry 即
<hash|key|value>）调卑，如果插槽已經(jīng)被占用時(shí)怎么辦呢抡砂？這常常是由于其它的 entry 擁有相同的哈希值（即哈希沖突）如果插槽被占用，CPython（包括 PyPy）會對比已占用的和將被插入的 entry 的哈希值和鍵（使用
==對比而不是is）（見：dictobject.c:337,344-345）恬涧，如果兩個(gè)都相同注益，則認(rèn)為這個(gè) entry 已經(jīng)存在，繼而轉(zhuǎn)向下一個(gè)被插入的 entry溯捆。如果存在哈希和鍵中某一個(gè)不匹配丑搔，則會開始查找查找意味它會一個(gè)一個(gè)的查看插槽是否為空，以找到一個(gè)空的插槽提揍。技術(shù)上來說啤月，我們可以通過不斷加 1，如 i+1劳跃，i+2谎仲，...一旦找到可用的就停止（即線性查找）。但是刨仑，因?yàn)槟承┰颍ㄔ创a的注釋非常漂亮的闡明了這些原因郑诺，見 dictobject.c:33-126），CPython 使用了隨機(jī)查找贸人。在隨機(jī)查找中间景，下一個(gè)插槽的位置是一個(gè)偽隨機(jī)數(shù)，而 entry 也會被添加到找到的第一個(gè)空的插槽中艺智。具體的算法對于本次討論來說并不太重要（具體可以查看 dictobject.c:33-126）。重要的是當(dāng)?shù)谝粋€(gè)空插槽被找到時(shí)圾亏，查找則停止
同樣的事情也發(fā)生在索引的時(shí)候十拣，它始于初始化的值 i（i 取決于鍵的哈希值），如果對應(yīng)的插槽所在的 entry 哈希值和鍵都不匹配志鹃，則會開始查找夭问，直到找到一個(gè)匹配的插槽。如果所有的插槽都找遍了也沒有找到匹配的曹铃，則會報(bào)告錯(cuò)誤
另外缰趋，字典將會在占用了 2/3 的時(shí)候重新調(diào)整大小，這會避免降低查找的速度（見 dictobject.h:64-65）
實(shí)際測試效果如下：
class HashTester(object):
def __init__(self):
self.value = 42
def __hash__(self):
return self.value
def __eq__(self, other):
return self.value == other.value
class HashTester2(object):
def __hash__(self):
return 42
>>> a = HashTester()
>>> b = HashTester()
>>> {a: 'this is a', b: 'this is b'} # a 與 b 的 hash 和 key 都相等
{<__main__.HashTester object at 0x00000222B7A691C0>: 'this is b'}
>>> e = HashTester2()
>>> f = HashTester2()
>>> {e: 'this is e', f: 'this is f'} # e 與 f 哈希沖突
{<__main__.HashTester2 object at 0x00000222B7A69CD0>: 'this is e', <__main__.HashTester2 object at 0x00000222B7A690A0>: 'this is f'}
