LRU 缓存算法
哈希表 + 双向链表
以 LeetCode 上的 LRU 缓存问题为例，核心需求是支持 get 和 put 操作，且时间复杂度需达到 O(1)。这通常通过组合哈希表和双向链表来实现。
设计思路
双向链表负责维护节点的访问顺序：最近使用的节点放在头部，最少使用的在尾部。当容量满时，直接删除尾部节点即可。哈希表则用于存储 key 到节点的映射，解决链表遍历查找慢的问题，确保 O(1) 的查找速度。
为了简化边界处理，通常会引入哑头（head）和哑尾（tail）节点。这样在插入或删除首尾节点时，无需判断链表是否为空或是否只有一个节点，逻辑更加统一。
核心规则很简单：
- 访问/更新：将节点移到链表头部，标记为'最近使用'。
- 新增：添加到头部，若超过容量，删除尾部节点并同步清理哈希表。
代码实现
class LRUCache {
// 双向链表节点类：封装缓存的 key、value，以及前后指针
class DLinkedNode {
int key; // 缓存键（淘汰节点时需要通过 key 删除哈希表中的映射）
int value; // 缓存值
DLinkedNode prev; // 前驱节点（双向链表）
DLinkedNode next; // 后继节点（双向链表）
// 无参构造：用于创建哑头/哑尾节点（无实际 key/value）
public DLinkedNode() {}
// 有参构造：用于创建真实的缓存节点（初始化 key 和 value）
public DLinkedNode(int _key, int _value) {
this.key = _key;
this.value = _value;
}
}
// 哈希表：key -> 节点（O(1) 查找）
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 = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
// get 操作：根据 key 获取缓存值
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
moveToHead(node); // 将节点移到链表头部
return node.value;
}
// 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);
}
}
// 辅助方法：删除链表中指定的节点（O(1) 时间）
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 辅助方法：将节点添加到链表头部（O(1) 时间）
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;
}
}
关键点分析
- DLinkedNode 内部类：除了存储 key 和 value，prev/next 指针支持 O(1) 时间的节点增删。特别注意，节点中必须存储 key，因为淘汰时我们需要通过 key 从哈希表中删除映射，仅存 value 无法反向查找。
- 哑头/哑尾节点：这是工程实践中常用的技巧，避免了大量
if (head == null)或if (tail == null)的判断，让增删逻辑统一。 - 核心方法：
moveToHead保证了'最近使用的节点在头部'，这是 LRU 规则的核心体现。removeTail配合哈希表删除，确保了空间限制下的淘汰机制。
LFU 缓存算法
LFU（Least Frequently Used）策略优先淘汰访问频率最低的元素。若频率相同，则淘汰最早访问的元素。
方案一：哈希表 + 平衡二叉树
借助 HashMap 实现 O(1) 查找，借助 TreeSet 实现节点的有序存储（按频率 + 时间戳排序）。TreeSet 的第一个元素即为待淘汰节点。
核心逻辑
需要自定义 Node 类实现 Comparable 接口，定义排序规则：先按频率升序，频率相同则按时间戳升序。每次访问或更新节点时，需先从 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);
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);
}
}
}
此方案中，TreeSet 的增删操作是 O(log n)，虽然不如纯哈希表快，但实现起来相对直观。
方案二：双哈希表优化
为了达到所有操作 O(1) 的时间复杂度，可以使用双层哈希表 + 双向链表。
设计思路
- keyTable：键 → 节点，快速查找。
- freqTable：频率 → 双向链表，同一频率的节点存在同一个链表中。
- minfreq：记录当前最小访问频率，直接定位待淘汰的频率组。
淘汰时，删除 minfreq 对应链表的尾节点（该频率下最久未使用的节点）。频率更新时，节点从原频率链表移除，加入新频率链表；若原频率链表为空且等于 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, 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 = 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 和 LFU 都是经典的缓存淘汰策略。LRU 基于访问时间，适合数据访问具有局部性的场景；LFU 基于访问频率，适合某些热点数据长期被频繁访问的场景。
在实际工程中，选择哪种方案取决于具体业务对时间复杂度的要求以及对内存开销的容忍度。理解其背后的数据结构设计，对于应对面试和优化系统性能都至关重要。