Python 的 OrderedDict 为什么有序？

将 脚本之家 设为“星标⭐”
第一时间收到文章更新

来源 | piglei（ID：real-piglei）

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

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

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

1. 保持向前兼容，已依赖其的旧代码可以保持不变；
2. 行为不同：OrderedDict 在判断相等性时会将键顺序纳入考量，内置字典不会；
3. 更多特性：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

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

1. 创建一个新的链表节点，并将其存放到 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 语言的垃圾回收主要基于引用计数完成。引用计数算法简单高效，但唯独无法很好地处理“环形引用”。以下面这个场景举例，在操作双向链表时，向链表尾部插入新节点，需要：

1. 将新节点的下一个节点修改为根节点（link.next = root）
2. 将根节点的上一个节点修改为新节点（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

1. link 和 root 通过 link.next 建立了一个方向的引用关系；

2. 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

END




    
  推荐阅读：