---
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 缓存的常规做法，也是面试的默认期望。