一、LRU 缓存算法
1. 哈希表 + 双向链表
在系统设计和面试中，LRU（Least Recently Used）是最经典的缓存淘汰策略。它的核心需求是：当缓存满时，淘汰掉最近最少使用的数据；同时保证 get 和 put 操作的时间复杂度尽可能低。
算法思路
要实现高效的 LRU，单纯用链表查找太慢，单纯用哈希表无法维护顺序。最佳方案是组合使用：哈希表 + 双向链表。
- 双向链表：维护节点的访问顺序。最近使用的节点放在头部，最少使用的在尾部。淘汰时直接删尾部，插入时加头部。
- 哈希表：存储 key 到链表节点的映射，实现 O(1) 快速查找，避免遍历链表。
- 哑头/哑尾节点：这是工程上的小技巧。通过哨兵节点简化边界处理，比如不需要判断'链表是否为空'或'是否插到了头尾'，逻辑会更统一。
代码实现
下面是一个标准的 Java 实现，重点在于辅助方法的设计，它们保证了所有操作都在常数时间内完成。
class LRUCache {
// 1. 双向链表节点类：封装缓存的 key、value，以及前后指针
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
// 无参构造：用于创建哑头/哑尾节点
public DLinkedNode() {}
// 有参构造：用于创建真实的缓存节点
public DLinkedNode(int _key, int _value) {
this.key = _key;
this.value = _value;
}
}
// 2. LRUCache 核心成员变量
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size; // 当前缓存中的节点数量
private int capacity; // 缓存的最大容量
private DLinkedNode head; // 链表哑头节点
private DLinkedNode tail; // 链表哑尾节点
{
.size = ;
.capacity = capacity;
head = ();
tail = ();
head.next = tail;
tail.prev = head;
}
{
cache.get(key);
(node == ) {
-;
}
moveToHead(node);
node.value;
}
{
cache.get(key);
(node == ) {
(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
(size > capacity) {
removeTail();
cache.remove(tailNode.key);
size--;
}
} {
node.value = value;
moveToHead(node);
}
}
{
node.prev.next = node.next;
node.next.prev = node.prev;
}
{
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
{
removeNode(node);
addToHead(node);
}
DLinkedNode {
tail.prev;
removeNode(res);
res;
}
}
