146. LRU 缓存

题目链接：146. LRU 缓存

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量实例化 LRU 缓存。
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

核心思考：哈希表配合双向链表 (OrderedDict)

LRU 缓存机制的实现，必须兼顾以下要求：查找具备 $O(1)$ 的速度，元素的调整插入和驱逐同样也要达到 $O(1)$。这就确定了我们需要两种基本组合：

1. 哈希表：用于快速定位映射查找键值位置。
2. 双向链表：用于在头部获取到记录后将目标节点解绑后无延时移入近期队列端，或在容量超限时及时删除并释放尾部目标。

在 Python 编程实现中，通常最为方便和推荐的是利用内置的 collections.OrderedDict 模块。它底层正好对应就是“有序字典”（哈希表与双向链表结合结构）的完整工业实现。

• get(key)：访问命中后，使用 self.cache.move_to_end(key, last=False) 将刚被唤醒阅读的数据迁移至活跃前端保护区。
• put(key, value)：装载或者更新重载入字典内时，利用 move_to_end() 置前。超容时直接切断末尾对象应用 popitem() 操作删除。

解题思路 (Python)

class LRUCache:
    from collections import OrderedDict
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache.keys():
            return -1
        self.cache.move_to_end(key, last = False)
        return self.cache[key]

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


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

复杂度分析

• 时间复杂度：无论是向体系内发起读取请求或是新载量覆写填充，$O(1)$ 可以完全恒定。这得利于集合内部对于常数化数据增改指向引用的直接偏移支持。
• 空间复杂度：$O(C)$，对于预置最大规模量体上限指标 capacity 也就是 C 进行容错预定。最满不超出约束内存槽限制。