wonder/leetcode-go
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
leetcode-go/链表/35-LRU 缓存.md
T

19 KiB
Raw Permalink Blame History

tags, create time
tags create time
LeetCode
哈希表
链表
设计
中等
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 指针。

数据结构设计

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 性质维持不变？

流程：

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)）：

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 有三种情况，你能枚举出来吗？

分三种情况处理：

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)）：

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)：将节点从链表中的任意位置摘除

// node.Prev 和 node.Next 都已正确指向它在链表中的邻居
node.Prev.Next = node.Next
node.Next.Prev = node.Prev

2. addToHead(node)：将节点插入到哨兵头部之后

node.Prev = dummyHead
node.Next = dummyHead.Next
dummyHead.Next.Prev = node
dummyHead.Next = node

3. removeTail()：摘除尾部有效节点（即 DummyTail 前面那个）

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 包已经实现了双向链表，可以让代码量减少一半以上：

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] ✅ 相关题目串联

代码

手写双向链表 + 哈希表 ⭐（标准答案）

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

Reference in New Issue View Git Blame Copy Permalink