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

Question

我该如何在Python中使用OrderedDict来记住元素的顺序？它会对性能造成多大的影响？对于像实现LRU这样的问题，我发现它非常强大且易于实现，但是这里有什么性能优势？它是如何记住首次插入的键的顺序的？

它是否使用类似下面图片所示的Dict()和Double Linked List来记住键的顺序？如果您能用简单的语言传达信息，而不是分享某种研究论文，我将不胜感激。

- python

Answer 1

最好的事情是，你可以查看OrderedDict的源代码来更好地理解它。

实际上，它是用纯Python实现的！这意味着你可以复制它，重新定义它，甚至无节制地变异它，直到你理解为止。

它确实使用了双向链表，这在源文件的docstring中有说明。通过理解双向 链表的工作原理并浏览源代码，你将会对它的工作方式有很好的掌握：

# 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].

- Dimitris Fasarakis Hilliard

---

谢谢，这确实非常有帮助。 - python

你能详细说明一下最后三行关于“哨兵元素”的内容吗？ - python

哨兵节点本质上是虚拟节点，用于标记链表的开头和结尾，以优化链表操作。有很多关于它们的资源[1, 2, 3]，这更多是理论方面的内容。最后一个只是指示每个节点的内容应该是什么。 - Dimitris Fasarakis Hilliard