這是一個相當簡單的問題，我無法找到答案。如果我有一本字典，迭代它的復雜性是什么？換句話說，字典遍歷的時間復雜度是for key in my_dict: print(key)多少？我幼稚的理解是，由于 Python 中的字典是哈希圖，我們需要遍歷字典的所有可能的哈希值。這看起來有點矯枉過正，但也許沒問題，因為隨著我們添加元素，字典會逐漸變大，所以我們通過始終擁有一個幾乎滿載到恒定負載因子的字典來分攤成本？
1 回答
縹緲止盈
TA貢獻2041條經驗 獲得超4個贊
在大多數情況下，遍歷字典總共需要 O(n) 時間，或者每個元素平均需要 O(1) 時間，其中 n 是字典中的項目數。
Python 的字典數據結構有多種不同版本，具體取決于您使用的 Python 版本，但它們都是某種hashtable。哈希表要么具有鍵/值對數組，要么具有鍵數組和并行值數組。通常，數組的固定比例（稱為負載因子）將包含字典項，其余空格保持為空，因此您需要迭代的數組長度是一個固定常數乘以字典項的數量. 這意味著您可以在 O(n) 時間內進行迭代。
在最新版本的 Python中，字典數據結構的數組只是保存另一個數組中每個項目的索引，其中另一個數組中的項目按插入順序保存。這個額外的數組可用于按插入順序迭代字典，仍然在 O(n) 時間內，但不必跳過查找數組中未使用的空格。
請注意，無論哪種方式，我們實際上都不需要計算任何鍵的哈希值來迭代字典的項目。
綜上所述，在某些情況下，迭代字典可能需要超過 O(n) 時間。這樣做的原因是，雖然哈希表的容量在需要插入更多項目時會擴大，但在刪除項目時它不會縮小。（感謝@HeapOverflow 在評論中指出這一點。）
如果刪除了很多項，那么字典項占數組容量的比例可能遠小于負載因子。在這種情況下，數組可以大于固定常數乘以項目數，因此迭代需要超過 O(n) 時間。
對于最近版本中使用的數據結構也是如此，它使用附加數組而不是查找數組進行迭代。當項目被刪除時，它們被簡單地替換為NULL( CPython source ); 大概這樣做是為了允許在 O(1) 時間內刪除，同時保持插入順序。因此，如果刪除了許多項目，附加數組也可能比 O(n) 長。
在大多數應用程序中，從字典中刪除大量項目并不常見。如果您需要這樣做并且擔心有效地迭代這些字典，請考慮僅使用您需要保留的鍵來構建新字典，而不是從現有字典中刪除它們。
添加回答
舉報
0/150
提交
取消