LRU 缓存算法
哈希表 + 双向链表
以 LeetCode 上的 LRU 缓存问题为例，核心需求是支持 get 和 put 操作，且时间复杂度需达到 O(1)。这通常通过组合哈希表和双向链表来实现。
设计思路
双向链表负责维护节点的访问顺序：最近使用的节点放在头部，最少使用的在尾部。当容量满时，直接删除尾部节点即可。哈希表则用于存储 key 到节点的映射，解决链表遍历查找慢的问题，确保 O(1) 的查找速度。
为了简化边界处理，通常会引入哑头（head）和哑尾（tail）节点。这样在插入或删除首尾节点时，无需判断链表是否为空或是否只有一个节点，逻辑更加统一。
核心规则很简单：
- 访问/更新：将节点移到链表头部，标记为'最近使用'。
- 新增：添加到头部，若超过容量，删除尾部节点并同步清理哈希表。
代码实现
class LRUCache {
// 双向链表节点类：封装缓存的 key、value，以及前后指针
class DLinkedNode {
int key; // 缓存键（淘汰节点时需要通过 key 删除哈希表中的映射）
int value; // 缓存值
DLinkedNode prev; // 前驱节点（双向链表）
DLinkedNode next; // 后继节点（双向链表）
// 无参构造：用于创建哑头/哑尾节点（无实际 key/value）
public DLinkedNode() {}
// 有参构造：用于创建真实的缓存节点（初始化 key 和 value）
public DLinkedNode(int _key, int _value) {
this.key = _key;
this.value = _value;
}
}
// 哈希表：key -> 节点（O(1) 查找）
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size; // 当前缓存中的节点数量
private int capacity; // 缓存的最大容量
DLinkedNode head;
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;
}
}
