Python詞典詳細信息

Question

我想知道python的Dictionary的源代碼位於何處。我知道源代碼可能難以閱讀，所以我真的只是粗略描述了實現和使用的散列例程。

是否有人知道使用了哪種算法以及它們如何處理碰撞，如果使用鏈接或重建表格。

我知道這個問題有點含糊，所以只有在正確的方向上的一個點將有所幫助。如果有人知道任何有關Python的字典的很好的文檔，那就太棒了。

Answer 1

它位於Objects/dictobject.c文件中。那裏也有一個dictnotes.txt file，以指導你理解源代碼。

Python字典使用散列表和開放尋址將鍵映射到插槽。衝突是通過「擾亂」關鍵來解決的;一個以大步開始的算法，然後使用越來越小的步驟，直到它掃描下一個空槽的表。

網上有幾篇文章，包括this blog post;你也可以拿起美麗的代碼書，以獲得良好的代碼曝光。

Answer 2

源樹對字典的工作原理相當不錯的文檔：http://hg.python.org/cpython/file/ab4b8da79a5f/Objects/dictnotes.txt

Answer 3

也..。這是一個dict這是更有效的活動狀態配方（from 3 to 24 times more space efficient than regular dictionaries）！ 。其他以前的兩個答案都很棒！
http://code.activestate.com/recipes/578375-proof-of-concept-for-a-more-space-efficient-faster/?in=user-178123