Python字典是散列表的一個例子嗎?



Answers

如果你對技術細節感興趣, Beautiful Code中的一篇文章討論了Python的dict實現的內部結構。

Question

Python中的基本數據結構之一是字典,它允許用戶記錄“鍵”來查找任何類型的“值”。 這是否在內部實現為散列表? 如果不是,那是什麼?




對於一個Python字典,除了在hash()上查表外,還必須有更多的字典。 通過粗暴的實驗,我發現了這個哈希碰撞

>>> hash(1.1)
2040142438
>>> hash(4504.1)
2040142438

但它並沒有打破字典:

>>> d = { 1.1: 'a', 4504.1: 'b' }
>>> d[1.1]
'a'
>>> d[4504.1]
'b'

完整性檢查:

>>> for k,v in d.items(): print(hash(k))
2040142438
2040142438

可能還有另外一個超出hash()的查找級別,可以避免字典鍵之間的衝突。 或者也許dict()使用不同的散列。

(順便說一句,這在Python 2.7.10中。在Python 3.4.3和3.5.0中,在hash(1.1) == hash(214748749.8)處發生衝突時出現hash(1.1) == hash(214748749.8) 。)




Related