缓存算法实战：LRU 与 LFU 原理及 Java 实现
在系统设计和面试中，缓存淘汰策略是高频考点。常见的 LRU（最近最少使用）和 LFU（最不经常使用）算法，核心在于如何在有限空间内平衡访问速度与淘汰效率。下面结合 Java 代码，深入剖析这两种算法的实现细节。
一、LRU 缓存算法
1. 核心思路
LRU 的核心需求是支持 O(1) 时间的查找和更新。单纯链表查找慢，单纯哈希表无法维护顺序。因此采用 哈希表 + 双向链表 的组合：
- 哈希表：存储 key 到节点的映射，实现 O(1) 快速定位。
- 双向链表：维护节点的使用顺序。最近使用的节点移到头部，最久未使用的在尾部，淘汰时直接删尾。
- 哑节点：引入头尾哨兵节点，简化边界判断（如空表或单节点情况）。
2. 代码实现
class LRUCache {
// 双向链表节点类
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;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
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 = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
{
node.prev.next = node.next;
node.next.prev = node.prev;
}
{
removeNode(node);
addToHead(node);
}
DLinkedNode {
tail.prev;
removeNode(res);
res;
}
}
