現(xiàn)在是 2025 年，網(wǎng)上已很少見到 Python 字典有序性的相關(guān)討論。自從 Python 在 2018 年發(fā)布 3.7 版本，將“字典保持成員的插入序”寫進語言規(guī)范后，人們已漸漸習(xí)慣有序的字典。那曾經(jīng)調(diào)皮、無序的字典，早已像 2.7 版本一樣成為過去，只在某些老登們憶苦思甜時被提起。

而在那個字典無法保持順序的年代，如果我們要用到有序的字典，我們用什么？答案是：collections.OrderedDict。

但是，隨著內(nèi)置字典已經(jīng)有序，OrderedDict 似乎也漸漸變得不再必要。不過，截止到目前（3.14 版本）為止，它仍然存在于標(biāo)準(zhǔn)庫模塊 collections 中。這主要是出于以下幾個原因：

• 保持向前兼容，已依賴其的舊代碼可以保持不變；
• 行為不同：OrderedDict 在判斷相等性時會將鍵順序納入考量，內(nèi)置字典不會；
• 更多特性：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 類型的內(nèi)部實現(xiàn)，了解在 Python 中實現(xiàn)一個有序的字典，需要做哪些工作。

注：具體來說，標(biāo)準(zhǔn)庫中的 OrderedDict 數(shù)據(jù)結(jié)構(gòu)有 C 和 Python 兩套不同實現(xiàn)，各自適用不同的運行環(huán)境，二者的實現(xiàn)類似；本文針對 Python 版本編寫。

一個雙向鏈表和另一個字典

OrderedDict 是一個有序的字典，它像普通字典一樣支持鍵值對操作，只是保留了鍵的順序。實現(xiàn) OrderedDict 的關(guān)鍵在于以下兩點：

1. 繼承 dict：自動擁有內(nèi)置字典類型的所有操作，所有鍵值對存放在 OrderedDict 對象自身中——self 就是一個 {}；

2. 引入額外數(shù)據(jù)結(jié)構(gòu)：引入額外的有序數(shù)據(jù)結(jié)構(gòu)，讓其作為一種外部參考來維護鍵的順序。

數(shù)據(jù)結(jié)構(gòu)有很多種，到底該使用哪一種來維持鍵的有序性？由于字典是一種基于哈希表（hash table）的高性能結(jié)構(gòu)，最擅長在 O(1) 的時間復(fù)雜度下完成鍵值對的存取操作。因此，OrderedDict 所需的用于保存鍵順序的額外結(jié)構(gòu)，首先應(yīng)滿足性能要求——“維護順序”的過程不能拖慢字典的原操作。

為了達到這個目標(biāo)，OrderedDict 同時使用了兩個數(shù)據(jù)結(jié)構(gòu)：一個雙向鏈表和另一個字典。

1. 雙向鏈表：有序結(jié)構(gòu)，根據(jù)鏈表節(jié)點可以方便地在鏈表中新增或刪除成員（時間復(fù)雜度為 O(1)），節(jié)點所保存的內(nèi)容為 OrderedDict 的鍵名。

2. 另一個字典：在鏈表中查詢一個節(jié)點，通常需要按序遍歷完所有節(jié)點，平均時間復(fù)雜度是 O(n)，這顯然不滿足性能需求，因此 OrderedDict 引入了另一個字典作為鏈表的索引，使用鍵可快速拿到鏈表節(jié)點（時間復(fù)雜度 O(1)）。

整個數(shù)據(jù)結(jié)構(gòu)如下圖所示：

圖：OrderedDict 內(nèi)部數(shù)據(jù)結(jié)構(gòu)示意圖，包含三大數(shù)據(jù)結(jié)構(gòu)：self（保存鍵值對的字典自身）、self.root...（有序雙向鏈表）、self._map（鏈表索引字典）

下面以 __setitem__ 方法為例，詳細看看 OrderedDict 如何完成鍵值對的寫操作，以下是相關(guān)代碼：

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)  # 4

1. 創(chuàng)建一個新的鏈表節(jié)點，并將其存放到 self.__map 中，之后可以通過 key 來快速讀取該節(jié)點；

2. 修改新節(jié)點 link 的前后節(jié)點，將其插入到 root 前，也就是作為尾部節(jié)點加入鏈表；

3. 修改另外兩個相關(guān)節(jié)點 last（原尾節(jié)點）和 root(根節(jié)點)，至此完成整套鏈表操作；

4. 修改自身字典中的對應(yīng)鍵值對。

假設(shè)執(zhí)行代碼 d["aa"] = 4，往字典中插入一個新成員，整套數(shù)據(jù)的變化如下圖所示：

圖：插入鍵值對 "aa": 4，OrderedDict 內(nèi)部數(shù)據(jù)結(jié)構(gòu)發(fā)生的變化

雙向鏈表、鏈表索引字典，以及 OrderedDict 字典自身，都需要處理 "aa": 4 這個新成員。

同 __setitem__() 類似，__delitem__()（刪除成員）和 pop()（彈出成員）方法除修改自身字典外，也需要調(diào)整對應(yīng)鍵在鏈表和索引字典中的數(shù)據(jù)狀態(tài)，在此不再贅述。

為了讓 OrderedDict 在被迭代時能有序返回所有鍵， __iter__ 方法也需要有所調(diào)整，下面是相關(guān)代碼：

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，實際上就是在遍歷它內(nèi)部的雙向鏈表。遍歷由一個 while 循環(huán)完成，它將鏈表中每個節(jié)點通過生成器返回，從而實現(xiàn)有序。

小結(jié)

通過引入額外的數(shù)據(jù)結(jié)構(gòu)，OrderedDict 最終實現(xiàn)了有序。雙向鏈表加索引字典的組合，最大程度降低了 OrderedDict 在數(shù)據(jù)存取時的開銷，雖付出了額外存儲空間，但仍維持了較好的存取性能。

有趣的細節(jié)

在閱讀 OrderedDict 實現(xiàn)時，我發(fā)現(xiàn)幾個有趣的細節(jié)。

1. 對 weakref 的使用

Python 語言的垃圾回收主要基于引用計數(shù)完成。引用計數(shù)算法簡單高效，但唯獨無法很好地處理“環(huán)形引用”。以下面這個場景舉例，在操作雙向鏈表時，向鏈表尾部插入新節(jié)點，需要：

• 將新節(jié)點的下一個節(jié)點修改為根節(jié)點（link.next = root）
• 將根節(jié)點的上一個節(jié)點修改為新節(jié)點（link = root.prev）

這將在 link 和 root 對象之間創(chuàng)建一個環(huán)形引用，二者都將使對方的引用計數(shù)加一，最終導(dǎo)致無法有效被 GC 及時回收。

介于此，OrderedDict 在處理類似情況時使用了 weakref^[1] 模塊。相關(guān)代碼如下：

link.prev, link.next, link.key = last, root, key  # 1
last.next = link
root.prev = proxy(link)  # 2

•  link 和 root 通過 link.next 建立了一個方向的引用關(guān)系；
• root 和 link 再通過 root.prev 建立另一個方向的引用關(guān)系，但這次采用 proxy(...) 修飾了 link 對象，其中 proxy 來自于 weakref 模塊。

一旦對象被 weakref 模塊修飾過，引用它將不會觸發(fā)引用計數(shù)器的增長，這有效阻止了“環(huán)形引用”的產(chǎn)生，能讓 GC 更及時地回收內(nèi)存。

2. 傳入 object() 作為默認(rèn)值

同內(nèi)置字典一樣，OrderdedDict 也需要支持 pop 操作。pop 方法負(fù)責(zé)從字典中“彈出”一個鍵（key）所對應(yīng)的值，如果 key 不存在，返回調(diào)用方法時傳入的 default 默認(rèn)值。

>>> d = {"a": 1}
>>> d.pop("a", 42)
1
>>> d.pop("c", 42)
42  # "c" 不存在，返回默認(rèn)值 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 不存在時的默認(rèn)值。marker 并不是什么魔法對象，它僅僅只是類初始化時創(chuàng)建的一個小 object()。

為什么選擇一個 object() 作為默認(rèn)值？這是因為，此處需要通過 pop(...) 的返回值來嚴(yán)格區(qū)分“key 存在”和“key 不存在”兩種情況。所以，一個絕不可能在用戶字典中出現(xiàn)的新鮮熱乎的 object() 對象，是最為理想的默認(rèn)值選擇。

引用鏈接

[1] weakref: https://docs.python.org/3/library/weakref.html