Python OrderedDict 有序字典

说明

《Python 教程》持续更新中，提供建议、纠错、催更等加作者微信: gairuo123（备注：pandas教程）和关注公众号「盖若」ID: gairuo。跟作者学习，请进入 Python学习课程。欢迎关注作者出版的书籍：《深入浅出Pandas》和《Python之光》。

有序词典就像常规词典一样，但有一些与排序操作相关的额外功能。由于内置的 dict 类获得了记住插入顺序的能力（在 Python 3.7 中保证了这种新行为），它们变得不那么重要了。注意，本文基于 Python 3.9。

快速使用

from collections import OrderedDict
d = OrderedDict()
d['a'] = 1
d['c'] = 3
d['b'] = 2

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

for k in d:
    print (k, d[k])
'''
a 1
c 3
b 2
'''

背景

有时，您需要一个Python字典来记住其项的顺序。在过去，您只有一个工具可以解决这个特定问题：Python 的 OrderedDict。它是一个字典子类，专门设计用于记住项的顺序，由键的插入顺序定义。

这在 Python3.6 中有所改变。内置的 dict 类现在也保持其项目的有序性。因此，Python 社区中的许多人现在怀疑 OrderedDict 是否仍然有用。仔细观察 OrderedDict 将发现该类仍然提供有价值的特性。

Python 的 OrderedDict 是一个 dict 子类，它保留键值对（通常称为项）插入字典的顺序。当您遍历 OrderedDict 对象时，将按原始顺序遍历项目。如果您更新现有键的值，则顺序保持不变。如果您删除一个项目并重新插入它，那么该项目将添加到字典的末尾。作为 dict 子类意味着它继承了常规字典提供的所有方法。

与普通字典的不同

由于内置的 dict 类获得了记住插入顺序的能力（在 Python 3.7 中保证了这种新行为），它们变得不那么重要了。一些与 dict 的不同仍然存在：

常规的 dict 被设计为非常擅长映射操作。跟踪插入顺序是次要的。
OrderedDict 旨在擅长重新排序操作。空间效率、迭代速度和更新操作的性能是次要的。
算法上， OrderedDict 可以比 dict 更好地处理频繁的重新排序操作。这使其适用于跟踪最近的访问（例如在 LRU cache 中）。
对于 OrderedDict ，相等操作检查匹配顺序。
OrderedDict 类的 popitem() 方法有不同的签名。它接受一个可选参数来指定弹出哪个元素。
OrderedDict 类有一个 move_to_end() 方法，可以有效地将元素移动到任一端。
Python 3.8之前， dict 缺少 __reversed__() 方法。

以下是对比：

特性	OrderedDict	dict
Key 插入顺序保持不变	Yes (since Python 3.1)	Yes (since Python 3.6)
项目顺序的可读性和意图信号	High	Low
对项目顺序的控制	High (`.move_to_end()`, 增强 `.popitem()`)	Low (需要移除和重新插入项目)
操作性能	Low	High
内存消耗	High	Low
相等性测试考虑项目的顺序	Yes	No
支持反向迭代	Yes (since Python 3.5)	Yes (since Python 3.8)
附加新实例属性的能力	Yes (`.__dict__` attribute)	No
支持合并 `Ι`和更新`Ι=` 字典运算符	Yes (since Python 3.9)	Yes (since Python 3.9)

操作

创建

创建一个有序字典有多种方式：

from collections import OrderedDict

od = OrderedDict()
od["a"] = 1
od["a"] = 2
od["c"] = 3

od = OrderedDict(a=1, b=2, c=3)
od = OrderedDict([("a", 1), ("b", 2), ("c", 3)])
od = OrderedDict({("a", 1), ("b", 2), ("c", 3)})
od = OrderedDict({"a": 1, "b": 2, "c": 3}) # py 3.6 以上顺序确定

od
# OrderedDict([('one', 1), ('two', 2), ('three', 3)])

OrderedDict 还提供了 .fromkeys() ，它从一组键创建一个新字典，并将其所有值设置为一个公共值：

od = OrderedDict()

od.fromkeys(['a','b','c'])
# OrderedDict([('a', None), ('b', None), ('c', None)])

od.fromkeys(['a','b','c'], 0)
# OrderedDict([('a', 0), ('b', 0), ('c', 0)])

od.fromkeys(['a','b','c'], [0, 1])
# OrderedDict([('a', [0, 1]), ('b', [0, 1]), ('c', [0, 1])])

od.fromkeys(range(3), 0)
# OrderedDict([(0, 0), (1, 0), (2, 0)])

访问

访问的基础的 dict 一样：

od.items()
# odict_items([('a', 1), ('b', 2), ('c', 3)])

od['a']
od.get('a')
od.get('h', 1)
# 1

修改

有两种方法进行修改，一种是使用 update 方法，一种是重新赋值：

od.update(a=0)
od['a'] = 0
od
# OrderedDict([('a', 0), ('b', 2), ('c', 3)])

如果在有序字典中更新给定键的值，则不会移动该键，而是将新值指定给该键。同样，如果使用 .update() 修改现有键-值对的值，则字典会记住键的位置并将更新后的值分配给它。

添加

新添加的项 ('d', 4) 放在基础字典的末尾，因此现有项的顺序不受影响，字典保持插入顺序。

od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od['d'] = 4
od
# OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

删除

可以使用 Python 有关键字 del 对项进行删除：

del od["a"]
od
# OrderedDict([('b', 2), ('c', 3)])

如果删除（'a'，1）项并插入同一项的新实例，则新项将添加到基础字典的末尾。

迭代

就像使用常规词典一样，您可以使用多种工具和技术遍历 OrderedDict 对象。您可以直接遍历键，也可以使用字典方法，例如 .items()、.keys() 和 .values()：

from collections import OrderedDict

od = OrderedDict(a=1, b=2, c=3)

# 直接迭代键 1
for key in od:
    print(key)
'''
a
b
c
'''

# 直接迭代键 2
for key in od:
    print(key, '=>', od[key])
'''
a => 1
b => 2
c => 3
'''

# 使用 .items() 迭代项目
for key, value in od.items():
    print(key, '=>', value)
'''
a => 1
b => 2
c => 3
'''

# 使用 .keys() 迭代键
for key in od.keys():
    print(key, '=>', od[key])
'''
a => 1
b => 2
c => 3
'''

# 使用 .values() 迭代这些值
for value in od.values():
    print(value)
'''
1
2
3
'''

第一个 for 循环直接迭代数字键，其他三个循环使用字典方法对项目、键和数字值进行迭代。

反向迭代

可以使用 reversed() 以相反顺序迭代。OrderedDict 自 Python 3.5 以来提供的另一个重要特性是，它的项、键和值支持使用 reversed() 进行反向迭代。此功能已添加到 Python 3.8 中的常规词典中。因此，如果您的代码使用它，那么您的向后兼容性将受到普通字典的更多限制。

迭代的方法还是和上例的一些迭代方法相同，我们随便举个反向的例子：

# 反向迭代
for key, value in reversed(od.items()):
    print(key, '=>', value)
'''
c => 3
b => 2
a => 1
'''

常规字典也支持反向迭代。但是，如果在低于 3.8 的Python 版本中尝试对常规 dict 对象使用 reversed()，则会出现 TypeError。

OrderedDict 独特的特性

排序控制

这里介绍的两个顺序控制方法是 OrderedDict 独特的特性。自 Python 3.6 以来，常规字典将其项保持在与插入基础字典相同的顺序。这限制了 OrderedDict 的实用性，正如您目前所看到的。然而，OrderedDict 提供了一些在常规 dict 对象中找不到的独特功能。

使用 OrderedDict，您可以访问以下额外和增强的方法：

.move_to_end() 是 Python 3.2 中添加的一个新方法，允许您将现有项移动到字典的末尾或开头。
.popitem() 是其 dict.popitem() 对应方法的增强变体，允许您从基础有序字典的结尾或开头删除并返回项。

OrderedDict 和 dict 在平等性测试中的表现也不同。具体来说，在比较有序字典时，项目的顺序很重要。普通字典并非如此。

最后，OrderedDict实例提供了一个名为 ._dict__ 的属性，在常规字典实例中找不到该属性。此属性允许您将自定义可写属性添加到现有的有序字典中。

重新排序 `.move_to_end()`

dict 和 OrderedDict 之间更显著的区别之一是后者有一个额外的方法，名为 .move_to_end()。此方法允许您将现有项移动到基础词典的末尾或开头，因此它是重新排序词典的一个很好的工具。

使用 .move_to_end() 时，可以提供两个参数：

key 保留标识要移动的项的键。如果密钥不存在，则会出现密钥错误。
last 一个布尔值，该值定义要将手头的项移动到词典的哪一端。它默认为 True，这意味着该项将移动到字典的末尾或右侧。False 表示该项将移动到已排序词典的前面或左侧。

这个操作是就地生效的，会直接修改原变量。例如：

from collections import OrderedDict
od = OrderedDict(a=1, b=2, c=3)

od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od.move_to_end('a') # 移动到尾部
od
# OrderedDict([('b', 2), ('c', 3), ('a', 1)])


od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od.move_to_end('a', last=False) # 移动到开头（不变）
od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])
od.move_to_end('b', last=False) # 移动到开头
od
# eredDict([('b', 2), ('a', 1), ('c', 3)])

可以按键对有序字典进行排序：

from collections import OrderedDict
od = OrderedDict(b=2, d=4, a=1, c=3)
od
# OrderedDict([('b', 2), ('d', 4), ('a', 1), ('c', 3)])
sorted(od)
# ['a', 'b', 'c', 'd']
for key in sorted(od):
    od.move_to_end(key)

od
# OrderedDict([('a', 1), ('b', 2), ('c', 3), ('d', 4)])

如果按值排序呢？

from collections import OrderedDict
od = OrderedDict(b=3, d=1, a=4, c=2)
od
# OrderedDict([('b', 3), ('d', 1), ('a', 4), ('c', 2)])

sorted(od.items(), key=lambda item: item[1])
# [('d', 1), ('c', 2), ('b', 3), ('a', 4)]

for key, _ in sorted(od.items(), key=lambda item: item[1]):
    od.move_to_end(key)

od
# OrderedDict([('d', 1), ('c', 2), ('b', 3), ('a', 4)])

删除项 `.popitem()`

OrderedDict 的另一个有趣特性是其 .popitem() 的增强版。默认情况下，.popitem() 以后进先出的顺序删除并返回项目。换句话说，它从有序字典的右端删除项：

from collections import OrderedDict
od = OrderedDict(a=1, b=2, c=3)

od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])

od.popitem() # ('c', 3)
od
# OrderedDict([('a', 1), ('b', 2)])

如果删无可删，就会报 KeyError: 'dictionary is empty'。如果传入 last=False 则从头开始删：

from collections import OrderedDict
od = OrderedDict(a=1, b=2, c=3)

od
# OrderedDict([('a', 1), ('b', 2), ('c', 3)])

od.popitem(last=False) # ('a', 1)
od
# OrderedDict([('b', 2), ('c', 3)])

因为该 last 参数默认为True，如果将last设置为 False，则 .popitem() 将按 FIFO（First-In/First-Out，先进先出）顺序删除，这意味着它将从字典的开头删除项。

相等性

与 Dict 不同，两个 OrderedDict 对象除了元素内容相同外，还需要顺序相同才，会被认为是两个相等的对象。可见，项的顺序起着重要作用。例如，如果您的有序词典包含相同的项集，则测试结果取决于它们的顺序：

from collections import OrderedDict
od1 = OrderedDict(a=1, b=2, c=3)
od2 = OrderedDict(b=2, a=1, c=3)

od1 == od2
# False

dict1 = dict(a=1, b=2, c=3)
dict2 = dict(b=2, a=1, c=3)

dict1 == dict2
# True

在这里，当您测试两个常规字典的相等性时，如果两个字典具有相同的项集，则为 True。在这种情况下，项目的顺序不会更改最终结果。然而，OrderedDict 对象和常规字典之间的相等性测试不考虑项目的顺序：

od1 = OrderedDict(a=1, b=2, c=3)
dict2 = dict(b=2, a=1, c=3)

od2 == dict2
# True

将有序词典与常规词典进行比较时，项目的顺序并不重要。如果两个词典都有相同的项集，那么它们的比较是相等的，而不管它们的项的顺序如何。

附加新属性 `dict`

OrderedDict 对象具有在常规字典对象中没有的 __dict__ 属性，Python 在内部使用该属性来存储可写实例属性，比如可以使用有序字典的 __dict__ 属性来存储动态创建的可写实例属性，支持字典式赋值（字典式赋值，例如 ordered_dict.__dict__["attr"] = value），使用的时候可以用点去操作（如 ordered_dict.attr = value）。

from collections import OrderedDict
od = OrderedDict(a=1, b=2, c=3)

od.name = '一个有序字典'
od.name
# '一个有序字典'

可以创建动态方法作为实例属性，比如我们实现个将所有值相加的功能：

from collections import OrderedDict
od = OrderedDict(a=1, b=2, c=3)

od.sum = lambda: sum(od.values())
od.sum()
# 6

od['d'] = 4
od.sum()
# 10

vars(od)
# {'sum': <function __main__.<lambda>()>}

现在，已将 .sum() lambda 函数附加到 OrderedDict，可以通过直接使用点操作或使用 vars() 来检查 __dict__ 的内容。这样，实例就开挂了，能够得到非常多的技能扩展，大家可以试试将值无序的 OrderedDict 扩展一个值有序的 OrderedDict。

合并及更新

Python3.9 向字典空间添加了两个新操作符。现在有了合并（|）和更新（|=）字典操作符，这些操作符还处理 OrderedDict 实例：

from collections import OrderedDict

od1 = OrderedDict(a=1, b=2)
od2 = OrderedDict(a=3, c=4)

od1 | od2
# OrderedDict([('a', 3), ('b', 2), ('c', 4)])

od1 |= od2
od1
# OrderedDict([('a', 3), ('b', 2), ('c', 4)])
od2
# OrderedDict([('a', 3), ('c', 4)])

合并（merge）操作符将两个字典合并为一个新字典，其中包含两个初始字典的项。如果表达式中的字典具有公用键，则以最右边字典的值为准。当您有一个字典并且希望在不调用 .update() 的情况下更新它的一些值时，更新（|=）操作符非常方便。

上例中，使用字典更新操作符更新 a 的值，操作将就地（in place）更新词典，对左边的变量值进行修改。如果提供更新数据的字典具有新的键，则这些键将添加到原始字典的末尾。

性能问题

性能是编程中的一个重要课题。了解算法的运行速度或使用的内存量是常见的问题。OrderedDict 最初是用 Python 编写的，然后用 C 编写，以最大限度地提高其方法和操作的效率。这两种实现目前在标准库中可用。但是，如果由于某种原因 C 实现不可用，Python 实现可以作为替代方案。

OrderedDict 的两种实现都涉及使用双链接列表来捕获项目的顺序。尽管某些操作具有线性时间，但 OrderedDict 中的链表实现进行了高度优化，以保持相应字典方法的快速时间。也就是说，有序字典上的运算是 O(1)，但与常规字典相比，常数因子更大。

一般来说，OrderedDict 的性能低于常规词典。

原理

实际 OrderedDict 内部维护了一个双向链表，他会根据元素加入的顺序来排列键的位置，第一个新加入的元素被放置在链表的末尾，对已存在的键做重新赋值，不会改变键的顺序，所以 OrderedDict 的大小是普通字典的 2 倍多，大数据使用时要考虑实际的额外开销。

多年来，Python 字典都是无序的数据结构。Python 开发人员已经习惯了这一事实，当他们需要保持数据有序时，他们依赖列表或其他序列。随着时间的推移，开发人员发现需要一种新类型的字典，一种能够保持其条目有序的字典。

早在 2008 年，PEP372 就提出了在集合中添加一个新字典类的想法。它的主要目标是记住由插入键的顺序定义的项的顺序。这就是有序信息技术的起源。

核心 Python 开发人员希望填补这一空白，并提供一个能够保留插入键顺序的字典。这反过来又允许更直接地实现依赖于此属性的特定算法。

OrderedDict 被添加到 Python 3.1 中的标准库中。它的 API 本质上与 dict 相同。但是，OrderedDict 按照插入键的相同顺序对键和值进行迭代。如果新条目覆盖现有条目，则项目顺序保持不变。如果一个条目被删除并重新插入，那么它将被移动到字典的末尾。

Python 3.6 引入了 dict 的一个新实现。这个新实现在内存使用和迭代效率方面代表了一个巨大的胜利。此外，新的实现提供了一个新的、有些出乎意料的特性：dict 对象现在将其项保持在与引入时相同的顺序。最初，这个特性被认为是一个实现细节，官方文档建议不要依赖它。

用核心 Python 开发人员和 OrderedDict 的合作开发者 Raymond Hettinger 的话说，该类是专门为保持其项目的有序而设计的，而 dict 的新实现是为紧凑和提供快速迭代而设计的：

目前的常则字典是基于我几年前提出的设计。该设计的主要目标是在密集的键和值数组上实现紧凑性和更快的迭代。维持秩序是一种人工制品，而不是设计目标。设计可以维持秩序，但这不是它的专长。
相比之下，我给 collections.OrderedDict 一个不同的设计（后来由 Eric Snow 用 C 编码）。主要目标是即使对于严重的工作负载也能有效维护顺序，例如由 LRU缓存强加的，它经常改变顺序而不触及底层 dict。有意地，OrderedDict 的设计以额外的内存开销和更糟糕的插入时间为代价，优先考虑排序功能。
我的目标仍然是拥有 collections.OrderedDict 与常规 dicts 具有不同性能特征的不同设计。它有一些常规 dict 没有的特定于顺序的方法（例如 move_to_end() 和 popitem() 从任一端有效弹出）。 OrderedDict 需要擅长这些操作，因为这是它与常规 dicts 的区别。

在 Python 3.7 中，dict 对象的项目排序功能被宣布为 Python 语言规范的正式部分。因此，从那时起，当开发人员需要一个保持项目有序的字典时，他们可以依赖 dict。

这时候就产生了一个问题：在 dict 的这个新实现之后，还需要 OrderedDict 吗？答案取决于您的特定用例以及您希望在代码中的明确程度。

在编码时，OrderedDict 的某些功能仍然使其有价值且与常规 dict 不同：

意图信号：如果您在 dict 上使用 OrderedDict，那么您的代码会清楚地表明字典中项目的顺序很重要。您清楚地传达了您的代码需要或依赖于底层字典中项目的顺序。
控制项目的顺序：如果您需要重新排列或重新排列字典中的项目，那么您可以使用 .move_to_end() 以及 .popitem() 的增强变体。
相等测试行为：如果您的代码比较字典是否相等，并且项目的顺序在该比较中很重要，那么 OrderedDict 是正确的选择。

至少还有一个理由在你的代码中继续使用 OrderedDict：向后兼容性。依靠常规的 dict 对象来保留项目的顺序会在运行 Python 3.6 之前版本的环境中破坏您的代码。

很难说 dict 是否会很快完全取代 OrderedDict。如今，OrderedDict 仍然提供有趣且有价值的功能，您在为给定工作选择工具时可能需要考虑这些功能。

案例：构建基于字典的队列

当您需要实现基于字典的队列时，应该考虑使用 OrderedDict 对象而不是 dict 对象的用例。队列是以 FIFO（先进先出）方式管理其项的常见且有用的数据结构。这意味着您在队列末尾推入新项目，而旧项目则从队列开头弹出。

通常，队列实现一个将项目添加到其末端的操作，称为排队操作。队列还实现了一个从项目开始移除项目的操作，称为出列操作。要创建基于字典的队列，请启动代码编辑器或 IDE，创建一个名为 queue.py 的新Python模块，并向其中添加以下代码：

# queue.py

from collections import OrderedDict

class Queue:
    def __init__(self, initial_data=None, /, **kwargs):
        self.data = OrderedDict()
        if initial_data is not None:
            self.data.update(initial_data)
        if kwargs:
            self.data.update(kwargs)

    def enqueue(self, item):
        key, value = item
        if key in self.data:
            self.data.move_to_end(key)
        self.data[key] = value

    def dequeue(self):
        try:
            return self.data.popitem(last=False)
        except KeyError:
            print("Empty queue")

    def __len__(self):
        return len(self.data)

    def __repr__(self):
        return f"Queue({self.data.items()})"

在 Queue 中，您首先初始化一个名为 .data 的实例属性。此属性包含一个空的有序字典，您将使用它来存储数据。类初始值设定项采用第一个可选参数 initial_data，它允许您在实例化类时提供初始数据。初始值设定项还采用可选的关键字参数 (kwargs) 以允许您在构造函数中使用关键字参数。

然后您编写 .enqueue() 代码，它允许您将键值对添加到队列中。在这种情况下，如果键已经存在，则使用 .move_to_end() ，并且对新键使用正常分配。请注意，要使此方法起作用，您需要提供具有有效键值对的两项元组或列表。

.dequeue() 实现使用 last 设置为 False 的 .popitem() 从底层有序字典 .data 的开头删除和返回项目。在这种情况下，您使用 try ... except 块来处理在空字典上调用 .popitem() 时发生的 KeyError。

特殊方法 .__len__() 提供了检索内部有序字典 .data 长度所需的功能。最后，当您将数据结构打印到屏幕时，特殊方法 .__repr__() 提供了一个用户友好的队列字符串表示。

以下是如何使用队列的一些示例：

>>> from queue import Queue

>>> # 创建一个空队列
>>> empty_queue = Queue()
>>> empty_queue
Queue(odict_items([]))

>>> # 使用初始数据创建队列
>>> numbers_queue = Queue([("one", 1), ("two", 2)])
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2)]))

>>> # 使用关键字参数创建队列
>>> letters_queue = Queue(a=1, b=2, c=3)
>>> letters_queue
Queue(odict_items([('a', 1), ('b', 2), ('c', 3)]))

>>> # 添加项
>>> numbers_queue.enqueue(("three", 3))
>>> numbers_queue
Queue(odict_items([('one', 1), ('two', 2), ('three', 3)]))

>>> # 删除项
>>> numbers_queue.dequeue()
('one', 1)
>>> numbers_queue.dequeue()
('two', 2)
>>> numbers_queue.dequeue()
('three', 3)
>>> numbers_queue.dequeue()
Empty queue

在此代码示例中，您首先使用不同的方法创建三个不同的 Queue 对象。然后使用 .enqueue() 将单个项目添加到 numbers_queue 的末尾。最后，您多次调用 .dequeue() 以删除 numbers_queue 中的所有项目。请注意，对 .dequeue() 的最终调用会在屏幕上打印一条消息，通知您队列已为空。

参考

https://docs.python.org/zh-cn/3/library/collections.html#collections.OrderedDict
https://mail.python.org/pipermail/python-dev/2017-December/151266.html
https://realpython.com/python-ordereddict/