有没有任何不使用OrderedDict的理由？

Question

我指的是来自collections模块的OrderedDict，它是一个有序字典。

如果它具有可排序的附加功能，我意识到这可能经常不必要，但即使如此，它是否存在任何缺点？它是否更慢？它是否缺少任何功能？我没有看到任何缺失的方法。

简而言之，为什么我不应该总是使用它而不是普通字典？

- temporary_user_name

---

此外，许多软件包返回字典，与有序字典一起使用可能会混乱顺序。 - sashkello

为什么要使用有序字典？你为什么需要一个有序的字典？ - TerryA

@Haidro，这是标准库中的一个示例。链接 - fjarri

如果你使用OrderedDict的唯一目的是为了格式化输出（假定排序键），只需使用for key in sorted(dictvar): print (key, dictvar[key])。OrderedDict保留插入的顺序，而不是键的顺序。 - PaulMcG

@Wooble：请将答案发布为答案，而不是评论。 - Ethan Furman

Answer 1

OrderedDict是dict的一个子类，需要更多的内存来跟踪添加键的顺序。这不是微不足道的。实现在底层添加了第二个dict，以及所有键的双向链表(记住顺序的部分)，和一堆弱引用代理。它并不慢很多，但至少比使用普通的dict增加了一倍的内存。

但如果适当的话，请使用它！这就是为什么它存在的原因:-)

工作原理

基本字典只是将键映射到值的普通字典，根本不是"有序"的。当添加一对<key, value>时，key被追加到列表中。列表是记住顺序的部分。

但是，如果这是一个Python列表，删除键将重复O(n)次：在列表中查找键需要O(n)时间，从列表中删除键也需要O(n)时间。

所以它是一个双向链接列表。这使得删除一个键成为常数(O(1))时间。但是我们仍然需要找到属于键的双向链接列表节点。要使该操作的时间复杂度也为O(1)，第二个-隐藏的-字典将键映射到双向链接列表中的节点。

因此，添加一个新的<key, value>对需要将该对添加到基本字典中，创建一个新的双向链接列表节点来保存键，将该新节点附加到双向链接列表中，并将键映射到该新节点中的隐藏字典中。它是比普通的dict多了一点工作量，但总体上仍然是O(1)（预期情况下）的时间复杂度。

同样地，删除已存在的键也需要做两倍左右的工作，但总体上期望时间仅为O(1)：使用隐藏的字典来查找键的双向链表节点，从链表中删除该节点，并从两个字典中删除该键。

等等，这非常高效。

- Tim Peters

---

@GrijeshChauhan，我读了源代码 - 我是一名核心Python开发者，所以这就是我回答大多数问题的方式 - 哈哈；-) 您可以在Python源代码树中的 Lib/collections/__init__.py 中找到该代码。 - Tim Peters

等一下...你就是写TimSort的那个人！！！没想到你降临凡间，回答了我的微不足道的问题。谢谢！ - temporary_user_name

LOL！非常欢迎，@Aerovistae-这是一个值得提问的问题;-) - Tim Peters

我发现当我告诉人们“你可以在你的Python源代码树中找到代码”时，他们从不查看，但当我链接到hg存储库时，有时他们会查看。（通常只有当阅读源代码引发比我更深奥的问题时才会这样做。） - abarnert

请打开你的Python解释器，在命令行中输入import this，然后按回车键。编写这个程序的人就是回答这个问题的人。 - Games Brainiac

Answer 2

自从Python 3.7版本开始，所有的字典都是有序的。Python的贡献者们认为将dict变为有序不会对性能产生负面影响。我不知道在Python >= 3.7中OrderedDict的性能如何与dict相比较，但我想它们应该是可以相互比较的，因为它们都是有序的。

请注意，OrderedDict和dict之间仍然存在行为差异。详情请参见: Will OrderedDict become redundant in Python 3.7?

- Flimm

Answer 3

多线程

如果您的字典在没有锁定的情况下从多个线程访问，特别是作为同步点。

原始字典操作是原子操作的，而Python中扩展的任何类型都不是。

事实上，我甚至不能确定OrderedDict是否是线程安全的（没有锁定），尽管我不能排除它非常小心地编码并满足可重入性的定义的可能性。

小恶魔

如果您创建了大量这些字典，则会增加内存使用量。

如果您的所有代码都是修改这些字典，那么会增加CPU使用率。

- Dima Tisnek

Answer 4

为什么我不能一直使用这个而不是普通的字典

在Python 2.7中，正常的OrderedDict用法会创建引用循环。因此，任何使用OrderedDict都需要启用垃圾回收器以释放内存。是的，在cPython中，默认情况下启用了垃圾回收器，但是禁用它也有其用处。

例如，使用cPython 2.7.14

from __future__ import print_function

import collections
import gc

if __name__ == '__main__':
    d = collections.OrderedDict([('key', 'val')])
    gc.collect()
    del d
    gc.set_debug(gc.DEBUG_LEAK)
    gc.collect()
    for i, obj in enumerate(gc.garbage):
        print(i, obj)

输出

gc: collectable <list 00000000033E7908>
gc: collectable <list 000000000331EC88>
0 [[[...], [...], 'key'], [[...], [...], 'key'], None]
1 [[[...], [...], None], [[...], [...], None], 'key']

即使您只创建一个空的OrderedDict（d = collections.OrderedDict()）并且没有添加任何内容，或者您明确尝试通过调用clear方法（在del d之前d.clear()）来清除它，您仍将获得一个自引用列表：

gc: collectable <list 0000000003ABBA08>
0 [[...], [...], None]

自从这个提交移除了__del__方法以防止OrderedDict引起不可回收循环，这似乎一直是这种情况。正如该提交的更改日志中所述：

问题＃9825：从collections.OrderedDict的定义中删除了__del__。 这可以防止用户创建的自引用有序字典变为永久无法回收的GC垃圾。缺点是 移除__del__意味着内部双向链接列表必须等待GC收集，而不是在refcnt降至零时立即释放内存。

---

请注意，在Python 3中，同样的问题fix的处理方式有所不同，使用了弱引用代理来避免循环引用：

问题＃9825：在collections.OrderedDict的定义中使用__del__使得用户可以创建自引用的有序字典，这些字典成为永久无法收集的垃圾。重新采用Py3.1的方法，使用弱引用代理，以便首先不会创建引用循环。

- Day