OrderedDict是否是一棵树？

Question

7

OrderedDict是一种保持项目顺序（即它们插入的顺序）的集合。我认为哈希表不能实现这个功能（我认为普通字典使用哈希表），因此平衡树用于实现它吗？

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

- ArekBulski

是的，在线上有很多关于Python的文档资料。 - Untitled123

我发现很多关于普通字典是哈希表的问题，但没有关于有序字典的。 - ArekBulski

1

可以通过哈希表与有序列表（如链表）相结合来实现。 - khelwood

虽然不完全是重复的问题，但被接受的答案（来自其中一位核心开发者）解释了一些关于CPython中它是如何实现的。 - jonrsharpe

@jonrsharpe 不仅是任何核心开发人员，而是编写Timsort的那个家伙！ - John Red

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Simeon Visser · Accepted Answer

你可以在CPython源代码中阅读实现: Lib/collections/__init__.py，因为OrderedDict是用Python实现的。

它使用一个双向链表来维护字典中元素的顺序。