想象你是一座博物馆的馆长。博物馆只有一面精美的展墙，最多同时挂 5 件展品，但仓库里有成百上千件藏品。每天游客来来往往，有的展品被人围着看，有的则冷清落灰。你的工作就是决定：当展墙满了、又有人想展出新藏品时，撤下哪一件？ 有的馆长偷懒，最久没被游客围观的展品先撤——这叫“最近最少使用”（LRU）。有的馆长较真，给每件展品挂一个小计数器，统计累计参观人次，人最少的先撤——这叫“最不经常使用”（LFU）。两种撤展哲学各有拥趸，也各有翻车现场：LRU 可能被一次“只逛不买”的旅行团带偏，LFU 则可能让昔日网红展品永远占着 C 位。 现实世界中的 CPU 缓存、数据库缓冲池、Redis 内存、大模型 KV Cache，都在上演同样的“撤展难题”。这篇内容，就是带你逛遍这座“缓存博物馆”，看懂 LRU 与 LFU 的底层逻辑、进阶变体与工程实战。

岗位关联

面试必考的“缓存三兄弟”之一，是系统设计与性能优化的基本功。理解 LRU/LFU 的取舍，你才能在日常开发中正确地给 Redis、Caffeine 选对淘汰策略，也能在系统设计面试中讲出让人信服的缓存方案。

目录
  1. 可视化演示
  2. 缓存基础概念
  3. LRU 核心原理
  4. LRU 工程实现
  5. LFU 核心原理
  6. LRU 变体演进
  7. 策略对比分析
  8. 工业应用实践
  9. 调优与落地
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示LRU双向链表淘汰最近最少使用、LFU频率桶淘汰最不经常使用、以及两种策略命中率对比分析。

本节配有交互动效（进入视口后自动加载，约 3KB）。

LRU最近最少使用替换策略 双向链表维护访问顺序，访问数据时移动到链表头部，缓存满时淘汰尾部元素 哈希表+双向链表实现O(1)读写，最近访问的数据保留在靠近头部的位置 access(x): moveToHead(x) | evict: removeTail() LRU基于时间局部性假设最近访问的更可能再次访问

缓存基础概念

博物馆的展墙之所以存在，是因为游客等不及去仓库一件件翻藏品——把热门展品挂在眼前，大多数人一眼就能看到。计算机世界也一样：CPU 的速度比磁盘快几个数量级，如果每次读数据都去磁盘翻找，程序会慢得让人抓狂。于是我们在中间加一层“展墙”，也就是缓存（Cache），把最常用的数据放在离 CPU 近的地方。

但展墙面积总是有限的。内存再大，也装不下整个磁盘的数据；缓存再快，也容不下所有热点。这就逼着馆长制定“撤展规则”：满的时候该撤谁？这套规则，就是缓存替换策略（Cache Replacement Policy）。它回答一个核心问题：当缓存容量耗尽，新数据想进来，谁给谁让位？

评价一个撤展规则好不好，最直观的指标是命中率（Hit Rate）——游客想看的展品正好挂在墙上的比例。命中率越高，说明展墙上的东西越对游客胃口，系统性能越好。

回到博物馆：展墙就是缓存，仓库就是磁盘，游客的每一次“想看哪件”就是一次数据访问请求。明白了这个舞台，接下来就该看两位馆长——LRU 和 LFU——如何各显神通了。

hit rate=HH+M\text{hit rate} = \frac{H}{H + M}
命中率就是“游客想看的展品恰好挂在墙上”的次数，除以游客总共想看展品的次数。H 是命中次数（Hit），M 是未命中次数（Miss）。
  1. 分子 H（命中次数）游客想看一件展品，抬头一看——墙上正好挂着，直接欣赏。这次请求就算“命中”。
    H\text{H}
  2. 分母 H + M（总请求次数）命中的加上没命中的，就是游客提出看展需求的总次数。
    H + M\text{H + M}
  3. 两者相除（命中比例）命中次数占总次数的比例。90% 的命中率意味着 100 次看展需求里有 90 次不用去仓库翻。
    HH+M\frac{H}{H + M}

LRU 核心原理

LRU 馆长有一个朴素的生活经验：游客刚看完的展品，往往还会再来看一眼——比如一幅名画，有人看完发朋友圈，朋友也想来打卡。这叫时间局部性（Temporal Locality）：刚被访问的数据，很可能在不久的将来再次被访问。反过来说，很久没人看的展品，大概率会继续冷下去。

于是 LRU 馆长定下规矩：每次有人看某件展品，就把它的名字记到小本子的最末尾；当展墙满了要撤展时，就撤掉小本子最开头的那个——也就是最久没被访问的展品。LRU 的全称 Least Recently Used，翻译过来就是“最近最少使用”：注意，它看的不是“用了多少次”，而是“多久没用了”。

要用代码实现这个“小本子”，光靠一个列表不够——每次访问都要把名字从中间挪到末尾，数组挪动是 O(n) 的。聪明的做法是用一条“时间链”：把所有展品按访问时间排成一队，队尾是最新被看的，队头是最久没被看的。每次访问就把对应展品从当前位置摘下来，挂到队尾。这样“谁最久没被看”一目了然。

LRU 的优点是一眼看透：实现简单、应对突发热点（比如某个新闻突然爆了）反应极快，刚看完马上又看，必然命中。但它的命门也明显：如果有一批数据只是“一次性路过”（比如顺序扫描全表），它们会一路把真正热门的展品挤出展墙，这就是著名的缓存污染。馆长一时偷懒，没想到旅行团一来，展厅就乱了。

victim=arg⁡min⁡k∈C  t(k)\text{victim} = \arg\min_{k \in C} \; t(k)
这条公式是 LRU 的“撤展判决书”：在所有缓存项 C 中，选出最后访问时间 t(k) 最小的那个 k，把它淘汰掉。
  1. 集合 C（缓存中的所有数据项）代表当前挂在展墙上的全部展品。
    CC
  2. t(k)（数据项 k 的最后访问时间）每件展品都记着一个“上次被看的时间戳”，例如 t（名画）=10:30 表示它 10 点 30 分刚被看过。
    t(k)t(k)
  3. arg min（取最小值对应的那个对象）不是要最小值本身，而是要“哪个展品”的 t(k) 最小——也就是最久没被看的那一件。
    arg⁡min⁡k∈Ct(k)\arg\min_{k \in C} t(k)

LRU 工程实现

LRU 馆长要把“小本子”落成真正的制度，需要两件工具：一个哈希表（HashMap）用来快速定位展品在小本子上的位置，一条双向链表（Doubly Linked List）用来记录展品的新旧顺序。哈希表像“展品名牌柜”——每个名牌对应一个抽屉，抽屉里存着指向链表节点的指针；双向链表则像一串手拉手排队的人，每个人都知道自己前面是谁、后面是谁。

为什么必须用双向链表而不是单向的？因为撤展（删除节点）时，需要知道“前一位是谁”才能把链重新接上。单向链表想找前驱必须从头遍历，又退化成 O(n)。有了前驱指针，摘除任意节点的操作就变成了常数时间：让前一位直接指向后一位，握手改道即可。

规定制度后，get（看展）和 put（挂新展品）的流程是这样的：get 时先用哈希表 O(1) 找到节点，如果存在，把它从链表当前位置摘除并挂到末尾，表示“刚被看过”；put 时若 key 已存在同样移到末尾，若不存在则新建节点挂到末尾，若此时展墙已满，就从链表头部摘掉最久没被看的那件，同时删掉哈希表里对应的名牌。

这套“名牌柜 + 手拉手队列”的制度，就是面试中常考的 LRU Cache 标准实现。你已经掌握了 LRU 的底牌，接下来看看另一位馆长 LFU 是怎么用计数器治理展厅的。

Tget(n)=O(1),Tput(n)=O(1)T_{\text{get}}(n) = O(1), \quad T_{\text{put}}(n) = O(1)
get 和 put 的时间复杂度都是常数级 O(1)——不管缓存里有 10 条还是 1000 万条数据，每次操作的耗时都差不多，这正是哈希表 + 双向链表组合的威力。
  1. T_get(n) = O(1)看展操作分三步：哈希表找名牌 O(1)、链表摘除节点 O(1)、挂到末尾 O(1)，每步都是常数时间，与缓存总量 n 无关。
    Tget(n)=O(1)T_{\text{get}}(n) = O(1)
  2. T_put(n) = O(1)挂新展品同样走哈希表和链表操作；就算要撤展，也只需动链表头部一个节点。
    Tput(n)=O(1)T_{\text{put}}(n) = O(1)
  3. 哈希表与链表的分工哈希表负责“找得到”，链表负责“排得序”，两者通过指针桥接，缺一不可。这就是 O(1) 的关键所在。
    HashMap→ListNode\text{HashMap} \rightarrow \text{ListNode}

LFU 核心原理

LFU 馆长信奉另一条经验：有些展品天生就是“常青树”，比如博物馆的镇馆之宝，每天都有大量游客专程为它而来，累计参观人次遥遥领先。与其盯着“最后一次观看时间”，不如给每件展品挂一个计数器，记录累计被访问次数（Frequency）。当展墙满了，撤下计数器数字最小的那件——这叫最少使用（Least Frequently Used）。

LFU 的依据是频率局部性（Frequency Locality）：过去被频繁访问的数据，未来大概率还会被频繁访问。这个思路对“稳定热点”非常友好：一个 key 只要长期热门，它的计数器就会滚雪球一样涨上去，几乎不可能被淘汰。不像 LRU，热点数据一旦短暂休息（比如隔了几分钟没被访问），就可能被后来的“一次性数据”挤掉。

但 LFU 也有自己的麻烦。每件展品的计数器不是一成不变的，“最小频率”这个数字在动态变化中，如果每次淘汰都扫描全展厅找最小值，复杂度就是 O(n)。工业级实现用了一种“频率桶”的结构：用频率值做桶的编号（freq=1 一个桶，freq=2 一个桶……），每个桶里是一条双向链表，再维护一个变量 minFreq 指向当前最小的非空桶。这样找最小值永远 O(1)——直接看 minFreq 指着的桶就行。

LFU 的脾气也很鲜明：对稳定热点极其忠诚，但在“访问模式突变”时反应迟钝。比如一款过气的网红展品，计数器已经攒到 1000，虽然现在每天只有零零散散几个人看，它却因为“历史功勋”迟迟不肯让位。这就是 LFU 的“老臣困境”，也催生了一代代 LRU 变体去修补这些问题。

victim=arg⁡min⁡k∈C  f(k),同频时取最久未用\text{victim} = \arg\min_{k \in C} \; f(k), \quad \text{同频时取最久未用}
LFU 的撤展判决书：在缓存项 C 中，选出累计访问频率 f(k) 最小的那件淘汰；如果有多件频率相同，再按“谁更久没被访问”决出胜负。
  1. f(k)（数据项 k 的累计访问频率）每件展品的小计数器，每被看一次就 +1，代表累计人气。
    f(k)f(k)
  2. arg min f(k)（最小频率对应的对象）在展厅里找到计数器数字最小的展品，它就是撤展候选人。
    arg⁡min⁡k∈Cf(k)\arg\min_{k \in C} f(k)
  3. 同频次次级规则两个展品都是 3 次参观，怎么办？回退到 LRU 逻辑，撤下“更久没被看”的那件。这保证了规则没有歧义。
    tie-break:min⁡kt(k)\text{tie-break}: \min_{k} t(k)

LRU 变体演进

LRU 怕“一次性污染”，LFU 怕“旧热点赖着不走”。于是后续的学者像一代代馆长，不断改良撤展规则。LRU-K 的思路很直接：一件新展品刚来时先别急着上展墙，放进“候选区”观察；只有被访问满 K 次，才证明它是真热门，允许进入正式展厅。K 通常取 2，意思是“连续来看两次才算真爱”，一次性路过的人根本污染不了展墙。

ARC（Adaptive Replacement Cache，自适应替换缓存） 则更聪明：它维护两条 LRU 队列——一条保护“最近新来的”（Recency），一条保护“频繁到访的”（Frequency），并且有一个自适应调节器，根据实际命中情况动态调整两条队列的容量比例。如果最近访问模式占上风，就给新客队列多分点空间；如果老客户更活跃，就给常客队列多分点空间，两边都不吃亏。

TinyLFU 把 LFU 的计数器做成了“概率草图”（Count-Min Sketch）：用一小块内存配合多个哈希函数，近似估计每个 key 的访问频率，把空间开销压到极致。它还引入频率衰减机制：每隔一段时间，把所有计数器统一减半，让历史人气“降温”，老热点不再永远霸榜。W-TinyLFU（Window TinyLFU）是 Caffeine 缓存的默认策略，它把缓存分成“窗口区”和“主区”，新数据先进窗口区观察，防止 LRU 式的突发数据直接冲击主区。

变体的本质，是在“短期新宠”和“长期人气”之间做平衡。理解了这层博弈，你看 ARC 的 T1/T2 双队列、TinyLFU 的衰减窗口，都会觉得它们是在同一个方向上不断打磨。下一节，我们把 LRU 和 LFU 放到擂台上正面对比。

ck≥K⇒k 进入正式缓存c_k \ge K \quad \Rightarrow \quad k \text{ 进入正式缓存}
LRU-K 的入场券：候选数据 k 的累计访问次数 c_k 达到阈值 K 时，才被允许放入正式缓存。K=1 时退化为普通 LRU，K 越大，对“一次性访问”的抵抗力越强。
  1. c_k（候选数据 k 的访问计数）新展品在候选区挂了本小本子，每被游客看一眼就记一笔。
    ckc_k
  2. K（阈值，通常取 2）馆长定的“真爱标准”。K=2 表示要连续被看两次才够格上展墙，防止旅行团路过造成的虚假繁荣。
    KK
  3. 条件判定（≥）当 c_k 达到或超过 K，数据从候选区晋升到正式缓存。这是 LRU-K 与普通 LRU 最核心的区别——多了个“试用期”。
    ck≥Kc_k \ge K

策略对比分析

现在让 LRU 馆长和 LFU 馆长同台竞技。第一回合——命中率：如果访问模式是“突发型”（比如新闻热点突然涌入，随后降温），LRU 胜，因为刚访问的数据立刻留在队尾，短时间内再次访问必命中；LFU 则因为计数器还没攒起来，可能误杀刚热起来的新数据。如果访问模式是“稳定热点型”（比如数据库里经常被查的某几行），LFU 胜，计数器会把真正的常客牢牢锁在缓存里。

第二回合——实现复杂度：LRU 只需哈希表 + 双向链表，代码量少，心智负担低；LFU 需要频率桶、minFreq 变量、多级链表，代码复杂度和出错概率都更高。在内存开销上，两者都是 O(n) 的空间复杂度——每个缓存项都要存指针或频率信息，但 LFU 的常数因子通常更大（多了个频率桶映射）。

选谁，本质上取决于你了解你的访客吗？如果业务是“热点相对固定”，LFU 是可靠的老管家；如果业务是“流量忽高忽低、新内容不断涌现”，LRU 反应更快。这也是为什么工业界往往不直接二选一，而是用变体混合两者——这正是下一节 Redis 和 Caffeine 的做法。

SLRU(n)=O(n),SLFU(n)=O(n)S_{\text{LRU}}(n) = O(n), \quad S_{\text{LFU}}(n) = O(n)
两者的空间复杂度都是 O(n)：缓存有 n 条数据，就需要 n 份节点/映射元数据。差异只在常数项——LFU 每个节点要多存一个频率计数和桶指针。
  1. S_LRU(n) = O(n)LRU 每个缓存项对应一个链表节点 + 一个哈希表条目，总共 n 份，线性增长。
    SLRU(n)=O(n)S_{\text{LRU}}(n) = O(n)
  2. S_LFU(n) = O(n)LFU 同样每个 key 有节点和哈希条目，外加频率桶结构，总量仍是 n 的线性函数。
    SLFU(n)=O(n)S_{\text{LFU}}(n) = O(n)
  3. 常数因子的差别虽然量级相同，LFU 的“每件展品”要多挂一个计数器和桶编号，实际占用内存略高。
    O(n) 同阶，常数不同O(n) \text{ 同阶，常数不同}

工业应用实践

Redis 是缓存届的“连锁博物馆分馆”，它的内存就是展墙，但展品数量经常动辄上千万。Redis 没有用教科书式的精确 LRU——维护完整双向链表在千万级 key 上代价太高——而是用近似 LRU：当内存达到 maxmemory 上限时，随机采样若干 key（默认 5 个），从样本中挑出最久没被访问的那个淘汰。采样数越大，淘汰结果越接近真正的 LRU，但性能开销也越大，这就是 maxmemory-samples 参数的意义。

Java 生态的 Caffeine 缓存则采用了更前沿的 W-TinyLFU。它把缓存分成三块：窗口区（Window）、试用区（Probation）、保护区（Protected）。新数据先进窗口区，攒够频率后晋升到保护区；窗口区满了用 LRU 淘汰，主区满了则比较“候选数据的频率”和“被淘汰数据的频率”，频率高者留下。这套机制同时吸收了 LRU 的抗突发能力和 LFU 的热点识别能力。

工程实践的智慧是“够用就好”：精确 LRU 在教科书里很美，但千万级数据下采样近似更实惠；W-TinyLFU 结构复杂，但能显著提升长尾场景的命中率。真正落地时，参数调优和监控指标是绕不开的最后一公里。

P=1−(1−mN)nP = 1 - \left(1 - \frac{m}{N}\right)^n
Redis 近似 LRU 的采样公式：从 N 个 key 中随机采样 n 个，m 是其中“真正的冷数据”数量，那么这 n 个样本里至少包含一个冷数据的概率就是 P。n 越大，精准淘汰冷数据越容易。
  1. (1 - m/N)随机抽一个 key，它“不是冷数据”的概率——展厅里 N 件展品，m 件是冷门，抽到非冷门的概率就是这部分。
    1−mN1 - \frac{m}{N}
  2. n 次方（采样 n 个全不是冷数据）连续抽 n 个 key 全都不是冷数据的概率。采样越多，全不中的概率指数级下降。
    (1−mN)n\left(1 - \frac{m}{N}\right)^n
  3. 1 减去（至少命中一个冷数据）用 1 减掉上面的“全不中”概率，就是采样中至少逮到一个冷数据的概率。Redis 用户调高 maxmemory-samples，就是在提高这个 P。
    1−(1−mN)n1 - \left(1 - \frac{m}{N}\right)^n

调优与落地

无论选哪种策略，落地都要先回答三个问题：我的访问模式是什么？容量设多大合适？怎么判断策略是否有效？识别访问模式是第一步：如果是电商大促，流量陡增陡降，LRU 系更抗冲击；如果是日志分析、热榜排名，热点稳定，LFU 系命中率更漂亮。可以用一段时间的访问日志离线重放，对比不同策略的命中率再拍板。

容量规划方面，缓存不是越大越好——内存有成本，而且容量大到一定程度，命中率增长会变得非常平缓。监控指标上，别只盯着命中率：驱逐数（Evictions）、平均访问延迟、缓存项的平均生存时间，都是判断策略健康度的信号。命中率突然下跌，可能是访问模式变了，也可能是缓存容量被调小了。

TinyLFU 的频率衰减给了我们一个重要的调优启示：任何“历史战绩”都应该随时间贬值。现实中，一个曾经的爆款视频，半年后热度归零，如果它的计数器还高悬榜首，就会长期霸占缓存位置。定期把计数器减半，相当于“翻篇”——让新的热点有机会冒头。这个思想也可以用到你自己的缓存设计里：给每条缓存加“新鲜度权重”，让旧数据逐步让位。

走到这里，你已经在“缓存博物馆”里逛完了全部展厅：从 LRU 和 LFU 的底层原理，到实现细节、变体演进，再到工业实践和调优心法。现在我们把目光从博物馆移回你的代码——看看这些策略在真实 AI 场景里如何为你效力。

fnew=⌊fold2⌋f_{\text{new}} = \left\lfloor \frac{f_{\text{old}}}{2} \right\rfloor
TinyLFU 的衰减公式：每隔固定周期，把所有 key 的访问频率都除以 2（向下取整）。老热点的人气每周期“腰斩”一次，不可能永远占着 C 位。
  1. f_old（衰减前的访问频率）展品当前计数器上的数字，可能是历史积累的 100 次，也可能是 3 次。
    foldf_{\text{old}}
  2. 除以 2（人气腰斩）把计数器砍半。100 次变 50 次，3 次变 1 次。历史越久，被砍得越狠，新秀的数据相对占比就上来了。
    fold2\frac{f_{\text{old}}}{2}
  3. 向下取整（⌊ ⌋）除出来的小数直接舍掉，保证计数器永远是整数。1 次减半后变成 0，意味着“彻底归零”的过期热点可以被正常淘汰。
    ⌊fold2⌋\left\lfloor \frac{f_{\text{old}}}{2} \right\rfloor

AI 应用场景

大模型推理的 KV Cache 管理

阶段：模型推理优化

解决的问题：大语言模型生成每个 token 时都要计算注意力，KV Cache（键值缓存）存放历史 token 的 Key 和 Value 张量。上下文很长时 KV Cache 会占满 GPU 显存，传统做法只能粗暴截断历史，导致模型“失忆”。用 LRU 变体管理 KV Cache，可以让模型优先保留最近讨论的关键信息，显存满了就淘汰最久远的历史 token，兼顾长对话能力和显存上限。

具体案例：某公司做超长文档问答，上下文窗口 32K，每请求需缓存约 2GB 的 KV 张量。引入 LRU 式 KV Cache 淘汰策略后，把上下文上限提到 128K，同时显存占用不变，长文档关键信息的召回率提升约 18%。

推荐系统的热点特征缓存

阶段：特征工程与在线服务

解决的问题：推荐系统每一路请求都要读取用户画像、物品 Embedding 等特征，特征存储远在数据库中，直接读延迟太高。用 LFU 策略缓存高频热门物品的特征——因为热门物品被推荐给大量用户、命中频率极高，LFU 能确保它们的特征长期驻留内存，冷门物品的特征则来去匆匆，把宝贵内存留给真正的顶流。

具体案例：某短视频推荐系统，使用 Caffeine 的 W-TinyLFU 缓存物品特征，容量 10 万条。上线后特征平均读取延迟从 5ms 降到 0.3ms，缓存命中率稳定在 92% 以上，推荐服务整体 P99 延迟下降 40%。

Redis 加速 AI 模型的重复计算

阶段：模型推理降本

解决的问题：图像分类、文本向量化等 AI 服务经常收到大量重复输入（比如同一张商品图被反复识别）。用 Redis 做推理结果缓存，设置 maxmemory-policy=allkeys-lru，让最近调用过的推理结果留在内存里，相同输入直接返回缓存结果，省掉一次昂贵的 GPU 推理。

具体案例：一个 OCR 识别服务用 Redis 缓存识别结果，容量 2GB，LRU 淘汰策略。由于同一批证件照片会被多系统反复调用，缓存命中率达到 85%，GPU 推理调用量下降 70%，直接省下三张推理卡的预算。

Python 演示

python68 行
# -*- coding: utf-8 -*-"""缓存替换策略演示: LRU 与 LFU 命中率对比"""from collections import OrderedDict  class LRUCache:    """哈希表 + 双向链表(OrderedDict)实现 LRU, get/put 均为 O(1)"""     def __init__(self, capacity):        self.cap = capacity        self.data = OrderedDict()     def get(self, key):        if key not in self.data:            return -1        self.data.move_to_end(key)  # 刚访问过, 移到链表末尾(最新)        return self.data[key]     def put(self, key, value):        if key in self.data:            self.data.move_to_end(key)  # 已存在则先移到末尾        self.data[key] = value        if len(self.data) > self.cap:            self.data.popitem(last=False)  # 淘汰最久未用的队头  class LFUCache:    """简化版 LFU: 用字典存 (value, freq), 淘汰时找最小频率"""     def __init__(self, capacity):        self.cap = capacity        self.data = {}  # key -> (value, freq)     def get(self, key):        if key not in self.data:            return -1        val, f = self.data[key]        self.data[key] = (val, f + 1)  # 计数器 +1        return val     def put(self, key, value):        if key in self.data:            _, f = self.data[key]            self.data[key] = (value, f + 1)            return        if len(self.data) >= self.cap:            victim = min(self.data, key=lambda k: self.data[k][1])  # 频率最小者            del self.data[victim]        self.data[key] = (value, 1)  def simulate(cache, keys):    hits = 0    for k in keys:        if cache.get(k) != -1:            hits += 1        else:            cache.put(k, 1)    return hits / len(keys)  if __name__ == "__main__":    # 模拟一段访问流: 前面是顺序扫一遍, 后面反复访问热点 A/B    stream = list("ABCDEFABGACHABD")    lru_hit = simulate(LRUCache(5), stream)    lfu_hit = simulate(LFUCache(5), stream)    print("LRU hit rate:", round(lru_hit, 3))    print("LFU hit rate:", round(lfu_hit, 3))
目的：用 Python 实现简化版 LRU 和 LFU 缓存，在同样的访问序列上模拟运行，计算各自命中率，直观感受两种策略的差异。
  1. self.data = OrderedDict()用 Python 的 OrderedDict 同时充当“哈希表 + 双向链表”：既能 O(1) 按 key 查找，又保持插入顺序，move_to_end 相当于把节点移到链表尾部。
  2. self.data.move_to_end(key)每次 get 都把 key 挪到末尾，保证“末尾 = 最近访问”，队头自然就是“最久未用”。
  3. self.data.popitem(last=False)弹出 OrderedDict 的第一个元素，即淘汰 LRU 语义下最久没被访问的 key。
  4. self.data[key] = (val, f + 1)LFU 的计数器 +1：同一 key 每被访问一次，元组里的频率 f 就递增。
  5. victim = min(self.data, key=lambda k: self.data[k][1])遍历所有 key，按频率值找出最小的那个，作为淘汰对象。教学简化版是 O(n)，工业版用频率桶优化到 O(1)。
  6. if cache.get(k) != -1:模拟一次访问：get 返回 -1 表示未命中缓存，需要走 put 把数据放进缓存；返回具体值则命中，计数器加一。

常见误区

误区“LRU 名字里有 Least Recently Used，那不就是把用得最少的那个 key 淘汰掉吗？跟 LFU 应该差不多吧？”很多初学的人会把 LRU 和 LFU 混为一谈，以为都是看“次数”。

正解LRU 看的是时间——“最后一次访问距今多久”，不是次数。一个 key 被访问了 1000 次，但只要最后一次访问在很久以前，LRU 照样可能淘汰它；另一个 key 只被访问过 1 次，但只要刚访问完，它就排在链表末尾很安全。就像博物馆里一件展品曾经万人空巷，但半年没人看了，LRU 馆长依然会把它撤下来。

为何常见：“Least Recently Used“ 中的 ”Recently“（最近）指的是时间维度，但中文翻译”最近最少使用“里的”少“字容易让人联想到次数，加上和 LFU 的 ”Frequently”（频繁）摆在一起，概念就混淆了。

误区“LFU 记住了每个 key 的访问频率，信息比 LRU 多，命中率肯定更高，所以无脑用 LFU 就行。”

正解不存在绝对更优的策略，只有“更适合某种访问模式”的策略。如果业务有大量“一次性扫描”（比如数据分析里遍历全表），LFU 的新数据计数器都是 1，很容易被误杀，而 LRU 能保住刚访问的数据；反过来在稳定热点场景 LFU 明显更强。RocksDB、Guava Cache 等真实系统之所以提供多种策略，正是因为访问模式千差万别。

为何常见：人容易觉得“信息越多越聪明”，忽略了 LFU 的历史包袱——老热点计数器高企不下、新热点难以冒头，以及衰减机制带来的额外复杂度。

误区“我写个 Python 列表，每次 get 把 key 删掉再 append 到末尾，pop(0) 淘汰头部，这不就是 LRU 吗？挺简单的呀。”

正解列表的 append 是 O(1)，但“把中间的 key 删掉再插入末尾”是 O(n) 的操作——因为在数组里删除中间元素需要把后续所有元素往前挪。只有在每个节点都有“前驱/后继指针”的双向链表中，摘除任意节点才是 O(1)。真正的 LRU 实现必须是“哈希表定位 + 双向链表摘除”的组合，才能在千万级数据下保持稳定性能。

为何常见：初学者写小规模 demo 时 n 很小，O(n) 和 O(1) 看不出区别，很容易误以为列表实现“够用”，到大规模生产环境才暴露问题。

误区“Redis 设置了 maxmemory-policy=allkeys-lru，它就会严格按照 LRU 顺序淘汰最久没用的 key，和教科书写的一样。”

正解Redis 实际用的是近似 LRU——不维护全局链表，而是在内存满时随机采样 N 个 key（默认 5 个），从样本里挑最久未用的淘汰。N 越大越接近真实 LRU，但 CPU 开销越高。Redis 官方文档明确说这是“近似 LRU 算法”，通过 maxmemory-samples 参数在“精度”和“性能”之间找平衡。

为何常见：配置项名字就叫 "lru"，用户很容易认为它就是教科书里的 LRU；而且 Redis 官方也默认用这个策略，很少有人去读源码或文档的细节说明。

面试题

Q1. LRU 缓存淘汰数据时，选择哪个 key 作为淘汰对象？

单选题 · easy

  • A.访问次数最少的 key
  • B.最近最少被访问的 key← 正确答案
  • C.数据体积最大的 key
  • D.创建时间最早的 key

答案：B。LRU 的定位是“Least Recently Used“，即最久没被访问的 key。它关注的是”最后访问时间“而非”访问次数”——那是 LFU 的职责。选项 A 是 LFU 的规则，C、D 与 LRU 无关。

Q2. 下列哪种数据结构组合是 LRU 的标准高效实现？

单选题 · easy

  • A.数组 + 二分查找
  • B.哈希表 + 双向链表← 正确答案
  • C.红黑树 + 队列
  • D.哈希表 + 数组

答案：B。哈希表负责 O(1) 定位 key 对应的节点，双向链表负责 O(1) 摘除任意节点并移动位置。数组删除中间元素是 O(n)，所以 D 不行；红黑树 O(log n) 性能不如 O(1)；二分查找依赖有序性，无法维护访问顺序。

Q3. LFU 缓存的核心淘汰依据是什么？

单选题 · easy

  • A.最后访问时间
  • B.数据写入时间
  • C.累计访问频率← 正确答案
  • D.访问延迟

答案：C。LFU 的全称是 Least Frequently Used，淘汰累计访问频率最低的 key。它统计“来过几次”，而非“多久没来”。选项 A 是 LRU 的规则。

Q4. 一个基于“哈希表 + 双向链表”的 LRU 缓存，get 与 put 操作的时间复杂度分别是多少？

单选题 · mid

  • A.O(log n) 和 O(log n)
  • B.O(1) 和 O(n)
  • C.O(n) 和 O(n)
  • D.O(1) 和 O(1)← 正确答案

答案：D。get 由哈希表定位 O(1)，链表摘除+移动也是 O(1)；put 的查找、插入、淘汰头部同样是常数时间。整个操作链每一环都是 O(1)，因此 get 与 put 均为 O(1)，与缓存大小 n 无关。

Q5. 关于 Redis 的近似 LRU，下列说法正确的是？

单选题 · mid

  • A.Redis 维护全局双向链表实现精确 LRU
  • B.Redis 随机采样若干 key 并从样本中淘汰最久未用的← 正确答案
  • C.Redis 默认采样 100 个 key
  • D.近似 LRU 一定比精确 LRU 命中率高

答案：B。Redis 为控制内存与 CPU 开销，采用近似 LRU：随机采样 maxmemory-samples（默认 5）个 key，从中淘汰最久未用的。采样数越大越接近精确 LRU，但性能开销更高，因此 A 错误、C 错误；近似通常是精度换性能，不会比精确命中率高，D 错误。

Q6. LRU-K 算法中，K 的作用是什么？

单选题 · mid

  • A.K 表示缓存容量的大小
  • B.K 表示内存中维护的链表条数
  • C.K 表示数据被访问多少次后才允许进入正式缓存← 正确答案
  • D.K 表示频率衰减的周期

答案：C。LRU-K 的核心思想是给新数据设“试用期”：累计访问次数达到 K（通常取 2）才进入正式缓存，防止一次性扫描的数据污染缓存。K 不是容量、链表条数或衰减周期，因此其余选项错误。

Q7. 以下哪些属于 LFU 工业级实现（O(1) 版本）需要的核心组成部分？

多选题 · mid

  • A.频率到节点链表的映射（频率桶）← 正确答案
  • B.记录当前最小频率的变量 minFreq← 正确答案
  • C.按频率排序的平衡二叉树
  • D.key 到节点的哈希表映射← 正确答案

答案：ABD。LFU 的 O(1) 实现用“频率桶 + 双向链表 + 哈希表”：桶记录每个频率对应的节点链，minFreq 快速定位最小频率桶，哈希表实现 O(1) 查节点。平衡二叉树是 O(log n) 方案，不是 O(1) 的核心组件，因此 C 不选。

Q8. 关于 ARC（自适应替换缓存）的特点，描述最准确的是？

单选题 · mid

  • A.它只使用一个 LRU 队列，不做区分
  • B.它维护两条 LRU 队列并动态调整容量比例← 正确答案
  • C.它完全放弃 LRU，改用 LFU 计数
  • D.它要求所有数据必须先被访问 K 次

答案：B。ARC 维护“最近访问”和“频繁访问”两条 LRU 队列，用自适应算法根据命中情况动态调整两条队列的容量比例：突发模式多给新客队列，热点模式多给常客队列。A 把 ARC 降级成普通 LRU，C 和 D 分别混入了 LFU 和 LRU-K 的思路。

Q9. TinyLFU 中“频率衰减”机制的主要目的是什么？

单选题 · hard

  • A.降低哈希冲突的概率
  • B.让历史人气不断贬值，给新热点让位← 正确答案
  • C.减少计数器占用的内存
  • D.提升缓存写入的速度

答案：B。衰减机制定期把计数器除 2，例如旧热点从 100 万降到 50 万再降到 25 万，历史战绩逐步缩水，新的高频 key 才有机会竞争缓存名额。它不直接改变哈希冲突、内存占用或写入速度，因此其余选项错误。

Q10. W-TinyLFU 缓存将存储空间划分为哪几个区域？

多选题 · hard

  • A.窗口区（Window）← 正确答案
  • B.试用区（Probation）← 正确答案
  • C.保护区（Protected）← 正确答案
  • D.溢出区（Overflow）

答案：ABC。W-TinyLFU 是 Caffeine 默认策略，三段结构：新进数据先入窗口区，窗口淘汰后进入试用区；试用区的数据若被再次访问则晋升到保护区，保护区淘汰的数据再回到试用区竞争。不存在“溢出区”，因此 D 不选。