缓存淘汰算法里,LRU(Least Recently Used)是最常被要求手写的一个。它的难点不在思路,而在于同时满足 O(1) 的查找与 O(1) 的淘汰。单独用任何一种数据结构都做不到。
为什么需要两种结构#
如果用数组存 key,查找是 O(1) 的,但每次访问都要把元素挪到末尾,移动是 O(n)。如果用链表,移动到头部是 O(1),但查找必须遍历,也是 O(n)。
把「查找」和「顺序维护」拆给两个结构:哈希表存 key → 节点指针,链表维护冷热顺序。这就是 LRU 的全部秘密。
结构设计#
用一个带哨兵头尾的双向链表,头部是最近访问,尾部是最久未访问。哈希表的 value 直接指向链表节点,因此删除节点不需要遍历。
| 操作 | 数据结构 | 复杂度 |
|---|---|---|
| 查找 key | dict | O(1) |
| 移到头部 | 双向链表 | O(1) |
| 淘汰尾部 | 双向链表 + dict | O(1) |
参考实现#
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key=0, val=0):
self.key, self.val = key, val
self.prev = self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {}
self.head = Node() # 哨兵:最近使用
self.tail = Node() # 哨兵:最久未用
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, node):
node.prev.next, node.next.prev = node.next, node.prev
def _push_front(self, node):
node.next, node.prev = self.head.next, self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
if key not in self.map:
return -1
node = self.map[key]
self._unlink(node)
self._push_front(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.map:
node = self.map[key]
node.val = value
self._unlink(node)
self._push_front(node)
return
if len(self.map) == self.cap:
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
node = Node(key, value)
self.map[key] = node
self._push_front(node)
三个容易踩的坑#
- 删除 dict 条目时要用节点里存的 key,而不是外部传入的 key,否则淘汰逻辑会错位。
- 哨兵节点能让边界判断消失,强烈建议加,代码可读性提升明显。
- Python 3.7+ 的 dict 虽然有序,但那是插入顺序,不是访问顺序,不能直接当 LRU 用。
小结#
LRU 是「用空间换常数」的典型:多存一份指针,换来所有操作都是 O(1)。真正写的时候,把哨兵和摘链/头插两个基础操作封装好,主流程就只有几行。