Python 的 OrderedDict 為什么有序？
現在是 2025 年，網上已很少見到 Python 字典有序性的相關討論。自從 Python 在 2018 年發布 3.7 版本，將“字典保持成員的插入序”寫進語言規范后，人們已漸漸習慣有序的字典。那曾經調皮、無序的字典，早已像 2.7 版本一樣成為過去，只在某些老登們憶苦思甜時被提起。
而在那個字典無法保持順序的年代，如果我們要用到有序的字典，我們用什么？答案是：collections.OrderedDict。
但是，隨著內置字典已經有序，OrderedDict 似乎也漸漸變得不再必要。不過，截止到目前（3.14 版本）為止，它仍然存在于標準庫模塊 collections 中。這主要是出于以下幾個原因：
- 保持向前兼容，已依賴其的舊代碼可以保持不變；
- 行為不同：
OrderedDict在判斷相等性時會將鍵順序納入考量，內置字典不會； - 更多特性：
OrderedDict擁有move_to_end等方法。
>>> d
OrderedDict([('a', 1), ('b', 2), ('c', 3)])
>>> d.move_to_end('a')
>>> d
OrderedDict([('b', 2), ('c', 3), ('a', 1)]) # 1-
move_to_end()可以把某個鍵移動到字典的末尾
本文將深入 OrderedDict 類型的內部實現，了解在 Python 中實現一個有序的字典，需要做哪些工作。
注：具體來說，標準庫中的
OrderedDict數據結構有 C 和 Python 兩套不同實現，各自適用不同的運行環境，二者的實現類似；本文針對 Python 版本編寫。
一個雙向鏈表和另一個字典
OrderedDict 是一個有序的字典，它像普通字典一樣支持鍵值對操作，只是保留了鍵的順序。實現 OrderedDict 的關鍵在于以下兩點：
1. 繼承 dict：自動擁有內置字典類型的所有操作，所有鍵值對存放在 OrderedDict 對象自身中——self 就是一個 {}；
2. 引入額外數據結構：引入額外的有序數據結構，讓其作為一種外部參考來維護鍵的順序。
數據結構有很多種，到底該使用哪一種來維持鍵的有序性？由于字典是一種基于哈希表（hash table）的高性能結構，最擅長在 O(1) 的時間復雜度下完成鍵值對的存取操作。因此，OrderedDict 所需的用于保存鍵順序的額外結構，首先應滿足性能要求——“維護順序”的過程不能拖慢字典的原操作。
為了達到這個目標，OrderedDict 同時使用了兩個數據結構：一個雙向鏈表和另一個字典。
1. 雙向鏈表：有序結構，根據鏈表節點可以方便地在鏈表中新增或刪除成員（時間復雜度為 O(1)），節點所保存的內容為 OrderedDict 的鍵名。
2. 另一個字典：在鏈表中查詢一個節點，通常需要按序遍歷完所有節點，平均時間復雜度是 O(n)，這顯然不滿足性能需求，因此 OrderedDict 引入了另一個字典作為鏈表的索引，使用鍵可快速拿到鏈表節點（時間復雜度 O(1)）。
整個數據結構如下圖所示：
圖：OrderedDict 內部數據結構示意圖，包含三大數據結構：self（保存鍵值對的字典自身）、self.root...（有序雙向鏈表）、self._map（鏈表索引字典）
下面以 __setitem__ 方法為例，詳細看看 OrderedDict 如何完成鍵值對的寫操作，以下是相關代碼：
def __setitem__(self, key, value,
dict_setitem=dict.__setitem__, proxy=_proxy, Link=_Link):
'od.__setitem__(i, y) <==> od[i]=y'
if key not in self:
self.__map[key] = link = Link() # 1
root = self.__root
last = root.prev
link.prev, link.next, link.key = last, root, key # 2
last.next = link
root.prev = proxy(link) # 3
dict_setitem(self, key, value) # 41. 創建一個新的鏈表節點，并將其存放到 self.__map 中，之后可以通過 key 來快速讀取該節點；
2. 修改新節點 link 的前后節點，將其插入到 root 前，也就是作為尾部節點加入鏈表；
3. 修改另外兩個相關節點 last（原尾節點）和 root(根節點)，至此完成整套鏈表操作；
4. 修改自身字典中的對應鍵值對。
假設執行代碼 d["aa"] = 4，往字典中插入一個新成員，整套數據的變化如下圖所示：
圖：插入鍵值對 "aa": 4，OrderedDict 內部數據結構發生的變化
雙向鏈表、鏈表索引字典，以及 OrderedDict 字典自身，都需要處理 "aa": 4 這個新成員。
同 __setitem__() 類似，__delitem__()（刪除成員）和 pop()（彈出成員）方法除修改自身字典外，也需要調整對應鍵在鏈表和索引字典中的數據狀態，在此不再贅述。
為了讓 OrderedDict 在被迭代時能有序返回所有鍵， __iter__ 方法也需要有所調整，下面是相關代碼：
def __iter__(self):
'od.__iter__() <==> iter(od)'
root = self.__root
curr = root.next
while curr is not root:
yield curr.key
curr = curr.next可以看出，遍歷一個 OrderedDict，實際上就是在遍歷它內部的雙向鏈表。遍歷由一個 while 循環完成，它將鏈表中每個節點通過生成器返回，從而實現有序。
小結
通過引入額外的數據結構，OrderedDict 最終實現了有序。雙向鏈表加索引字典的組合，最大程度降低了 OrderedDict 在數據存取時的開銷，雖付出了額外存儲空間，但仍維持了較好的存取性能。
有趣的細節
在閱讀 OrderedDict 實現時，我發現幾個有趣的細節。
1. 對 weakref 的使用
Python 語言的垃圾回收主要基于引用計數完成。引用計數算法簡單高效，但唯獨無法很好地處理“環形引用”。以下面這個場景舉例，在操作雙向鏈表時，向鏈表尾部插入新節點，需要：
- 將新節點的下一個節點修改為根節點（
link.next = root） - 將根節點的上一個節點修改為新節點（
link = root.prev）
這將在 link 和 root 對象之間創建一個環形引用，二者都將使對方的引用計數加一，最終導致無法有效被 GC 及時回收。
介于此，OrderedDict 在處理類似情況時使用了 weakref[1] 模塊。相關代碼如下：
link.prev, link.next, link.key = last, root, key # 1
last.next = link
root.prev = proxy(link) # 2- link 和 root 通過 link.next 建立了一個方向的引用關系；
- root 和 link 再通過 root.prev 建立另一個方向的引用關系，但這次采用
proxy(...)修飾了link對象，其中 proxy 來自于 weakref 模塊。
一旦對象被 weakref 模塊修飾過，引用它將不會觸發引用計數器的增長，這有效阻止了“環形引用”的產生，能讓 GC 更及時地回收內存。
2. 傳入 object() 作為默認值
同內置字典一樣，OrderdedDict 也需要支持 pop 操作。pop 方法負責從字典中“彈出”一個鍵（key）所對應的值，如果 key 不存在，返回調用方法時傳入的 default 默認值。
>>> d = {"a": 1}
>>> d.pop("a", 42)
1
>>> d.pop("c", 42)
42 # "c" 不存在，返回默認值 42對于 OrderdedDict 而言，其在 pop 方法中，需要完成從自身字典中 pop 以及更新雙向鏈表兩件事。核心代碼如下：
class OrderedDict(dict):
__marker = object()
def pop(self, key, default=__marker):
marker = self.__marker
result = dict.pop(self, key, marker)
if result is not marker:
# The same as in __delitem__().
# 更新鏈表部分已省略 ...你可以注意到，在 dict.pop(self, key, marker) 中，代碼傳入了 marker 作為 key 不存在時的默認值。marker 并不是什么魔法對象，它僅僅只是類初始化時創建的一個小 object()。
為什么選擇一個 object() 作為默認值？這是因為，此處需要通過 pop(...) 的返回值來嚴格區分“key 存在”和“key 不存在”兩種情況。所以，一個絕不可能在用戶字典中出現的新鮮熱乎的 object() 對象，是最為理想的默認值選擇。
引用鏈接
[1] weakref: https://docs.python.org/3/library/weakref.html
