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

Question

OrderedDict在Python中如何记住元素的所有顺序？性能开销是多少？对于诸如实现之类的问题LRU，我发现它确实非常强大且易于实现，但是这里的性能提升是多少？如何记住最初插入的键的顺序？

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

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