Q

Python詞典詳細信息

2013-02-02 130 views 1 likes

1

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

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

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

2013-02-02 c_programmer_jim

A

回答

5

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

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

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

2013-02-02 17:45:18

+0

輝煌，這是一個好的開始。謝謝 –

+0

+1的回答速度！問題發佈後僅需33秒:) – namit

2

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

2013-02-02 17:46:46

2

也..。這是一個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

2013-02-02 17:52:02 namit

+0

您是否測試過針對內置字典（在不同的場景中）的實現？ –

+0

哇，這很好！ –

+0

是的......我測試了它們的默認尺寸，它是Python內置的詞典的1/4。 – namit

相關問題