有什么理由不使用OrderedDict？

Question

我指的是模块中的OrderedDictcollections，这是一个有序的字典。

如果它具有可订购的附加功能，我意识到这通常不是必需的，但是即使如此，是否还有缺点？慢一点吗？是否缺少任何功能？我没有看到任何丢失的方法。

简而言之，为什么我 不 总是使用它而不是普通的词典？

Answer 1

OrderedDict是的子类dict，并且需要更多内存来跟踪键的添加顺序。这不是小事。该实现dict在幕后增加了第二个，所有键的双向链接列表（这是记住顺序的部分），以及一堆weakref代理。它并没有慢
很多 ，但至少比使用plain的内存多了一倍dict。

但是，如果合适，请使用它！这就是为什么它在那里:-)

这个怎么运作

基本dict只是将键映射到值的普通dict-根本不是“有序的”。<key, value>添加一对后，key会附加到列表中。列表是记住订单的部分。

但是，如果这是Python列表，则 删除 密钥将花费O(n)两倍的时间：
O(n)在列表中找到密钥的O(n)时间，以及从列表中删除密钥的时间。

因此，它是一个双向链接列表。这使得删除键的O(1)时间为常数（）。但是我们仍然需要找到属于该键的双向链接列表节点。为了节省操作O(1)时间，第二个-
隐藏的dict将键映射到双向链接列表中的节点。

因此，添加新<key, value>对需要将对添加到基本字典，创建一个新的双向链接列表节点来保存密钥，将该新节点附加到双向链接列表中，并将密钥映射到隐藏字典中的该新节点。工作量是原来的两倍多，但O(1)总体上还是（预期的情况）。

同样，删除存在的密钥也要花两倍的O(1)时间，但总的来说是预期的时间：使用隐藏的字典来查找密钥的双向链接列表节点，从列表中删除该节点，然后从两个字典中删除密钥。

等等，这非常有效。