OrderedDict：有序写查删

先后序字典

我这里选择不叫“有序字典“，因为“序“可能会产生的歧义。与此先后序区分的是自然顺序（或叫秩rank），比如SortedDict元素的排序是元素的自然顺序。

OrderedDict实现的结构是哈希链表LinkedHashmap，然而重要的部分是双向链表，它是保证快速有序写查删的关键，哈希表的部分只是链表中节点的索引（以key access）。

图片来源：https://krishankantsinghal.medium.com/

之前我们看了如何用哈希表保存了键值对，我们能用近乎O(1)的时间找到给定key对应的值。然而我们没有键的先后顺序，没办法找到firstKey的值，也办法像栈一样压入一个新的键值对。

这个时候我们就像用某种能够记住“先后次序“的数据结构来存储key对应的值。如果只需增删最新或最旧的键，那用栈、队列、单向链表都可以做到。

如果需要支持任意元素的删除或更新呢？它有可能在数据中的任意位置。还记得吗，除了像单向链表一样能够在O(1)时间里写查删头尾节点，双向链表能帮我们在O(1)时间删除任意一个节点，并保持链表原来的顺序。如果需要的话，还可以在O(1)时间把它放到开头或者末尾。

经典的应用：

• LRU缓存

• 数据流中的滑动窗口

哈希链表实现

下面是哈希链表LinkedHashMap用双向链表DDL(实现见顺序结构章节)的简单实现，另附直接调用OrderedDict实现。

主要功能：

• put(key, value)：O(1)更新一个键，并把它放在链表头部 实现：DDL中删除一个键，并在头部插入新的键值对

• get(key)：O(1)得到一个键值对，并把它放在链表头部 实现：DDL中查找一个键值对，并调用put(key, value)

哈希表 + 双向链表

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hash = defaultdict(ListNode)
        self.cache = DoubleLinkedList()

    def get(self, key: int) -> int:
        if key not in self.hash:
            return -1
        node = self.hash[key]
        self.put(key, node.val)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.hash:
            self.cache.remove(self.hash[key])
        else:
            if len(self.hash)==self.capacity:
                last = self.cache.removeLast()
                del self.hash[last.key]

        node = ListNode(key, value)
        self.cache.insertFront(node)
        self.hash[key] = node

OrderedDict实现

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hash = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.hash:
            return -1
        self.put(key, self.hash[key])
        return self.hash[key]

    def put(self, key: int, value: int) -> None:
        if key in self.hash:
            del self.hash[key]
        self.hash[key] = value
        if len(self.hash)>self.capacity:
            self.hash.popitem(last=False)