LRU (Least Recently Used) 缓存在达到容量时会驱逐最长时间未被访问的项。经典设计将哈希映射（O(1) 查找）与双向链表（O(1) 重新排序）结合起来，提供 O(1) get 和 put。
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)
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 前面，用于保持热数据快速访问并限制内存使用。
这个问题是高级面试的常见题目，因为它测试了如何结合两个数据结构，使得彼此的弱点都被弥补 — 这是关键的系统设计技能。
一个包含详细解答的 IT 面试题库——从初级到高级。
捐赠