OrderedDict 是一棵树吗？

Question

OrderedDict 是一个保留项目顺序的集合（它们被插入其中）。我不认为这可以通过哈希表（我认为常规字典使用）来实现，那么平衡树是否用于实现它？

我假设有很多依赖项，例如 Python 2/3 和 CPython/IPython/others。

Answer 1

您可以阅读 CPython 源代码中的实现：Lib/collections/__init__.py 因为 OrderedDict 在 Python 中实现。

它使用一个doubly linked list来维护字典中元素的顺序。