Python的OrderedDict如何记住插入的元素？

Question

在Python中，OrderedDict是怎么记住所有元素的顺序的呢？它的性能开销大吗？比如在实现LRU（最近最少使用）这种问题时，我发现它非常强大，而且实现起来也很简单，但它在性能上有什么好处呢？它是怎么记住最先插入的键的顺序的呢？

它是用一个Dict()和一个双向链表来记住这些键的吗？如果你能用简单的语言来解释一下，而不是分享一些研究论文那就太好了。

相关文章：

• 暂无相关问题

Answer 1

这段内容最棒的地方在于，你可以查看OrderedDict的源代码，来更好地理解它。

其实它也是用纯Python实现的！这意味着你可以随意复制、重新定义，甚至疯狂地修改它，直到你完全理解为止。

它使用了双向链表，这个在源文件的文档字符串中有说明。了解双向链表是怎么工作的，再加上浏览源代码，你就能很好地掌握它的具体工作原理：

# An inherited dict maps keys to values.
# The inherited dict provides __getitem__, __len__, __contains__, and get.
# The remaining methods are order-aware.
# Big-O running times for all methods are the same as regular dictionaries.

# The internal self.__map dict maps keys to links in a doubly linked list.
# The circular doubly linked list starts and ends with a sentinel element.
# The sentinel element never gets deleted (this simplifies the algorithm).
# Each link is stored as a list of length three:  [PREV, NEXT, KEY].