Python字典迭代器性能

當在Python中使用字典時，this page表示遍歷字典元素的時間複雜度爲O(n)，其中n是字典最大的大小。Python字典迭代器性能

但是，我不認爲有一個明顯的方式來遍歷散列表的元素。在遍歷哈希表的元素時，我可以假設dict.iteritems()有良好的性能，而沒有太多的開銷？

由於字典在Python中使用很多，我假設這是以一種智能的方式實現的。不過，我需要確保。

2015-07-03 Koen

究竟什麼是你問？如果您對字典的實施感興趣，請查看[*「強大的字典」*]（https://www.youtube.com/watch?v=C4Kc8xzcA68）。 – jonrsharpe

目前還不清楚你正在尋找什麼類型的答案。你可以假設有良好的表現，直到你的需求太慢。 – chepner

散列表只不過是一個由散列值索引的數組。迭代元素沒有任何困難。 –

如果你看一下notes on Python's dictionary source code，我認爲相關的要點如下：

這些方法（迭代和主要上市）遍歷每一個潛在的進入

多少潛在條目會作爲最大尺寸（存儲在該字典中的最大鍵數）的函數，有嗎？請查看同一文檔中的以下兩節：

PyDict_SetItem中的最大字典加載。目前設置爲2/3

達到最大負載時的增長率。目前設置爲* 2。

這表明，字典的稀疏性將是周圍某處1/3〜2/3的（除非生長速率設置爲* 4，那麼它的1/6的〜2/3）。所以基本上你會檢查每個密鑰的3個（或6個如果* 4）潛在條目。

當然，無論是3項還是1000，它仍然是O（n），但3似乎是一個非常可接受的常數因子。

順便說一下這裏的源&文檔的其餘部分，包括了DictObject的：

2015-07-04 01:05:28 zehnpaard

謝謝，那正是我正在尋找的！ – Koen

回答