一文搞懂 LRU/LFU 缓存设计：O(1) 读写背后的结构拆解与手写实现要点

缓存淘汰策略的题面一句话就能说完：「设计一个支持 get 和 put 的缓存结构，容量满时按某种规则淘汰元素」。LRU（Least Recently Used）淘汰最久未使用的，LFU（Least Frequently Used）淘汰访问频次最低的。这是公认的面试「手写题之王」——不考你背过什么，只考你能否在压力下把几个基础结构拼出一个严丝合缝的整体。

它同时也是真正的工程问题：Redis 的内存淘汰、浏览器页面缓存、CDN 边缘节点、数据库的 buffer pool，本质都在回答同一个问题——「内存有限，谁该被请出去」。这篇文章把 LRU 和 LFU 的结构设计、O(1) 推导与手写实现一次讲透，并总结实现里最容易翻车的几个点。

问题背景：淘汰决策为什么必须 O(1)

先想清楚一个前提：淘汰决策发生在每一次写入的关键路径上。缓存存在的意义是把热点数据的访问从毫秒级（查库）压到微秒级（内存），如果每次 get/put 都要附带一次 O(n) 的扫描来「找最该淘汰的」，缓存本身就成了性能瓶颈——数据规模一大，还不如直接查库。

于是需求被精确刻画为：get 与 put 都必须 O(1)。哈希表能 O(1) 定位任意 key，这一半好办；难点在另一半——「谁最久没用」「谁频次最低」这类时间维度的次序信息，哈希表给不出来。要维护全局次序，自然想到链表；但单向链表删除中间节点得先 O(n) 找前驱，也过不了关。所以真正的答案是组合结构：哈希表负责 O(1) 定位，双向链表负责 O(1) 的次序调整——删除一个节点之所以能 O(1)，是因为节点里同时存了前后两个方向的指针，不需要找，直接摘。

思路推导：LRU 与 LFU 的结构设计

LRU：哈希表 + 双向链表。 双向链表按「最近使用」排序：头部是刚被访问的，尾部是最久未用的。再拆成原子动作：get 命中时，把节点从链中摘下、头插回去；put 已存在的 key，更新值并做同样两步；put 新 key 时头插入链，若超容量则把尾部节点摘除并从哈希表删除。摘除与头插都是纯指针操作 O(1)，配合哈希表 O(1) 定位，全程 O(1)。工程细节上用头尾哨兵节点把「链表为空」「只有一个节点」这些特判全部消掉——真实节点永远挂在两个哨兵之间，边界逻辑不复存在。

LFU：双哈希 + 频次桶。 LFU 难在两点：其一，频次是会变的，不能像 LRU 那样用一条静态链表维护次序；其二，频次相同的 key 淘汰谁？业界标准答案是平局时退化为 LRU——淘汰同频次里最久未使用的。O(1) 的经典设计用两个哈希表：第一张 key → (value, freq)，O(1) 定位元素；第二张 freq → 双向链表，每个频次一个桶，桶内链表按到达该频次的时间排序。访问一个 key 时，它从 freq 桶摘出、尾插进 freq+1 桶——注意同频桶内一个 key 只会被插入一次（因为每次访问都会升频离开），所以桶内顺序天然就是「最久未使用序」，平局规则被结构自动满足。再维护一个 minFreq 变量：新 key 进 1 号桶时 minFreq 重置为 1；发生升频或淘汰时若 minFreq 桶空了，minFreq 加一。淘汰时直接去 minFreq 桶取链表头，两个 O(1) 操作严丝合缝。

顺带一提工程现实：Redis 在数据量大时用的是近似 LRU——不维护全局链表，而是每个 key 记一个最近访问时钟，淘汰时随机采样一批取最旧的。原因是精确双向链表在多线程高并发下锁竞争激烈，采样方案牺牲少量精度换取实现简单与并发友好。算法题的「完美解」与工程的「合适解」有时并不一致，这是刷题之外的另一层认知。

实操代码：手写 LRU 与 LFU 完整实现

先写 LRU。注意每个节点必须同时持有 key，原因见文末避坑第一条：

python

class Node:
    """双向链表节点：必须持有 key，淘汰尾节点时才能反查哈希表"""
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: int = 0, value: int = 0):
        self.key, self.value = key, value
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map: dict[int, Node] = {}       # key -> 节点，O(1) 定位
        # 头尾哨兵：真实节点永远挂在中间，消灭所有空链表特判
        self.head, self.tail = Node(), Node()
        self.head.next, self.tail.prev = self.tail, self.head

    def _remove(self, node: Node) -> None:   # 从链中摘除，纯指针操作
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node: Node) -> None:  # 头插 = 标记为最近使用
        node.next, node.prev = self.head.next, self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if (node := self.map.get(key)) is None:
            return -1
        self._remove(node)
        self._add_front(node)                # 命中即提到最前
        return node.value

    def put(self, key: int, value: int) -> None:
        if (node := self.map.get(key)) is not None:
            node.value = value               # 更新已有 key：不占新容量
            self._remove(node)
            self._add_front(node)
            return
        if len(self.map) >= self.cap:        # 容量满，淘汰尾部（最久未用）
            last = self.tail.prev
            self._remove(last)
            del self.map[last.key]           # 链表与哈希表必须同步删
        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

再写 LFU。这里用「freq → 有序字典」代替「freq → 双向链表」，借助 Python 3.7+ 字典的插入有序性达到同样的桶内次序语义，逻辑更短：

python

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.kv: dict[int, tuple[int, int]] = {}          # key -> (value, freq)
        self.buckets: dict[int, dict] = defaultdict(dict)  # freq -> {key: value}
        self.min_freq = 0

    def _touch(self, key: int, value: int, freq: int) -> None:
        """访问一次：key 从 freq 桶升到 freq+1 桶"""
        self.kv[key] = (value, freq + 1)
        self.buckets[freq].pop(key, None)
        if not self.buckets[freq] and self.min_freq == freq:
            self.min_freq += 1                 # 桶空则最低频次上移
        self.buckets[freq + 1][key] = value    # 插到桶尾 = 同频里最近使用

    def get(self, key: int) -> int:
        if key not in self.kv:
            return -1
        value, freq = self.kv[key]
        self._touch(key, value, freq)
        return value

    def put(self, key: int, value: int) -> None:
        if self.cap <= 0:                      # 边界：容量为 0 直接拒绝
            return
        if key in self.kv:
            old_value, freq = self.kv[key]
            self._touch(key, value, freq)
            return
        if len(self.kv) >= self.cap:           # 淘汰最低频、同频最久未用
            bucket = self.buckets[self.min_freq]
            victim = next(iter(bucket))        # 桶内首个 = 最久未使用
            bucket.pop(victim)
            del self.kv[victim]
        self.kv[key] = (value, 1)
        self.buckets[1][key] = value           # 新 key 进 1 号桶
        self.min_freq = 1

复杂度与正确性推导：LRU 的 get/put 均为 O(1)，因为每个分支都只由「一次哈希定位 + 一次摘除 + 一次头插」组成；LFU 同为 O(1)——升频只动一个桶、淘汰只看 minFreq 桶头。正确性的关键在于前文推导过的结构性质：key 每被访问必然升频离开当前桶，所以同频桶内不存在重复插入，桶内顺序严格等于「到达该频次的时间序」，next(iter(...)) 取到的就是同频最久未使用者。空间两者均为 O(capacity)。边界条件：容量 0 或负数、put 覆盖已有 key（不得触发淘汰）、minFreq 桶空的时机，三处在上面代码里都有对应处理。

避坑总结

节点忘存 key 是最高频 bug。淘汰尾部节点时，要靠节点反查哈希表做同步删除；只存 value 的节点到了这一步就没辙，缓存与链表随即不一致，之后全是玄学错误。
put 更新已有 key 不走淘汰逻辑。更新不占新容量，写成「先查容量再覆盖」会在容量恰好满时错杀一个无辜 key。
LFU 的平局规则不能漏。「频次相同淘汰最久未使用」漏掉的话，面试官一眼就能判不合格；好在只要结构设计对了（每频次一桶 + 升频离桶），规则是被结构自动满足的，不需要额外时间戳。
minFreq 的维护时机要画图推一遍。它只在两处变化：新 key 入 1 号桶时置 1；旧 key 升频或被淘汰导致 minFreq 桶空时加一。漏掉后者，下一次淘汰就会去空桶里取节点。
按场景选近似算法。精确 O(1) 链表版是面试与中小规模的最优解；单机几十万级以上的高并发缓存，参考 Redis 的随机采样近似 LRU，用可接受的精度损失换掉锁竞争，往往才是正确的工程取舍。

写在最后

LRU 和 LFU 的设计过程示范了一个通用方法论：单一结构扛不住多维需求时，用组合结构把每一维分派给最擅长它的组件——哈希表管「定位」，链表管「次序」，频次桶管「分层」。看懂这一点，再遇到「O(1) 全栈最小」「O(1) 随机取删」这类变体题，都是同一套拼装手法的重新组合。

免责声明

本工具与文章内容仅用于学习测试场景，优化建议仅供参考，请勿直接用于生产环境，由此产生的风险自行承担。

一文搞懂 LRU/LFU 缓存设计：O(1) 读写背后的结构拆解与手写实现要点 ​

问题背景：淘汰决策为什么必须 O(1) ​

思路推导：LRU 与 LFU 的结构设计 ​

实操代码：手写 LRU 与 LFU 完整实现 ​

避坑总结 ​

写在最后 ​