Implement · LRU Cache · Go

LRU 缓存：Go 手撕实现

LC 146，手撕率最高的结构组合题——思路一分钟推导（为什么恰好是哈希 + 双向链表），代码两个版本直接可背：container/list 默写版 + 手写双链表版，LC 146 官方用例本机实测通过。

一个结构组合

哈希管「点」：O(1) 定位；双向链表管「序」：O(1) 摘下 + 头插——单结构怎么改都不行，逐条否决才能推出这个组合

两个 Go 版本

container/list + map 三十行默写版；手写双向链表 + 双哨兵版——面试官说「别用标准库」就切第二版，两版操作一一对应

三个易漏点

Get 命中要前移 · Put 更新也要前移 · 逐出时 delete(map) 的 key 从链表节点里取——写完逐条自查

Implement · Data Structure · LRU 缓存
定位：本 deck 是 LRU 的「思路 + 手撕代码」，面向面试白板默写；工程近似（Redis 采样 / InnoDB 分区 / Clock）、LFU 对比与高频 QA 在 Redis 内存策略、OS 页面置换等各系统 deck。两条主线：结构推导是答题内容本身、两个实现版本是默写素材。代码已在本机 go1.22 实测。

Theory · Design Derivation

思路：逐条列需求，单结构逐一被否决

需求（LC 146 原题约束）候选结构的回答
get(k) O(1) 定位哈希表 ✓；链表 ✗ 要扫 O(n)
维护「最近使用」全序链表 ✓；哈希表 ✗ 无序语义
摘任意节点 O(1)双向链表 ✓；单链表 ✗ 要先找前驱
头插（变 MRU）O(1)双向链表 ✓
删最旧（tail.prev）O(1)双向链表 + 尾哨兵 ✓；数组 ✗ 搬移 O(n)

平衡树 / 跳表是 O(log n)，不达 O(1) 线；数组中间摘除要整体搬移。逐项排除后只剩一个组合。

题目在考什么

容量满了驱逐谁get/put O(1)

缓存容量永远小于全量数据，满了必须驱逐；LRU 驱逐最久未被访问的一条——赌时间局部性（刚用过的马上还会用）。LC 146 的硬约束：get / put 均 O(1)。

结论：两个结构各管一半，焊在一起

哈希表给「点」的能力：key → 节点指针，一次定位；双向链表给「序」的能力：任意 O(1) 摘下、O(1) 头插，头 = MRU、尾 = LRU。组合件 map[key] → *node。

为什么数组 / 单链表都不行

凡是「每次访问都要动全局顺序」的方案（数组搬移、遍历找时间戳最小值）都过不了 O(1)；摘中间节点要 O(1) 拿前驱、删 LRU 要 O(1) 摘尾——只有双向链表两样都做得到。

复杂度与并发

get / put 均 O(1)（哈希定位一次 + 常数次指针改写），空间 O(capacity)；结构本身非线程安全，工程上外包 mutex 或按 key 分片。

答题模板：先复述约束（get/put 均 O(1)）→ 逐项列需求 → 排除单结构 → 报组合（哈希 + 双链表）→ 补一句「节点里同时存 key 和 value」。这个推导过程本身就是面试官想听的内容，比直接背答案高一档。
Implement · Data Structure · LRU 缓存
核心句："哈希管点、双链表管序"。需求表左列是 LC146 题面约束，右列是逐个否决——注意"每次访问都动全局顺序"这个角度：数组、时间戳、堆全都死在这里，只有链表的指针改写是常数。单链表被否决的原因（找前驱 O(n)）是后续追问的第一站。

The Composite Structure

核心结构：map 定位 + 双向链表维护访问序

LRU 缓存的核心复合结构 上层哈希表把每个 key 映射到下层双向链表的节点；链表带 head 和 tail 两个哨兵，头端是最近使用的节点，尾端是最久未使用的节点，相邻节点用前后指针互连。 MAP · O(1) 定位 k1 → ●k2 → ●k3 → ● DOUBLY LINKED LIST · O(1) 摘插 head哨兵 k1|v1 k2|v2 k3|v3 tail哨兵 next prev ◀ MRU · 刚使用 LRU · 最久未用，先淘汰 ▶ 为什么节点必须同时存 key？ 淘汰 tail.prev 后要 delete(map, node.key) 只存 value 的话，map 里那条永远删不掉 哨兵消灭一切边界 head.next 永远是 MRU，tail.prev 永远是 LRU 空表 / 单节点 / 删尾全走同一段代码 Go container/list 源码：环形链表 + root 哨兵 get / put 的每一步都是常数次操作：map 定位一次 + 链表改 4 个指针 → 整体 O(1)
Implement · Data Structure · LRU 缓存
这张图要能白板默写：上排 map（key→节点指针），下排带双哨兵的双向链表，头 MRU 尾 LRU。右侧两张卡就是两个最高频追问：节点为什么存 key（淘汰时反查 map）、为什么要哨兵（边界统一）。图中 k3 标蓝表示"刚被访问过被提到头部"。

Implement I · container/list + map

实现一 · 标准库版：container/list + map，三十行

type entry struct{ key, val int }  // 节点存 key：淘汰反查 map
type LRUCache struct {
    cap   int
    l     *list.List              // Front=MRU · Back=LRU
    m     map[int]*list.Element  // O(1) 定位
}

func Constructor(capacity int) LRUCache {
    return LRUCache{cap: capacity,
        l: list.New(), m: make(map[int]*list.Element, capacity)}
}
func (c *LRUCache) Get(key int) int {
    if e, ok := c.m[key]; ok {
        c.l.MoveToFront(e); return e.Value.(*entry).val // 命中即提升 MRU
    }
    return -1
}

func (c *LRUCache) Put(key, val int) {
    if e, ok := c.m[key]; ok {      // 已存在：更新 + 前移
        e.Value.(*entry).val = val; c.l.MoveToFront(e)
        return
    }
    c.m[key] = c.l.PushFront(&entry{key, val})
    if c.l.Len() > c.cap {          // 插入后再逐最旧
        if e := c.l.Back(); e != nil {
            c.l.Remove(e); delete(c.m, e.Value.(*entry).key) // key 从节点取
        }
    }
}

复杂度

Get / Put 均 O(1)：哈希定位一次 + 链表常数次指针改写；空间 O(capacity)。并发不安全——工程外包 mutex 或分片。

面试节奏

① 白板先画结构图（上一页）② 报复杂度 ③ 再落代码。面试官常说「别用标准库」——那就切下一页的手写骨架，两版要都会。

Implement · Data Structure · LRU 缓存
标准库版是「能跑的参考答案」：结构体三个字段（cap、list、map）+ 两个方法，每个方法不超过三个动作。container/list 的环形哨兵原理展开在下一页——它解释了为什么边界处理零分支。右侧两段覆盖复杂度与面试节奏。

Implement I · Inside container/list

为什么 container/list 顺手：环形链表 + root 哨兵

环形双向链表：首尾相接，永远没有 nil 分支

// src/container/list/list.go（节选注释）
//       ┌────────────────────────────────┐
//       ▼                                │
//     root ──next──▶ e1 ──next──▶ e2 ────┘
//       ▲ ◀──prev────    ◀──prev──────
//
// root.next = 首元素(Front) · root.prev = 尾元素(Back)
// 空表：root.next = root.prev = &root

type Element struct {
    next, prev *Element
    list       *List
    Value      any      // 我们存 *entry
}
type List struct {
    root Element   // 哨兵，不存数据
    len  int
}

root 哨兵：零值即可用

&l.root 既是尾节点的 next 又是首节点的 prev——首尾相接成环，没有 nil、没有边界特判：空表、单节点、删头删尾走同一段指针赋值。

LRU 要的三个原语全部 O(1)

PushFront（进 MRU 位）· MoveToFront（命中提升，= Remove+PushFront）· Back+Remove（逐 LRU）。没有一次遍历——上一页三十行就是这么来的。

代价：Value 是 interface{}

取值要断言 e.Value.(*entry)（上一页 Get/Put 的写法）；不能随机访问第 k 个元素——前者靠「节点存 key」消化，后者 LRU 本就不需要。

易漏点自查：Get 命中后有没有 MoveToFront？Put 更新分支有没有前移？delete 用的 key 是不是从链表节点里取的？——这三处是 146 的三大 bug 高发区，写完先查这里。
Implement · Data Structure · LRU 缓存
环形哨兵与下一页手写版的 head/tail 双哨兵思想一致：哑节点 + 首尾相接消灭所有边界分支，MoveToFront 是 Remove+PushFront 的原语化。Value 断言是标准库版唯一比手写版啰嗦的地方——节点存 key 让淘汰反查免费。右侧三段覆盖哨兵、原语、代价。

Implement II · Hand-Rolled Doubly Linked List

实现二 · 手写双向链表：不用标准库

结构与 O(1) 原语：摘下 / 头插全靠改 4 个指针

type node struct {
    key, val   int
    prev, next *node
}
type LRUCache struct {
    cap        int
    m          map[int]*node
    head, tail *node // 两个哨兵，不存数据
}

func Constructor(capacity int) LRUCache {
    c := LRUCache{cap: capacity, m: map[int]*node{},
        head: &node{}, tail: &node{}}
    c.head.next, c.tail.prev = c.tail, c.head
    return c
}

func (c *LRUCache) remove(n *node) {
    n.prev.next, n.next.prev = n.next, n.prev
}
func (c *LRUCache) pushFront(n *node) {
    n.prev, n.next = c.head, c.head.next
    c.head.next.prev, c.head.next = n, n
}

Get / Put：原语的两套组合

func (c *LRUCache) Get(key int) int {
    n, ok := c.m[key]
    if !ok { return -1 }
    c.remove(n); c.pushFront(n) // 命中 → 提升 MRU
    return n.val
}
func (c *LRUCache) Put(key, val int) {
    if n, ok := c.m[key]; ok {
        n.val = val             // 更新也要前移！
        c.remove(n); c.pushFront(n)
        return
    }
    n := &node{key: key, val: val}
    c.m[key] = n
    c.pushFront(n)
    if len(c.m) > c.cap {       // 先插入再判超容
        last := c.tail.prev     // LRU = 尾哨兵前驱
        c.remove(last)
        delete(c.m, last.key)   // key 从节点取！
    }
}
写完自查五条：map 的 value 存 *node 指针 · 节点同时存 key 和 val · Get 命中要前移 · Put 更新分支要前移 · 判超容用 > 且放在插入后（cap=1 也无需特殊分支）。
Implement · Data Structure · LRU 缓存
手写版与标准库版操作一一对应，核心只有 remove 和 pushFront 两个 O(1) 原语——所有行为都是它们的组合。哨兵的回报：head/tail 两个哑节点让"摘头/摘尾/空表/单节点"全部退化成同一段指针赋值，没有 nil 判断，这正是 bug-free 的来源。五条易错点按出 bug 概率排序。

Runnable · LC 146 Official Example

完整可运行版：LC 146 官方序列实测

// import "fmt" · 承接上页的手写实现
func main() {
    c := Constructor(2)
    c.Put(1, 1)
    c.Put(2, 2)
    fmt.Println(c.Get(1)) // 1
    c.Put(3, 3)           // 容量满 → 逐出 key=2
    fmt.Println(c.Get(2)) // -1
    c.Put(4, 4)           // 逐出 key=1
    fmt.Println(c.Get(1)) // -1
    fmt.Println(c.Get(3)) // 3
    fmt.Println(c.Get(4)) // 4
}
// 输出：1 -1 -1 3 4

这段序列在验证什么

逐尾map 同步删

put(3,3) 时容量满，被逐出的是尾哨兵前驱（最久未使用的 key=2）；两次 get 返回 -1 证明逐出后 map 同步删除，不会命中「幽灵节点」——get(1) 从 1 变 -1 则证明 get/put 的前移都在生效。

本机实测（本 deck 代码均为实测）

go1.22.5 实测：container/list 版与手写双链表版对 LC 146 官方序列输出完全一致；另测两组边界——cap=1（插入即逐出，新 key 可正常命中）、put 更新前移（更新过的 key 不被误逐出），全部通过。

并发一句话：结构本身非线程安全——整体 mutex（正确、有争用）或按 key 哈希分片成 N 个小 LRU 降争用（groupcache 思路）；链表上做无锁复杂度不成正比，工程上不划算。
Implement · Data Structure · LRU 缓存
白板验收标准：15 分钟 bug-free 默写——用上一页五条易错点自查。这段官方序列覆盖"命中前移、逐尾、幽灵节点"三个考点；并发追问按 callout 档位答（先正确再快）。

Related & References

相关知识点与参考

结构底座（theory 系列）

哈希表 →（「点」能力的底座，本结构的另一半）
数组与链表 →（双链表摘插与哨兵的细节）
堆与优先队列 →（偷懒版淘汰序：O(log n) 的替代方案）
快速排序（手撕）→　跳表（手撕）→（本分类兄弟 deck）

Go 与工程近似

Go map 底层 →（哈希定位那一半的源码）
Redis 内存策略 →（采样近似 LRU / LFU 逐参数源码级）
OS 页面置换 →（Clock 二次机会：硬件做不起真 LRU）
缓存三大问题 →（LRU 在读路径里的位置）

参考来源（思路与写法可溯源至下列一手材料；本 deck 代码经 go1.22.5 编译运行验证）

LeetCode 146. LRU Cache / 460. LFU Cache题面约束（get/put O(1)）、容量语义与官方示例
src/container/list/list.go（Go 官方源码）环形双链表 + root 哨兵；MoveToFront / Remove / PushFront 均 O(1)
java.util.LinkedHashMap javadocaccessOrder 访问序与 removeEldestEntry 契约（Java 一行版）
redis.io · Key eviction + src/evict.c采样近似 LRU / LFU 参数——工程近似的展开在 Redis 内存策略 deck
本机 go1.22.5 实测container/list 版 + 手写双链表版：LC 146 官方序列、cap=1、put 更新前移全部一致通过
Implement · Data Structure · LRU 缓存
收尾互链：结构底座三条 + Go/工程四条。本 deck 是"结构设计与手撕层"；Redis 内存策略 / OS 页面置换是"工程近似层"（旧版 deck 的工程近似串讲、LFU 对比与 QA 深拆已归位到各系统 deck）。总页数 7。