你如何设计一个具有 O(1) get 和 put 的 LRU 缓存？

Question

Accepted Answer

**LRU (Least Recently Used) 缓存**在达到容量时会驱逐最长时间未被访问的项。经典设计将**哈希映射**（O(1) 查找）与**双向链表**（O(1) 重新排序）结合起来，提供 **O(1) get 和 put**。 ## 两个结构的设计 ```text HashMap: key -> node DLL (recency order): MRU <-> ... <-> LRU get/put: map finds node move touched node to front (MRU) in O(1); DLL splices it evict the tail (LRU) when full to the front in O(1) ``` ## Code ```python from collections import OrderedDict class LRUCache: def __init__(self, capacity): self.cap = capacity self.cache = OrderedDict() # preserves access order def get(self, key): # O(1) if key not in self.cache: return -1 self.cache.move_to_end(key) # mark as most recently used return self.cache[key] def put(self, key, value): # O(1) if key in self.cache: self.cache.move_to_end(key) self.cache[key] = value if len(self.cache) > self.cap: self.cache.popitem(last=False) # evict least recently used ``` `OrderedDict` 本身就是哈希映射加双向链表，正好是上述描述的结构。 | Operation | Time | |---|---| | get | O(1) | | put | O(1) | | space | O(capacity) | ## 为什么使用双向链表双向链表让你能够**在 O(1) 时间内从中间分离一个节点**（你持有它的 `prev`/`next`），而对于单向链表或数组来说，这在没有 O(n) 移位的情况下是不可能的。 ## 为什么这很重要 LRU 缓存位于数据库、Web 服务器和 CPU 前面，用于保持热数据快速访问并限制内存使用。这个问题是高级面试的常见题目，因为它测试了如何结合两个数据结构，使得*彼此的弱点都被弥补* — 这是关键的系统设计技能。