一、LRU 缓存算法
1. 哈希表 + 双向链表
在面试和实际系统设计中，LRU（Least Recently Used）是最经典的缓存淘汰策略。它的核心需求是：支持 O(1) 时间复杂度的查找、插入和删除操作。
单纯用数组或链表无法满足，单纯用哈希表又无法维护访问顺序。因此，最佳实践是将哈希表与双向链表结合使用。
核心设计思路
- 双向链表：维护缓存节点的访问顺序。最近使用的节点放在头部，最少使用的节点放在尾部。淘汰时直接删尾部。
- 哈希表：存储 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) {
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 {
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;
}
}
代码分析要点
- DLinkedNode：内部类封装了键值对及指针。注意
key必须保存，因为淘汰时需要通过它从哈希表中删除映射，仅存 value 无法反向查找。 - 哑节点：
head和tail是哨兵，让增删逻辑统一，不用单独处理空链表或单节点情况。 - moveToHead：这是 LRU 的核心体现。每次访问或更新，都要把节点提到最前面，保证尾部永远是'最久未使用'的。
二、LFU 缓存算法
LFU（Least Frequently Used）淘汰的是访问频率最低的元素。如果频率相同，则淘汰最早访问的。
1. 哈希表 + 平衡二叉树
这种方案利用 TreeSet 来维护有序性，按频率和时间戳排序。
核心逻辑
- HashMap：实现 O(1) 查找节点。
- TreeSet：按「频率 + 时间戳」排序，第一个元素即为待淘汰节点。
- 排序规则：先按频率升序，频率相同则按时间戳升序。
代码实现
class LFUCache {
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);
key_table.put(key, 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) {
key_table.remove(S.first().key);
S.remove(S.first());
}
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);
key_table.put(key, cache);
}
}
}
2. 双哈希表（优化方案）
上述 TreeSet 方案的时间复杂度是 O(logN)。为了达到纯 O(1)，我们采用双哈希表 + 双向链表的方案。
算法设计
- keyTable：键 → 节点，用于快速查找。
- freqTable：频率 → 双向链表，同一频率的节点存在同一个链表中。
- minfreq：记录当前最小访问频率，直接定位待淘汰的频率组。
淘汰规则
缓存满时，删除 minfreq 对应链表的尾节点（该频率下最久未使用的节点）。访问节点时，频率 +1，从原频率链表移除，加入新频率链表。
代码实现
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);
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) {
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 {
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;
int val;
int freq;
Node prev;
Node 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;
Node 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 = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
size--;
}
public Node getHead() { return dummyHead.next; }
public Node getTail() { return dummyTail.prev; }
}
}
总结
相比 TreeSet 方案，双哈希表方案将所有操作（增删改查）都优化到了纯 O(1) 时间复杂度，是 LFU 缓存的最优实现。
核心在于：按频率分组。每个频率对应一个双向链表，链表内按 LRU 排序。minfreq 快速定位淘汰目标。只有当原频率链表为空且等于 minfreq 时，才更新 minfreq。
三、总结
LRU 和 LFU 都是面试中高频考察的缓存淘汰算法。
- LRU 侧重于'最近使用'，适合数据访问具有局部性的场景，实现简单高效。
- LFU 侧重于'历史频率'，适合某些数据长期被频繁访问的场景。
理解这两种算法背后的数据结构组合（哈希表 + 链表 vs 哈希表 + 平衡树），对于掌握系统设计中的性能优化至关重要。
