LRU 缓存算法
1. 哈希表 + 双向链表
LRU（Least Recently Used）的核心在于维护一个访问顺序，确保最近使用的数据保留在缓存中。实现这一目标的最佳组合是哈希表加双向链表。
核心设计思路：
- 双向链表：用于维护节点的访问顺序。最近使用的节点放在头部，最少使用的节点在尾部。淘汰时直接删除尾部节点。
- 哈希表：存储 key 到链表节点的映射，实现 O(1) 时间复杂度的查找，避免遍历链表。
- 哑头/哑尾节点：简化边界处理，无需判断链表是否为空或节点是否为头尾。
关键规则：
- 访问或更新节点时，将其移到链表头部。
- 新增节点时添加到头部，若超过容量则删除尾部节点并同步清理哈希表。
class LRUCache {
// 双向链表节点类：封装缓存的 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;
}
}
// 核心成员变量
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head;
private DLinkedNode tail;
// 构造方法：初始化 LRU 缓存
public LRUCache(int capacity) {
this.size = 0;
this.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;
}
}
