一、什么是 LRU？
Mermaid · 渲染中（下方为源码）
graph LR A[LRU] --> B["哈希表 O(1) 定位"] A --> C["双向链表 O(1) 调整序"]
LRU（Least Recently Used） 是一种缓存淘汰策略：
当缓存容量满时，淘汰最久未被访问的条目。
要求：
get(key)：O(1) 时间返回 value（不存在返回 -1），同时标记该条目为"最近使用"。put(key, value)：O(1) 时间插入或更新条目；若插入时容量满，先淘汰最久未使用的条目。
这是面试中最常考的设计题之一。
二、数据结构选择
为什么不能用单链表？
- 删除中间节点需要 O(n) 找到前驱。
- 把访问到的节点移到链表头也需要 O(n)。
最优组合：哈希表 + 双向链表。
| 数据结构 | 作用 |
|---|---|
哈希表 Map<K, Node> | O(1) 查找 key 对应的链表节点 |
| 双向链表 | O(1) 插入 / 删除任意节点（已知指针） |
链表节点顺序：从头到尾按访问时间递减。
- 链表头 = 最近使用
- 链表尾 = 最久未使用（待淘汰）
三、代码实现
3.1 节点定义
class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}3.2 完整实现
public class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // 哨兵：头
private final Node tail = new Node(0, 0); // 哨兵：尾
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
moveToHead(node);
return;
}
Node fresh = new Node(key, value);
map.put(key, fresh);
addToHead(fresh);
if (map.size() > capacity) {
Node removed = removeTail();
map.remove(removed.key);
}
}
// ===== 双向链表操作 =====
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node node = tail.prev;
removeNode(node);
return node;
}
}四、复杂度分析
get：哈希表 O(1) + 移动节点 O(1) = O(1)put：同上 = O(1)- 空间：O(capacity)
五、进阶：LFU（最不经常使用）
LFU 淘汰访问频率最低的条目，比 LRU 更复杂。
经典实现需要：
- 节点带
freq字段。 - 用
Map<Integer, DoublyLinkedList>维护freq → 节点列表。 - 维护当前最小频率。
模板：
class LFUCache {
// ===== 双向链表 =====
static class DLinkedList {
Node head = new Node(0, 0), tail = new Node(0, 0); // 哨兵
int size = 0;
DLinkedList() { head.next = tail; tail.prev = head; }
void addFirst(Node n) {
n.prev = head;
n.next = head.next;
head.next.prev = n;
head.next = n;
size++;
}
void removeNode(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
size--;
}
Node removeLast() {
if (size == 0) return null;
Node n = tail.prev;
removeNode(n);
return n;
}
boolean isEmpty() { return size == 0; }
}
static class Node {
int key, value, freq;
Node prev, next;
Node(int k, int v) { key = k; value = v; freq = 1; }
}
Map<Integer, Node> nodeMap = new HashMap<>(); // key → 节点
Map<Integer, DLinkedList> freqMap = new HashMap<>(); // freq → 链表
int minFreq = 0, capacity;
public LFUCache(int capacity) { this.capacity = capacity; }
public int get(int key) {
if (capacity == 0) return -1;
Node node = nodeMap.get(key);
if (node == null) return -1;
increaseFreq(node);
return node.value;
}
public void put(int key, int value) {
if (capacity == 0) return;
Node node = nodeMap.get(key);
if (node != null) {
node.value = value;
increaseFreq(node);
return;
}
if (nodeMap.size() == capacity) {
// 淘汰 minFreq 链表的尾节点（最久未访问）
DLinkedList list = freqMap.get(minFreq);
Node removed = list.removeLast();
nodeMap.remove(removed.key);
}
Node fresh = new Node(key, value);
nodeMap.put(key, fresh);
freqMap.computeIfAbsent(1, k -> new DLinkedList()).addFirst(fresh);
minFreq = 1;
}
private void increaseFreq(Node node) {
int freq = node.freq;
DLinkedList list = freqMap.get(freq);
list.removeNode(node);
if (freq == minFreq && list.isEmpty()) minFreq++;
node.freq++;
freqMap.computeIfAbsent(node.freq, k -> new DLinkedList()).addFirst(node);
}
}关键点：
minFreq维护当前最低频率。每次 get / put 增加频率后，若旧频率链表空了且等于 minFreq，要把 minFreq +1。
六、为什么必须用双向链表？
| 数据结构 | 删除已知节点 | 移动到头 |
|---|---|---|
| 单链表 | O(n)（找前驱） | O(n) |
| 双向链表 | O(1) | O(1) |
双向链表的核心优势：已知
prev和next指针，可以不依赖前驱完成删除。
七、哨兵节点（dummy head/tail）的好处
// 有哨兵时：不用判断 head/tail 是不是 null
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}好处：
- 边界条件减少（链表为空 / 只有一个节点都不用特判）。
- 代码更简洁、更安全。
八、Java 内置：LinkedHashMap
Java 提供了一个内置实现：LinkedHashMap。
public class LRUCache extends LinkedHashMap<Integer, Integer> {
private final int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75f, true); // accessOrder = true
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
}关键参数：accessOrder = true → 按访问顺序排序。
removeEldestEntry → 容量满时自动删除最旧的条目。
九、其他变种
| 变种 | 行为 |
|---|---|
| FIFO | 淘汰最早插入的条目 |
| LRU | 淘汰最久未访问 |
| LFU | 淘汰访问频率最低 |
| ARC | 自适应，融合 LRU + LFU |
| 2Q | 两个队列，新旧缓存区分 |
十、面试常见追问
Q1: 为什么不用 LinkedList？
java.util.LinkedList查找 O(n)，定位后再删除也是 O(n)。需要双向链表是为了已知指针就能 O(1) 删除。
Q2: 多线程下怎么办？
用
ConcurrentHashMap+ 加锁。读写并发场景下用读写锁ReentrantReadWriteLock。
Q3: 节点 value 很大怎么办？
节点只存引用。value 是大对象时，多份缓存仍能共享同一对象。
Q4: 内存紧张怎么办？
软引用（
SoftReference）+ LRU：缓存被淘汰时，对象在内存压力下可被 GC 回收。
十一、刷题清单
| 题目 | 难度 | 关键点 |
|---|---|---|
| LRU Cache | 🟡 | 哈希 + 双向链表 |
| LFU Cache | 🔴 | 多级频率链表 |
| Design In-Memory File System | 🟠 | TreeMap + 路径处理 |
| Design Twitter | 🟠 | 时间优先队列 + 关注列表 |
| All O`one Data Structure | 🔴 | 双向链表 + 计数 |
十二、心法
设计题 = 数据结构选择 + 边界处理 + 代码模板。
掌握 LRU 模板，再做 LFU、其他变种就是改字段、加链表。