LeetCode 146. LRU 缓存：设计题的爷爷，O(1) 的组合艺术

题目：O(1) 的 get 与 put

LRU 缓存——哈希+双向链表的组合艺术

LeetCode 146：设计 LRU（最近最少使用）缓存，支持 get(key) 与 put(key, value)，两个操作都必须 O(1)——容量超限时淘汰「最近最少使用」的项。「必须 O(1)」是这道题的灵魂——它直接否定了朴素解法。

朴素解法的失败：数组或链表存数据，记录访问时间戳，淘汰时找最旧的——get 是 O(1)（哈希）、但「找最旧淘汰」是 O(n)；有序结构（按时间排序）——「找最旧」是 O(1)（尾部），但「找 key」是 O(n)——每种单一结构都缺一块——这就是设计题的入口：单一数据结构无法满足，必须组合。

组合：哈希表 + 双向链表

各取所长：哈希表负责「key → 节点」的 O(1) 定位（「跳到节点」）；双向链表负责「节点的有序维护」——按访问时间排序：最新访问的放头部、最旧的在尾部——「淘汰」是 O(1)（删尾节点）、「访问后提到头」也是 O(1)（摘下节点插到头）——「双向」是关键：O(1) 摘除任意节点需要前驱指针（单向链表摘除节点要知道前驱——遍历找前驱是 O(n)——双向链表解决了「O(1) 摘除」——这就是为什么必须是双向链表。

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}                    # key -> Node
        self.head = Node()               # 哨兵头
        self.tail = Node()               # 哨兵尾
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node):             # O(1) 摘除
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node):          # O(1) 头插
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev, self.head.next = node, node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node); self._add_front(node)   # 访问即提到头
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.value = value
            self._remove(node); self._add_front(node)
            return
        if len(self.map) >= self.cap:                # 淘汰尾部
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

graph TD
    A[哈希表: key → 节点<br/>O(1) 定位] --> B[双向链表: 按访问时间排序<br/>O(1) 摘除任意节点]
    B --> C[get: 定位 → 摘除 → 头插]
    B --> D[put: 满容量淘汰尾节点]
    E[哨兵节点 head/tail<br/>消除边界判空] --> B

实现细节的三个坑

坑一：哨兵节点（dummy head/tail）。链表的头插、尾删都要处理「空链表」「只有一个节点」的边界——「哨兵节点」消除所有边界判断：永远有一个假头和假尾——真实节点永远在中间——「remove」与「add_front」不再有任何 if——哨兵是链表设计的标准技巧——Code 更短、bug 更少。坑二：删除淘汰节点时同步删哈希表。淘汰链表尾节点时，哈希表里的 key 也要 del——忘删=内存泄漏+脏读（get 已淘汰的 key 返回旧值）——「淘汰是两件事」：链表摘除+哈希删除——这也是 Node 里要存 key 的原因（淘汰时需要 key 来删哈希——「反向引用」的设计动机）。坑三：访问与更新的语义。put 一个已存在的 key——既是更新也是「访问」——要提到头部（LRU 的「最近使用」包括写入）——「写入算不算访问」是语义题——LRU 的定义里算——面试时要与面试官确认语义（有的变体「写入不重置位置」——「确认语义」是设计题的加分动作**。

LRU 在真实系统中的存在

Redis 的 LRU：Redis 的内存淘汰策略之一（maxmemory-policy allkeys-lru——「Redis 的 LRU 是近似 LRU」：真正的 LRU 要全局链表（Redis 的实现是「采样近似」：随机采样 N 个 key，淘汰其中最久未用的——「近似 LRU」的性能取舍（全局链表的锁开销——「工程中的近似」与「算法题的精确」——Redis 用 24bit 的 lru 字段记录时钟（「精度与成本的折衷」——近似 LRU 的效果在实测中接近精确——「工程决策」：够用就好。操作系统的页面置换：LRU 是页面置换算法的理论最优之一（「理论 LRU 不可实现」（需要全局时间戳——操作系统用 「时钟算法」（Clock）近似 LRU（引用位+循环指针——「二次机会（Second Chance）」——「算法理论 → 工程近似」的又一次实践。面试的延伸问题：「LFU 与 LRU 的区别」（460 题 LFU——按频率而非时间——「频率 vs 时间」的淘汰哲学——LRU 的问题：偶发的一次访问把冷数据救活——LFU 的缺点：历史热点赖着不走——「两种淘汰」各有失败场景——「考试刷题、工作看面试题库」**的类比。

LRU 的进阶：Redis 的淘汰策略与「LFU 对比」

LRU 的进阶：Redis 的完整淘汰策略与 LFU 的深度对比。「Redis 的八种淘汰策略」：「maxmemory 触发时」的策略选择——「noeviction」（默认：内存满拒绝写——「拒绝写的场景」（缓存拒绝写、持久数据不允许丢——「allkeys-lru vs volatile-lru」（全 keys vs 有 TTL 的 keys——「volatile 的语义」（只淘汰设了过期时间的——「allkeys-random / volatile-random」（随机淘汰——「随机淘汰」的场景（不关心热度的均匀淘汰——「volatile-ttl」（越快过期越先淘汰——「ttl 策略」的业务语义——「四种 lfu/volatile-lfu」（Redis 4.0+ 的 LFU——「LFU 在 Redis」的实现。「Redis 的近似 LFU」：「Morris 计数器」的对数计数（「logc 字段」（8bit 的对数计数——「概率递增」（访问次数的计数是概率性的（「counter += 1 的概率」随计数下降——「对数计数」的空间效率——「lfu-decay-time」（衰减因子（「时间衰减」的模拟——「老热点」的降权——「LFU 的衰减」解决「历史热点赖着不走」——「LFU vs LRU 的场景对比」：LRU 的问题（「偶发扫描」（一次全量扫描把热数据全挤出——「scan 的问题」——LFU 的优点（「累积频率」抗偶发——「LFU 的问题」（「新热点」上升慢——「两种策略」的失败场景互补——「策略的选择」按业务（「偶发扫描多」选 LFU、「新鲜度敏感」选 LRU。「设计题的延伸」：「LFU（LeetCode 460）的手写」（双层结构（频率桶 + 同频链表——「频率桶」（freq → 节点链（「minFreq」的追踪——「O(1) 的四个操作」（get/put/inc/dec——「手写 LFU」比 LRU 难一档——「难度在于」频率变化时的桶迁移。LRU 的进阶总结：Redis 八策略（noeviction/volatile/allkeys/lfu 组合）+近似 LFU（Morris 计数+衰减）+LFU/LRU 的失败场景互补+手写 LFU 的双层结构——「淘汰策略」是「缓存系统」的核心设计——「LRU 的思想」从算法题延伸到 Redis 与操作系统——「同一思想的多层实现」——算法层的精确、工程层的近似——「近似的智慧」：够用且高效。

LRU 的高频问答：结构选型、时序陷阱与并发安全

问题一：为什么必须是双向链表？单向链表或「数组加哈希」不行吗？——刚性需求是「O(1) 摘除任意节点」：摘除要先知道前驱，单向链表找前驱只能从头遍历 O(n)，双向链表把前驱存在节点自己身上，摘除才降到 O(1)。那「数组 + 哈希（key → 下标）」呢？定位没问题，但「把访问过的元素移到头部」在数组里意味着 O(n) 的整体搬移——「有序维护」这半边职责数组接不住。所以结论不是「双向链表更好」，是「只有双向链表同时满足摘除与重排两个 O(1)」——数据结构选型永远是需求倒推结构，不是个人偏好；面试里把「哪个操作逼出了双向」讲清楚，比背结论高一档。

问题二：put 满容量时的时序有没有坑？——有，而且是手写 LRU 最常见的错误来源：必须先判「key 已存在」再判「容量满」——已存在的 key 走「更新值 + 提头」，绝不能触发淘汰，否则会把别的 key 错误逐出、还留下脏哈希；淘汰只发生在「新 key 且已满」这一支。淘汰本身是两步动作：链表摘尾 + 哈希删除，漏掉哈希删除就是内存泄漏加脏读（get 已淘汰的 key 会命中旧节点，返回不存在的数据）。再配两个防御习惯：Node 里冗余存 key（淘汰时要用它删哈希——反向引用的设计动机）与哨兵头尾节点（空链表、单节点的边界分支全部消失）。这三处——时序、双删、哨兵——就是白板手写的完整自查清单，按这个顺序过一遍，十分钟内代码基本无 bug。

问题三：多线程环境下这份实现能直接用吗？——不能。get 的「摘除 + 头插」、put 的「淘汰 + 插入」都是多步操作，并发交错会让链表断链、重复淘汰甚至丢数据。工程上的三条路：粗粒度互斥锁（整个缓存一把锁，正确但吞吐上不去）；分段锁（按 key 哈希分片、各片独立加锁，老版本 ConcurrentHashMap 的思路）；无锁化缓冲（Caffeine 的方案：读写先落本地缓冲队列，异步批量应用到淘汰结构，牺牲一点淘汰的实时精度换吞吐）。Redis 则用「单线程命令执行 + 采样近似」从根上绕开竞态——它不做精确 LRU 的原因之一就是不想为一把全局链表锁付出代价。面试的高分动作是主动说出「这份实现在并发下不安全」并给出改造方向——单线程正确性与多线程安全性是两个独立的考察维度，主动跨界讨论说明你见过真实系统，而不只是刷过题。

问题四：LRU 的容量按「条数」还是按「字节」？工程实现有什么差别？——算法题按条数（key-value 对的个数），工程缓存几乎都按字节——内存预算是真实的约束，「一条 1MB 的值」和「一条 1KB 的值」占用的资源差一千倍。按字节淘汰意味着 put 时除了「淘汰最旧」，还要处理单条超限的拒绝策略（过大值直接拒绝、或写入方拆分）；Redis 按「进程内存用量」触发淘汰、Memcached 按 slab class 预分配内存，都是「容量度量单位」决定淘汰逻辑形状的实例。面试被追问「怎么支持按字节淘汰」时，答「链表节点加 size 字段、淘汰时从尾部累计回撤到预算以内」就能过关——算法题的「容量」是抽象数字，工程的「容量」是稀缺资源，这个差别贯穿所有缓存设计题。

小结

LRU 缓存的完整解析：题目灵魂（get/put 都要 O(1)——单一结构做不到——组合是设计题的解法）；组合方案（哈希表 O(1) 定位 + 双向链表 O(1) 有序维护——「双向」是 O(1) 摘除的前提——哨兵节点消除边界）；三个实现坑（哨兵消除判空、淘汰要同步删哈希（Node 存 key 的动机）、put 已存在 key 要提头）；真实系统（Redis 的近似 LRU——采样+24bit 时钟、操作系统的 Clock 算法——「精确理论 → 工程近似」的普遍规律）；面试延伸（LFU 对比、写入语义的确认）。给面试者的建议：LRU 的手写要练到「十分钟白板无 bug」——它是「考官看你代码功底」的试金石——链表的指针操作 + 哈希的配合 + 边界的处理，一次手写全暴露——练熟 LRU，设计的面试就赢了一半。

LRU 之于设计题，正如两数之和之于哈希表——它们是各自领域的「第一课」，而且这一课的内容，在 Redis 与操作系统里以各种近似形态活着。