Python 的 OrderedDict 为什么有序？ | Piglei

现在是 2025 年，网上已很少见到 Python 字典有序性的相关讨论。自从 Python 在 2018 年发布 3.7 版本，将“字典保持成员的插入序”写进语言规范后，人们已渐渐习惯有序的字典。那曾经调皮、无序的字典，早已像 2.7 版本一样成为过去，只在某些老登们忆苦思甜时被提起。

而在那个字典无法保持顺序的年代，如果我们要用到有序的字典，我们用什么？答案是：collections.OrderedDict。

但是，随着内置字典已经有序，OrderedDict 似乎也渐渐变得不再必要。不过，截止到目前（3.14 版本）为止，它仍然存在于标准库模块 collections 中。这主要是出于以下几个原因：

>>> d
OrderedDict([('a', 1), ('b', 2), ('c', 3)])
>>> d.move_to_end('a')
>>> d
OrderedDict([('b', 2), ('c', 3), ('a', 1)])    # 1

本文将深入 OrderedDict 类型的内部实现，了解在 Python 中实现一个有序的字典，需要做哪些工作。

OrderedDict 是一个有序的字典，它像普通字典一样支持键值对操作，只是保留了键的顺序。实现 OrderedDict 的关键在于以下两点：

数据结构有很多种，到底该使用哪一种来维持键的有序性？由于字典是一种基于哈希表（hash table）的高性能结构，最擅长在 O(1) 的时间复杂度下完成键值对的存取操作。因此，OrderedDict 所需的用于保存键顺序的额外结构，首先应满足性能要求——“维护顺序”的过程不能拖慢字典的原操作。

为了达到这个目标，OrderedDict 同时使用了两个数据结构：一个双向链表和另一个字典。

整个数据结构如下图所示：

图：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)  # 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 实现时，我发现几个有趣的细节。

Python 语言的垃圾回收主要基于引用计数完成。引用计数算法简单高效，但唯独无法很好地处理“环形引用”。以下面这个场景举例，在操作双向链表时，向链表尾部插入新节点，需要：

这将在 link 和 root 对象之间创建一个环形引用，二者都将使对方的引用计数加一，最终导致无法有效被 GC 及时回收。

介于此，OrderedDict 在处理类似情况时使用了 weakref 模块。相关代码如下：

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

一旦对象被 weakref 模块修饰过，引用它将不会触发引用计数器的增长，这有效阻止了“环形引用”的产生，能让 GC 更及时地回收内存。

同内置字典一样，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() 对象，是最为理想的默认值选择。