深入理解 LRU 与 LFU 缓存算法实现
在系统设计和面试中，缓存淘汰策略是高频考点。LRU（最近最少使用）和 LFU（最不经常使用）代表了两种不同的淘汰逻辑，掌握它们的底层实现原理，对于应对高并发架构挑战至关重要。
一、LRU 缓存算法
1. 哈希表 + 双向链表
以 LeetCode 的 LRU Cache 题目为例，核心需求是在 O(1) 时间复杂度内完成 get 和 put 操作。
设计思路
单纯用哈希表无法维护访问顺序，单纯用链表查找效率太低。因此我们采用组合方案：
- 双向链表：维护节点的访问顺序。最近使用的节点放在头部，最少使用的节点放在尾部。淘汰时直接删除尾部节点。
- 哈希表：存储 key 到链表节点的映射，实现 O(1) 快速查找。
- 哑头/哑尾节点：简化边界处理，无需判断链表是否为空或节点是否为头尾。
代码实现
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; // 链表哑尾节点
// 3. 构造方法：初始化 LRU 缓存
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
// 4. get 操作：根据 key 获取缓存值
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 存在则移到链表头部，标记为'最近使用'
moveToHead(node);
return node.value;
}
// 5. put 操作：添加/更新缓存
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 情况 1：key 不存在，新增节点
DLinkedNode newNode = new DLinkedNode(key, value);
cache.put(key, newNode);
addToHead(newNode);
size++;
// 若超过容量，淘汰尾部节点
if (size > capacity) {
DLinkedNode tailNode = removeTail();
cache.remove(tailNode.key);
size--;
}
} else {
// 情况 2：key 已存在，更新缓存值
node.value = value;
moveToHead(node);
}
}
// 6. 辅助方法：删除链表中指定的节点（O(1) 时间）
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 7. 辅助方法：将节点添加到链表头部（O(1) 时间）
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
// 8. 辅助方法：将节点移到链表头部（先删除，再头插）
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
// 9. 辅助方法：移除链表尾部的真实节点，并返回该节点
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
关键点解析
- 哑节点的作用：有了哑头哑尾，插入和删除逻辑就不需要单独处理'链表为空'或'操作头尾节点'的特殊情况，代码更简洁。
- Key 的必要性：节点中必须存储 key。因为当需要从哈希表中删除映射时，我们只有链表节点，如果没有 key，就无法反向定位哈希表中的 entry。
- 复杂度：所有操作均为 O(1)，这是 LRU 缓存的最优实现。
二、LFU 缓存算法
LFU（Least Frequently Used）优先淘汰访问频率最低的元素。如果频率相同，则淘汰最早访问的元素。
1. 哈希表 + 平衡二叉树
这种方案借助 TreeSet 来维护节点的有序性。
核心逻辑
- HashMap：实现 O(1) 查找节点。
- TreeSet：按「频率 + 时间戳」排序。第一个元素即为待淘汰节点。
- 排序规则：先按频率升序，频率相同则按时间戳升序。
代码实现
class LFUCache {
// 缓存节点类：实现 Comparable 用于 TreeSet 排序
class Node implements Comparable<Node> {
int cnt; // 访问频率
int time; // 时间戳
int key;
int value;
public Node(int cnt, int time, int key, int value) {
this.cnt = cnt;
this.time = time;
this.key = key;
this.value = value;
}
@Override
public boolean equals(Object anObject) {
if (this == anObject) return true;
if (anObject instanceof Node) {
Node rhs = (Node) anObject;
return this.cnt == rhs.cnt && this.time == rhs.time;
}
return false;
}
@Override
public int compareTo(Node rhs) {
return cnt == rhs.cnt ? time - rhs.time : cnt - rhs.cnt;
}
@Override
public int hashCode() {
return cnt * 1000000007 + time;
}
}
private int capacity;
private int time;
private Map<Integer, Node> key_table;
private TreeSet<Node> S;
public LFUCache(int capacity) {
this.capacity = capacity;
this.time = 0;
key_table = new HashMap<>();
S = new TreeSet<>();
}
public int get(int key) {
if (capacity == 0 || !key_table.containsKey(key)) {
return -1;
}
Node cache = key_table.get(key);
S.remove(cache); // 移除旧节点，因为属性要更新
cache.cnt++;
cache.time = ++time;
S.add(cache); // 重新加入
return cache.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (!key_table.containsKey(key)) {
if (key_table.size() == capacity) {
// 淘汰频率最低、最早访问的节点
Node toRemove = S.first();
key_table.remove(toRemove.key);
S.remove(toRemove);
}
Node cache = new Node(1, time++, key, value);
key_table.put(key, cache);
S.add(cache);
} else {
Node cache = key_table.get(key);
S.remove(cache);
cache.cnt++;
cache.time = ++time;
cache.value = value;
S.add(cache);
}
}
}
分析
此方案实现简单，但 TreeSet 的增删操作是 O(log N)。每次更新节点都需要先从集合中移除，修改属性后再插入，以保证排序正确。
2. 双哈希表优化
为了达到纯 O(1) 的时间复杂度，我们可以引入「频率桶」的概念。
设计思路
- keyTable：键 → 节点，用于快速查找。
- freqTable：频率 → 双向链表，同一频率的节点挂在同一个链表中。
- minfreq：记录当前最小访问频率，直接定位待淘汰的频率组。
淘汰时，只需找到 minfreq 对应链表的尾节点即可。频率更新时，节点从原频率链表移除，加入新频率链表。
代码实现
class LFUCache {
private int minfreq;
private int capacity;
private Map<Integer, Node> keyTable;
private Map<Integer, DoublyLinkedList> freqTable;
public LFUCache(int capacity) {
this.minfreq = 0;
this.capacity = capacity;
keyTable = new HashMap<>();
freqTable = new HashMap<>();
}
public int get(int key) {
if (capacity == 0 || !keyTable.containsKey(key)) {
return -1;
}
Node node = keyTable.get(key);
int val = node.val;
int freq = node.freq;
// 从原频率链表移除
freqTable.get(freq).remove(node);
// 如果原频率链表为空，删除该频率映射，并更新 minfreq
if (freqTable.get(freq).size == 0) {
freqTable.remove(freq);
if (minfreq == freq) {
minfreq += 1;
}
}
// 加入新频率链表
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, val, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, freqTable.get(freq + 1).getHead());
return val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (!keyTable.containsKey(key)) {
if (keyTable.size() == capacity) {
// 淘汰 minfreq 对应链表的尾节点
Node node = freqTable.get(minfreq).getTail();
keyTable.remove(node.key);
freqTable.get(minfreq).remove(node);
if (freqTable.get(minfreq).size == 0) {
freqTable.remove(minfreq);
}
}
DoublyLinkedList list = freqTable.getOrDefault(1, new DoublyLinkedList());
list.addFirst(new Node(key, value, 1));
freqTable.put(1, list);
keyTable.put(key, freqTable.get(1).getHead());
minfreq = 1;
} else {
// 逻辑同 get，只是更新 value
Node node = keyTable.get(key);
int freq = node.freq;
freqTable.get(freq).remove(node);
if (freqTable.get(freq).size == 0) {
freqTable.remove(freq);
if (minfreq == freq) {
minfreq += 1;
}
}
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, value, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, freqTable.get(freq + 1).getHead());
}
}
class Node {
int key, val, freq;
Node prev, next;
public Node() { this(-1, -1, 0); }
public Node(int key, int val, int freq) {
this.key = key; this.val = val; this.freq = freq;
}
}
class DoublyLinkedList {
Node dummyHead, dummyTail;
int size;
public DoublyLinkedList() {
dummyHead = new Node();
dummyTail = new Node();
dummyHead.next = dummyTail;
dummyTail.prev = dummyHead;
size = 0;
}
public void addFirst(Node node) {
Node prevHead = dummyHead.next;
node.prev = dummyHead;
dummyHead.next = node;
node.next = prevHead;
prevHead.prev = node;
size++;
}
public void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
size--;
}
public Node getHead() { return dummyHead.next; }
public Node getTail() { return dummyTail.prev; }
}
}
对比总结
相比 TreeSet 方案，双哈希表 + 双向链表实现了真正的 O(1) 时间复杂度。虽然代码量稍多，但在对性能要求极高的场景下，这是 LFU 缓存的最优解。
核心在于利用 minfreq 快速定位淘汰目标，并通过分组链表避免全局遍历。实际开发中，可根据具体场景权衡实现复杂度与性能需求。
