538 lines
19 KiB
Markdown
538 lines
19 KiB
Markdown
|
---
|
|||
|
|
tags: ["LeetCode", "哈希表", "链表", "设计", "中等"]
|
|||
|
|
create time: 2026-05-18 16:00
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# 35-LRU 缓存
|
|||
|
|
|
|||
|
|
## 题面
|
|||
|
|
|
|||
|
|
请你设计并实现一个满足 **LRU (最近最少使用) 缓存** 约束的数据结构。
|
|||
|
|
|
|||
|
|
实现 `LRUCache` 类：
|
|||
|
|
|
|||
|
|
- `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存
|
|||
|
|
- `int get(int key)` 如果关键字 `key` 存在于缓存中，则返回关键字的值，否则返回 `-1` 。
|
|||
|
|
- `void put(int key, int value)` 如果关键字 `key` 已经存在，则变更其数据值 `value` ；如果不存在，则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ，则应该 **逐出（evict）** 最久未使用的关键字。
|
|||
|
|
|
|||
|
|
函数 `get` 和 `put` 必须以 **O(1) 的平均时间复杂度** 运行。
|
|||
|
|
|
|||
|
|
**示例：**
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
输入
|
|||
|
|
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
|
|||
|
|
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
|
|||
|
|
输出
|
|||
|
|
[null, null, null, 1, null, -1, null, -1, 3, 4]
|
|||
|
|
|
|||
|
|
解释
|
|||
|
|
LRUCache lRUCache = new LRUCache(2);
|
|||
|
|
lRUCache.put(1, 1); // 缓存是 {1=1}
|
|||
|
|
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
|
|||
|
|
lRUCache.get(1); // 返回 1
|
|||
|
|
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
|
|||
|
|
lRUCache.get(2); // 返回 -1 (未找到)
|
|||
|
|
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
|
|||
|
|
lRUCache.get(1); // 返回 -1 (未找到)
|
|||
|
|
lRUCache.get(3); // 返回 3
|
|||
|
|
lRUCache.get(4); // 返回 4
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**提示：**
|
|||
|
|
|
|||
|
|
- `1 <= capacity <= 3000`
|
|||
|
|
- `0 <= key <= 10000`
|
|||
|
|
- `0 <= value <= 10^5`
|
|||
|
|
- 最多调用 `2 * 10^5` 次 `get` 和 `put`
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 核心约束
|
|||
|
|
> **O(1) 时间复杂度**——这是这道题的灵魂要求。任何涉及线性遍历的操作（如切片删除、遍历 map 找最旧元素）都会直接超时。这意味着每次操作都必须是"直接寻址"级别的速度。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
> [!question] 💡 需求拆解
|
|||
|
|
> LRU 缓存需要同时满足两个看似矛盾的要求：
|
|||
|
|
>
|
|||
|
|
> | 操作 | 需要什么能力 | 天然数据结构 |
|
|||
|
|
> |------|-------------|-------------|
|
|||
|
|
> | `get(key)` | **按 key 快速查找** → O(1) | 哈希表 ✅ |
|
|||
|
|
> | `put(key)` + 驱逐最老元素 | **维护访问顺序**，能在两端高效增删 | 双向链表 ✅ |
|
|||
|
|
|
|||
|
|
单一数据结构无法同时满足这两个需求：
|
|||
|
|
- **纯哈希表**：查找 O(1)，但不知道哪个元素"最久未用"。
|
|||
|
|
- **纯双向链表**：能维护顺序、两端增删都是 O(1)，但查找需要遍历 O(n)。
|
|||
|
|
|
|||
|
|
**解法：哈希表 + 双向链表的组合！** 🎯
|
|||
|
|
|
|||
|
|
> [!tip] 🔑 为什么是"双向"链表而不是"单向"？
|
|||
|
|
> 在双向链表中删除任意节点只需要该节点的指针（因为既有 next 也有 prev）。但单向链表要删除节点 A，必须知道 A.prev——而 A 自身不持有这个引用。如果你只有 A 的指针，就得从头遍历找到 A.prev，这就变成了 O(n)。**O(1) 删除的前提是有 prev 指针。**
|
|||
|
|
|
|||
|
|
### 数据结构设计
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart TD
|
|||
|
|
subgraph HashMap["哈希表 map[key] -- Node"]
|
|||
|
|
H1["1 -> NodeA"]
|
|||
|
|
H2["3 -> NodeB"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
subgraph DoublyLinkedList["双向链表 (队首=最近使用 <-> 队尾=最久未用)"]
|
|||
|
|
DH["DummyHead"] --> NA["key=1 -- val=1"]
|
|||
|
|
NA <--> NB["key=3 -- val=3"]
|
|||
|
|
NB -.-> DT["nil (DummyTail)"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
H1 -.指向.-> NA
|
|||
|
|
H2 -.指向.-> NB
|
|||
|
|
|
|||
|
|
style HashMap fill:#e8f4fd,stroke:#28a
|
|||
|
|
style DoublyLinkedList fill:#fff3cd,stroke:#28a
|
|||
|
|
style NA fill:#bbf,stroke:#333
|
|||
|
|
style NB fill:#f9d,stroke:#333
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**约定：**
|
|||
|
|
- **链表头部（靠近 DummyHead）** = 最近使用的节点（most recent）
|
|||
|
|
- **链表尾部（靠近 DummyTail）** = 最久未使用的节点（least recent / victim）
|
|||
|
|
- DummyHead / DummyTail 是哨兵节点，让边界操作不需要特殊判空
|
|||
|
|
|
|||
|
|
### 操作详解
|
|||
|
|
|
|||
|
|
#### 操作一：`get(key)`
|
|||
|
|
|
|||
|
|
> [!question] 💡 思考一下
|
|||
|
|
> 查到键后，除了返回值，还需要做什么才能让 LRU 性质维持不变？
|
|||
|
|
|
|||
|
|
**流程：**
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart TD
|
|||
|
|
START["get(key)"] --> LOOKUP{"map 中存在 key?"}
|
|||
|
|
LOOKUP -->|否| RETURN_NEG1["return -1"]
|
|||
|
|
LOOKUP -->|是| FOUND["从 map 拿到对应 Node 指针"]
|
|||
|
|
FOUND --> REMOVE["将 Node 从当前位置移除 removeNode(node)"]
|
|||
|
|
REMOVE --> ADD_HEAD["把 Node 移到队 head.add(node)"]
|
|||
|
|
ADD_HEAD --> RETURN_VAL["return node.val"]
|
|||
|
|
|
|||
|
|
style FOUND fill:#bbf,stroke:#333
|
|||
|
|
style REMOVE fill:#ffd700,stroke:#333
|
|||
|
|
style ADD_HEAD fill:#f9d,stroke:#333
|
|||
|
|
style RETURN_VAL fill:#d4edda,stroke:#28a
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**逐步演示（capacity=2，当前缓存 `{1=1, 3=3}`，调用 `get(1)`）：**
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart LR
|
|||
|
|
subgraph BEFORE["get(1) 之前"]
|
|||
|
|
B1["head --> key=1--val=1 --> key=3--val=3 <-- tail"]
|
|||
|
|
end
|
|||
|
|
|
|||
|
|
B1 --> REMOVE["① 摘下 key=1--val=1"]
|
|||
|
|
REMOVE --> MID["中间态: head --> key=3--val=3 <-- tail\n map 仍指向原 key=1--val=1 节点"]
|
|||
|
|
MID --> REINSERT["② 插入 head 之后"]
|
|||
|
|
REINSERT --> AFTER["③ 结果: head --> key=1--val=1 --> key=3--val=3 <-- tail\n 1 变成最近使用的"]
|
|||
|
|
|
|||
|
|
style BEFORE fill:#ffd700,stroke:#333
|
|||
|
|
style AFTER fill:#d4edda,stroke:#28a
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**时间复杂度：O(1)** — map 查找 O(1) + 链表节点摘除/重插 O(1)
|
|||
|
|
|
|||
|
|
#### 操作二：`put(key, value)`
|
|||
|
|
|
|||
|
|
> [!question] 💡 put 有三种情况，你能枚举出来吗？
|
|||
|
|
|
|||
|
|
**分三种情况处理：**
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart TD
|
|||
|
|
START["putkey, value"] --> CHECK{"key 已存在？"}
|
|||
|
|
|
|||
|
|
CHECK -->|是| UPDATE["更新值 node.val = value\n然后把 node 移到队首\n-- 因为它变最新了"]
|
|||
|
|
|
|||
|
|
CHECK -->|否| CAPACITY{"已满？"}
|
|||
|
|
|
|||
|
|
CAPACITY -->|是| EVICT["① 删除 tail 前面的节点（最久未用）\n② 从 map 中删除对应的 key\n③ 创建新节点插到队首\n④ map[key]=newNode"]
|
|||
|
|
|
|||
|
|
CAPACITY -->|否| INSERT["① 创建新节点插到队首\n② map[key]=newNode"]
|
|||
|
|
|
|||
|
|
UPDATE --> DONE["✅ 完成"]
|
|||
|
|
EVICT --> DONE
|
|||
|
|
INSERT --> DONE
|
|||
|
|
|
|||
|
|
style UPDATE fill:#bbf,stroke:#333
|
|||
|
|
style EVICT fill:#f9d,stroke:#333
|
|||
|
|
style INSERT fill:#9df,stroke:#333
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**逐步演示（capacity=2，当前缓存 `{1=1, 2=2}`，调用 `put(3, 3)`）：**
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart LR
|
|||
|
|
S1["初始: {1=1, 2=2}\nhead --> key=1--val=1 --> key=2--val=2 <-- tail"] --> FULL{"容量满？"}
|
|||
|
|
FULL -->|是, key=3 不存在| EVICT["驱逐 tail 前节点 key=2--val=2\nmap 删除 key=2"]
|
|||
|
|
EVICT --> MID["临时: {1=1}\nhead --> key=1--val=1 <-- tail"]
|
|||
|
|
MID --> INSERT["插入 key=3--val=3 到队首"]
|
|||
|
|
INSERT --> RESULT["结果: {1=1, 3=3}\nhead --> key=3--val=3 --> key=1--val=1 <-- tail\n 3 变最新, 1 变最旧"]
|
|||
|
|
|
|||
|
|
style S1 fill:#ffd700,stroke:#333
|
|||
|
|
style RESULT fill:#d4edda,stroke:#28a
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
**时间复杂度：O(1)** — 所有步骤都是 map 查询/O(1) + 链表操作 O(1)
|
|||
|
|
|
|||
|
|
### 完整执行过程追踪（示例）
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
capacity = 2
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
| 操作 | map[key→Node] | 链表 (head→tail) | 返回值 |
|
|||
|
|
|------|---------------|-----------------|--------|
|
|||
|
|
| `put(1,1)` | `{1→A}` | `[1,1]` | — |
|
|||
|
|
| `put(2,2)` | `{1→A, 2→B}` | `[1,1] ↔ [2,2]` | — |
|
|||
|
|
| `get(1)` | `{1→A, 2→B}` | `[1,1] ↔ [2,2]` *(1 移到头)* | **1** |
|
|||
|
|
| `put(3,3)` | `{1→A, 3→C}` *[驱逐 B]* | `[3,3] ↔ [1,1]` | — |
|
|||
|
|
| `get(2)` | — | — | **-1** *(2 不在 map 中)* |
|
|||
|
|
| `put(4,4)` | `{4→D, 3→C}` *[驱逐 A]* | `[4,4] ↔ [3,3]` | — |
|
|||
|
|
| `get(1)` | — | — | **-1** *(1 不在 map 中)* |
|
|||
|
|
| `get(3)` | `{4→D, 3→C}` | `[4,4] ↔ [3,3]` | **3** |
|
|||
|
|
| `get(4)` | `{4→D, 3→C}` | `[4,4] ↔ [3,3]` | **4** |
|
|||
|
|
|
|||
|
|
### 核心操作实现原理
|
|||
|
|
|
|||
|
|
#### 1. `removeNode(node)`：将节点从链表中的任意位置摘除
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
// node.Prev 和 node.Next 都已正确指向它在链表中的邻居
|
|||
|
|
node.Prev.Next = node.Next
|
|||
|
|
node.Next.Prev = node.Prev
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
#### 2. `addToHead(node)`：将节点插入到哨兵头部之后
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
node.Prev = dummyHead
|
|||
|
|
node.Next = dummyHead.Next
|
|||
|
|
dummyHead.Next.Prev = node
|
|||
|
|
dummyHead.Next = node
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
#### 3. `removeTail()`：摘除尾部有效节点（即 DummyTail 前面那个）
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
removed := dummyTail.Prev // 最久未用的节点
|
|||
|
|
removeNode(removed) // 从链表中摘除
|
|||
|
|
return removed // 返回被驱逐的节点
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!info] 🧠 为什么加 DummyHead 和 DummyTail？
|
|||
|
|
> 如果没有哨兵节点，操作空链表或只有一个节点的链表时需要大量的 nil 判断，代码会变得冗长且容易出错。哨兵节点让这些边界情况自动正确处理——即使是空链表，dummyHead.next = dummyTail 也永远成立。
|
|||
|
|
|
|||
|
|
> [!success] ✅ 复杂度分析
|
|||
|
|
|
|||
|
|
| 操作 | 时间复杂度 | 空间复杂度 |
|
|||
|
|
|------|-----------|-----------|
|
|||
|
|
| `get(key)` | **O(1)** | — |
|
|||
|
|
| `put(key, value)` | **O(1)** | — |
|
|||
|
|
| 整体 | O(1) 均摊 | **O(capacity)** 存储 n 个节点 |
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码提示
|
|||
|
|
|
|||
|
|
### LRU 缓存通用模板
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
type Node struct {
|
|||
|
|
Key int
|
|||
|
|
Val int
|
|||
|
|
Prev *Node
|
|||
|
|
Next *Node
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
type LRUCache struct {
|
|||
|
|
cap int
|
|||
|
|
size int
|
|||
|
|
dummyHead *Node // 哨兵头
|
|||
|
|
dummyTail *Node // 哨兵尾
|
|||
|
|
cache map[int]*Node // key → Node 映射
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func Constructor(capacity int) LRUCache {
|
|||
|
|
// ① 初始化哨兵节点，互相指向
|
|||
|
|
head := &Node{}
|
|||
|
|
tail := &Node{}
|
|||
|
|
head.Next = tail
|
|||
|
|
tail.Prev = head
|
|||
|
|
|
|||
|
|
return LRUCache{
|
|||
|
|
cap: capacity,
|
|||
|
|
size: 0,
|
|||
|
|
dummyHead: head,
|
|||
|
|
dummyTail: tail,
|
|||
|
|
cache: make(map[int]*Node),
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func (c *LRUCache) Get(key int) int {
|
|||
|
|
// ① map 查不到 → 返回 -1
|
|||
|
|
// ② map 查到了 → 摘除 + 移到头部 → 返回值
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func (c *LRUCache) Put(key int, value int) {
|
|||
|
|
// 如果 key 已存在：更新值 + 移到头部
|
|||
|
|
// 如果 key 不存在：
|
|||
|
|
// 如果满了：驱逐尾部节点 + map 删除
|
|||
|
|
// 创建新节点 + 插到头部 + map 记录
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 关键辅助方法
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
// 将已有节点从当前位置摘除
|
|||
|
|
removeNode(node):
|
|||
|
|
node.Prev.Next = node.Next
|
|||
|
|
node.Next.Prev = node.Prev
|
|||
|
|
|
|||
|
|
// 把节点插到 dummyHead 后面（最新位置）
|
|||
|
|
addToHead(node):
|
|||
|
|
node.Prev = dummyHead
|
|||
|
|
node.Next = dummyHead.Next
|
|||
|
|
dummyHead.Next.Prev = node
|
|||
|
|
dummyHead.Next = node
|
|||
|
|
|
|||
|
|
// 把节点先摘除再插到头部（组合操作）
|
|||
|
|
moveToHead(node):
|
|||
|
|
removeNode(node)
|
|||
|
|
addToHead(node)
|
|||
|
|
|
|||
|
|
// 摘除尾部前一个节点（被驱逐者）
|
|||
|
|
removeTail():
|
|||
|
|
toRemove = dummyTail.Prev
|
|||
|
|
removeNode(toRemove)
|
|||
|
|
return toRemove
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 技巧
|
|||
|
|
|
|||
|
|
> [!tip] 🔑 组合模式："哈希加速 + 链表定序"
|
|||
|
|
> 当题目同时要求 **"按 key 查找"** 和 **"维护某种顺序"** 时，考虑用哈希表做 O(1) 定位、用有序容器做排序。这种组合还出现在以下场景中：
|
|||
|
|
> - **LFU 缓存**（最少频次）→ 哈希表 + 频次桶 + 双向链表
|
|||
|
|
> - **Top K 频繁元素** → 哈希表计数 + 优先队列（堆）
|
|||
|
|
> - **滑动窗口最大值** → 哈希集合 + 双端队列（单调队列）
|
|||
|
|
|
|||
|
|
> [!tip] 🔑 哨兵节点（Dummy Head/Tail）的价值
|
|||
|
|
> 在所有需要"在头部/尾部增删"的链式结构中，加入虚拟头尾节点可以消除大量 nil 判断。这不仅是代码简洁的问题——更重要的是**减少分支预测失败的概率**。CPU 对规律性高的代码执行效率更高。
|
|||
|
|
>
|
|||
|
|
> 典型应用：链表反转、合并链表、本题、以及所有需要频繁在头部操作的场景。
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见错误 1：漏掉 update 场景
|
|||
|
|
> `put(key, value)` 中 key 已存在时要更新值并**移到头部**。很多人只写了更新值，忘了移到头部，导致 LRU 失效。记住：`put` 等同于"先读后写再刷新优先级"。
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见错误 2：驱逐时没删 map
|
|||
|
|
> 从链表中移除了最久未用的节点，却忘记了从 `cache map` 中 `delete(key)`。这样后续 `get` 仍然能找到这个已经被淘汰的节点，缓存一致性被破坏。
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见错误 3：capacity 为负数或零
|
|||
|
|
> 题目说明 `1 <= capacity`，所以不需要处理容量 ≤ 0 的情况。但如果面试题中面试官追问，合理的做法是直接 panic 或在构造函数中返回一个错误。
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见错误 4：链表操作指针遗漏
|
|||
|
|
> 双向链表插入/删除需要操作 **4 条指针**（每个方向各两条），少写一条就会导致链表断裂或死循环。建议通过"拆开两步走"的方式降低出错率：先拆后连。
|
|||
|
|
|
|||
|
|
> [!note] 🐹 Go 中的实现要点
|
|||
|
|
> 1. **可以用方法接收者**（`(c *LRUCache)`）封装辅助操作，也可以用普通函数独立实现。后者更清晰、更容易测试。
|
|||
|
|
> 2. Go 的 `map` 在 `delete(m, key)` 时对不存在的 key 不会 panic——直接无操作。这是一个安全的特性可以利用。
|
|||
|
|
> 3. Go 的 struct 零值会自动将指针字段设为 nil，所以 `Node{}` 的 `Prev` 和 `Next` 都是 nil。但在构建链表时必须显式设置它们。
|
|||
|
|
> 4. Go 1.21+ 提供了 `container/list` 包，其中 `list.List` 就是双向链表。在实际工程中可以直接使用它来缩短代码——但面试中通常要求自己手写。
|
|||
|
|
|
|||
|
|
> [!info] 📊 如果允许使用标准库？
|
|||
|
|
|
|||
|
|
Go 的 `container/list` 包已经实现了双向链表，可以让代码量减少一半以上：
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
type LRUCache struct {
|
|||
|
|
cap int
|
|||
|
|
list *list.List
|
|||
|
|
cache map[int]*list.Element
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
type entry struct {
|
|||
|
|
Key, Val int
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func Constructor(capacity int) LRUCache {
|
|||
|
|
return LRUCache{cap: capacity, list: list.New(), cache: make(map[int]*list.Element)}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func (c *LRUCache) Get(key int) int {
|
|||
|
|
if e, ok := c.cache[key]; ok {
|
|||
|
|
c.list.MoveToFront(e)
|
|||
|
|
return e.Value.(*entry).Val
|
|||
|
|
}
|
|||
|
|
return -1
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
func (c *LRUCache) Put(key int, value int) {
|
|||
|
|
if e, ok := c.cache[key]; ok {
|
|||
|
|
e.Value.(*entry).Val = value
|
|||
|
|
c.list.MoveToFront(e)
|
|||
|
|
return
|
|||
|
|
}
|
|||
|
|
e := c.list.PushFront(&entry{key, value})
|
|||
|
|
c.cache[key] = e
|
|||
|
|
if c.list.Len() > c.cap {
|
|||
|
|
removed := c.list.Back()
|
|||
|
|
c.list.Remove(removed)
|
|||
|
|
delete(c.cache, removed.Value.(*entry).Key)
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!success] ✅ 相关题目串联
|
|||
|
|
> - [36-O(1) 数据结构的难题](./36-o1-data-structure.md) — 同一作者设计的 "All O`one Data Structure"，同样是哈希表 + 双向链表
|
|||
|
|
> - [37-最小栈](./37-min-stack.md) — 另一个考察"如何做到 O(1)"的经典题
|
|||
|
|
> - [32-随机链表的复制](./32-随机链表的复制.md) — 同样是链表的指针操作
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
### 手写双向链表 + 哈希表 ⭐（标准答案）
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
package main
|
|||
|
|
|
|||
|
|
// Node 双向链表节点
|
|||
|
|
type Node struct {
|
|||
|
|
Key, Val int
|
|||
|
|
Prev, Next *Node
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// LRUCache LRU 缓存，哈希表 + 双向链表
|
|||
|
|
type LRUCache struct {
|
|||
|
|
cap int
|
|||
|
|
size int
|
|||
|
|
dummyHead *Node // 哨兵头节点
|
|||
|
|
dummyTail *Node // 哨兵尾节点
|
|||
|
|
cache map[int]*Node
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Constructor 初始化 LRU 缓存
|
|||
|
|
func Constructor(capacity int) LRUCache {
|
|||
|
|
head := &Node{}
|
|||
|
|
tail := &Node{}
|
|||
|
|
head.Next = tail
|
|||
|
|
tail.Prev = head
|
|||
|
|
|
|||
|
|
return LRUCache{
|
|||
|
|
cap: capacity,
|
|||
|
|
size: 0,
|
|||
|
|
dummyHead: head,
|
|||
|
|
dummyTail: tail,
|
|||
|
|
cache: make(map[int]*Node),
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Get 获取 key 对应的值，如果不存在返回 -1
|
|||
|
|
// 查到后将该节点移到链表头部（标记为最新使用）
|
|||
|
|
func (c *LRUCache) Get(key int) int {
|
|||
|
|
if node, ok := c.cache[key]; ok {
|
|||
|
|
c.moveToHead(node)
|
|||
|
|
return node.Val
|
|||
|
|
}
|
|||
|
|
return -1
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// Put 插入或更新 key-value
|
|||
|
|
// 若 key 已存在则更新值并移到头部；若不存在则插入到新节点到头部
|
|||
|
|
// 超出容量时驱逐尾部前一个节点（最久未使用）
|
|||
|
|
func (c *LRUCache) Put(key int, value int) {
|
|||
|
|
if node, ok := c.cache[key]; ok {
|
|||
|
|
// 情况 1：key 已存在，更新值并移到头部
|
|||
|
|
node.Val = value
|
|||
|
|
c.moveToHead(node)
|
|||
|
|
return
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// 情况 2：key 不存在，创建新节点
|
|||
|
|
newNode := &Node{Key: key, Val: value}
|
|||
|
|
c.addToHead(newNode)
|
|||
|
|
c.cache[key] = newNode
|
|||
|
|
c.size++
|
|||
|
|
|
|||
|
|
// 超出容量，驱逐尾部节点
|
|||
|
|
if c.size > c.cap {
|
|||
|
|
removed := c.removeTail()
|
|||
|
|
delete(c.cache, removed.Key)
|
|||
|
|
c.size--
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ---------- 辅助方法 ----------
|
|||
|
|
|
|||
|
|
// addToHead 将节点插入到 dummyHead 之后
|
|||
|
|
func (c *LRUCache) addToHead(node *Node) {
|
|||
|
|
node.Prev = c.dummyHead
|
|||
|
|
node.Next = c.dummyHead.Next
|
|||
|
|
c.dummyHead.Next.Prev = node
|
|||
|
|
c.dummyHead.Next = node
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// removeNode 将节点从链表中摘除（不管它在什么位置）
|
|||
|
|
func (c *LRUCache) removeNode(node *Node) {
|
|||
|
|
node.Prev.Next = node.Next
|
|||
|
|
node.Next.Prev = node.Prev
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// moveToHead 先摘除再插到头部（用于 get 命中和 put 更新场景）
|
|||
|
|
func (c *LRUCache) moveToHead(node *Node) {
|
|||
|
|
c.removeNode(node)
|
|||
|
|
c.addToHead(node)
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// removeTail 摘除并返回尾部前一个有效节点
|
|||
|
|
func (c *LRUCache) removeTail() *Node {
|
|||
|
|
removed := c.dummyTail.Prev // 倒数第二个节点 = 最久未用的
|
|||
|
|
c.removeNode(removed)
|
|||
|
|
return removed
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!success] ✅ 执行验证与总结
|
|||
|
|
|
|||
|
|
**这套实现的每一个操作都是严格的 O(1)：**
|
|||
|
|
|
|||
|
|
| 操作 | 路径 | 耗时组成 |
|
|||
|
|
|------|------|---------|
|
|||
|
|
| `Get(key)` | map 查找 → `moveToHead` | O(1) + O(1) = **O(1)** |
|
|||
|
|
| `Put(key, val)`（命中） | map 查找 → `moveToHead` | O(1) + O(1) = **O(1)** |
|
|||
|
|
| `Put(key, val)`（未命中，未满） | map 写入 → `addToHead` | O(1) + O(1) = **O(1)** |
|
|||
|
|
| `Put(key, val)`（未命中，已满） | map 写入 → `addToHead` → `removeTail` → map 删除 | O(1) × 4 = **O(1)** |
|
|||
|
|
|
|||
|
|
> [!TIP] 💬 面试加分话术
|
|||
|
|
> "我选择哈希表 + 双向链表的组合来实现。哈希表保证了 key 的 O(1) 查找，双向链表保证了任意位置节点的 O(1) 增删。为了简化边界处理，我在链表两端加了哨兵节点。整个设计中，最近使用的节点永远保持在头部，最久未用的永远在尾部——这天然匹配 LRU 的语义。唯一需要注意的是 put 操作中 key 已存在的情况，这时候需要先更新值再 move 到头部，保持 LRU 属性。"
|
|||
|
|
|
|||
|
|
> [!note] 🤔 为什么不用单链表？
|
|||
|
|
> 如前所述，单链表若要删除某个已知节点，需要找到它的 predecessor 才能断开前驱指针。虽然可以通过"覆盖后继节点的值"的技巧绕过这个问题（见下方思考），但这牺牲了可读性和正确性保证。**双向链表是 O(1) 删除已知节点的最自然方案。**
|
|||
|
|
|
|||
|
|
> [!question] 💡 延伸思考：单链表的 O(1) 删除 trick
|
|||
|
|
> 如果只能用单链表，有一种技巧可以在只知道待删除节点指针的情况下完成 O(1) 删除：**把后继节点的值复制到当前节点，然后删除后继**。但这要求待删除节点不能是最后一个节点。在 LRU 缓存的场景下，如果要驱逐的是尾节点，这个方法无效。所以这不是一个通用的解决方案。这也解释了为什么 LRU 的标准实现总是用双向链表。
|
|||
|
|
|
|||
|
|
> [!info] 📊 与其他语言的对比
|
|||
|
|
|
|||
|
|
| 语言 | 实现方式 | 备注 |
|
|||
|
|
|------|---------|------|
|
|||
|
|
| Go | 手写 struct + 指针 | 需手动管理 prev/next 指针 |
|
|||
|
|
| Java | `LinkedHashMap` / 手写 Node | JDK 内置 LinkedHashMap 就是 LRU 的实现 |
|
|||
|
|
| Python | `collections.OrderedDict` / 手写 | OrderedDict.move_to_end() 内置支持 |
|
|||
|
|
| C++ | `std::list` + `std::unordered_map` | STL 提供了双向链表和无序 map |
|
|||
|
|
|
|||
|
|
Go 没有类似 Java LinkedHashMap 或 Python OrderedDict 这样的内置结构，因此手写是实现 LRU 缓存的常规做法，也是面试的默认期望。
|