一、LRU 缓存算法
1. 哈希表 + 双向链表
问题背景 设计一个满足 LRU（最近最少使用）原则的缓存结构。当缓存达到容量上限时，需要淘汰最久未使用的元素。
核心思路 单纯使用数组或链表无法同时满足 O(1) 的查找和删除效率。最佳方案是组合数据结构：
- 哈希表（HashMap）：存储 key 到节点的映射，实现 O(1) 快速查找。
- 双向链表：维护节点的使用顺序。最近访问的节点移至头部，最久未使用的在尾部，淘汰时直接移除尾部。
- 哑头/哑尾节点：作为哨兵，简化边界处理，避免判断空指针或首尾节点的特殊逻辑。
代码实现
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 = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node);
return node.value;
}
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);
}
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}
关键点解析
moveToHead是 LRU 的核心，每次访问或更新都需将节点提到头部。- 淘汰逻辑发生在
put且size > capacity时，直接移除tail.prev。 - 节点中必须保存
key，以便从哈希表中同步删除被替换的节点。
二、LFU 缓存算法
LFU（最不经常使用）算法优先淘汰访问频率最低的元素。若频率相同，则淘汰最早访问的。
1. 哈希表 + 平衡二叉树
利用 TreeSet 按频率和时间戳排序，可快速获取待淘汰节点，但增删操作为 O(log n)。
核心逻辑
- 每个节点记录访问次数
cnt和时间戳time。 TreeSet根据cnt升序、time升序排列，队首即为淘汰目标。- 更新节点时需先从集合移除，修改属性后再加入，以维持有序性。
代码实现
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 o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node rhs = (Node) o;
return this.cnt == rhs.cnt && this.time == rhs.time;
}
@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> keyTable;
private TreeSet<Node> S;
public LFUCache(int capacity) {
this.capacity = capacity;
this.time = 0;
keyTable = new HashMap<>();
S = new TreeSet<>();
}
public int get(int key) {
if (capacity == 0 || !keyTable.containsKey(key)) return -1;
Node cache = keyTable.get(key);
S.remove(cache);
cache.cnt++;
cache.time = ++time;
S.add(cache);
keyTable.put(key, cache);
return cache.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (!keyTable.containsKey(key)) {
if (keyTable.size() == capacity) {
Node minNode = S.first();
keyTable.remove(minNode.key);
S.remove(minNode);
}
Node cache = new Node(1, time++, key, value);
keyTable.put(key, cache);
S.add(cache);
} else {
Node cache = keyTable.get(key);
S.remove(cache);
cache.cnt++;
cache.time = ++time;
cache.value = value;
S.add(cache);
keyTable.put(key, cache);
}
}
}
2. 双哈希表优化
为了达到纯 O(1) 复杂度，可使用双哈希表配合双向链表。
设计思路
keyTable：Key -> Node，用于快速定位。freqTable：Frequency -> DoublyLinkedList，同一频率的节点挂在同一个链表中。minfreq：记录当前最小频率，淘汰时直接定位该频率组。- 节点访问后，从原频率链表移除，加入新频率链表头部。
代码实现
class LFUCache {
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.next = node.next;
node.next.prev = node.prev;
size--;
}
public Node getHead() { return dummyHead.next; }
public Node getTail() { return dummyTail.prev; }
}
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++;
}
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, val, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, list.getHead());
return val;
}
public void put(int key, int value) {
if (capacity == 0) return;
if (!keyTable.containsKey(key)) {
if (keyTable.size() == capacity) {
DoublyLinkedList list = freqTable.get(minfreq);
Node node = list.getTail();
keyTable.remove(node.key);
list.remove(node);
if (list.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, list.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++;
}
DoublyLinkedList list = freqTable.getOrDefault(freq + 1, new DoublyLinkedList());
list.addFirst(new Node(key, value, freq + 1));
freqTable.put(freq + 1, list);
keyTable.put(key, list.getHead());
}
}
}
总结
- LRU 适合数据局部性明显、近期访问概率高的场景。
- LFU 适合长期访问频率稳定的场景。
- 双哈希表实现的 LFU 在时间复杂度上优于 TreeSet 方案，是更优的工程实践。