python3.7的字典是有序的

• 2020 年 1 月 2 日
• 筆記

python3.7的字典是有序的

舊結構

python3.7之前的字典結構，經典粗暴的hash表實現方式，這樣的話每次hash表的擴容和縮容都可能導致hash值的改變。

hash表容量更新的前後，它的鍵之間的相對順序是會變化的，因此字典的元素是無序的。舊結構類似下面

--+-------------------------------+    | 哈希值 (hash)  鍵 (key)  值 (value)  --+-------------------------------+  0 |    hash0      key0    value0  --+-------------------------------+  1 |    hash1      key1    value1  --+-------------------------------+  2 |    hash2      key2    value2  --+-------------------------------+  . |           ...  __+_______________________________+

新結構

Indices  ----------------------------------------------------  None | index0 | None | None | index2 | None | index1 ...  ----------------------------------------------------    Entries  --------------------  hash0   key0  value0  ---------------------  hash1   key1  value1  ---------------------  hash2   key2  value2  ---------------------          ...  ---------------------

新結構由 Indices(索引，數組實現) 和 Entries(實體，PyDictObject類型) 兩種結構組成。

• 當插入一個數據時，先計算數據對應的hash值並映射成 Indices 數組的一個下標，沒有衝突的話就將另一個值 Entries_index(暫時這麼叫吧) 填入Indices數組中下標對應的位置。並在Entries後面追加一行記錄，類似 hash值, key值, value值 。如果衝突的話可以用基本的解決衝突的辦法，這裡不贅述了。

這種方法，字典 增刪改查的時間複雜度 會有以前的O(1) 變為O(2)，因為多了一步查找的過程。而且字典擴容和縮容時要按照Indices的順序來保持字典始終有序。

但是至少有兩個優化。

• 字典佔用的記憶體變小了。舊的字典總會預留大於 1/3的容量的hash位置，防止hash碰撞過多影響效率。現在則不必預留。
• 字典有序了。

源碼見： dictobject.h

dictobject.c

記於：2019/07/23