再讲LRU时我们在拓展表里写下了一行LC.460 LFU缓存困难按“使用频次”淘汰频次相同再比时间。双哈希表key→节点频次→该频次下的双向链表并维护minFreq。这不是简单地把LRU再讲一遍——LFU是LRU的结构升级版LRU是“一条链表按时间排序”LFU是“一沓链表按频次分层层内再按时间排序”。先看两者并排对照LFU的结构就一目了然了LRULFU淘汰依据最近使用时间使用频次同频再比时间数据结构哈希表 一条双向链表哈希表 一沓双向链表每个频次一条层内顺序链表尾 最久未用某频次层的链表尾 该频次下最久未用命中后移到链表头从freq层摘下挂到freq1层头部淘汰时删链表尾删minFreq层的链表尾维护变量无minFreq复杂度O(1) / O(1)O(1) / O(1)一句话概括差异LRU是一条链表按时间排序LFU是一沓链表按频次分层层内再按时间排序。 题目速览30秒读懂实现LFU缓存LFUCache(capacity)初始化get(key)存在则返回值使用计数1否则返回−1put(key, value)已存在则更新值并计数1不存在则插入容量满时逐出使用计数最低的键若多个键计数相同逐出最久未使用的那个要求get和put都必须是O(1)平均时间复杂度。官方示例本机已逐步跑通LFUCache lfu new LFUCache(2); lfu.put(1, 1); lfu.put(2, 2); lfu.get(1); // 返回1 key1频次变2 lfu.put(3, 3); // 容量满逐出key2频次1 lfu.get(2); // 返回-1 lfu.get(3); // 返回3 key3频次变2 lfu.put(4, 4); // 逐出key1频次同为2但1更久未用 lfu.get(1); // 返回-1 lfu.get(3); // 返回3 lfu.get(4); // 返回4 核心思路三层结构 两条minFreq规则三层结构要做到get/put都是O(1)需要三层配合① key → value O(1)定位某个key的值 ② key → freq O(1)知道某个key的当前频次 ③ freq → 有序集合 O(1)在某频次层内插入/删除且保序能取到最久未用 ④ minFreq O(1)直接知道该淘汰哪一层Python里③用OrderedDictpopitem(lastFalse)取最旧的Java用LinkedHashSet。minFreq的维护唯一难点只有两条规则讲清楚代码就不会错淘汰之后minFreq必然回到1。因为新插入的key频次是1而它刚插入不会被立刻淘汰。get使某key从minFreq层升到minFreq1层时若该层空了minFreq要1。注意只加1——因为被升走的key只是从f到f1f1层本来就可能存在。️ 图解算法手把手走一遍官方序列以capacity 2为例操作返回freq1层旧→新freq2层freq3层minFreq说明put(1,1)—[1]——1插入规则1minFreq 1put(2,2)—[1, 2]——1key1在前 更久未用get(1)1[2][1]—1freq1层还剩key2非空⇒ minFreq不变put(3,3)—[3][1]—1容量满逐出freq1层最旧者key2get(2)−1[3][1]—1key2已被逐出get(3)3[][1, 3]—2freq1层空了⇒ 规则2minFreq升为2put(4,4)—[4][3]—1逐出minFreq2层最旧者key1与key3同频但更旧get(1)−1[4][3]—1key1已被逐出 ✓get(3)3[4][][3]1key4仍在freq1层所以minFreq不是 3get(4)4[][4][3]2freq1层空了 ⇒ minFreq升为2两行值得单独看第3行get(1)key1从freq1升到freq2但freq1层还剩key2非空所以minFreq保持1。这说明规则2的判定条件是“被移走的key原来所在的层在移走后是否为空”而不是“minFreq层是否还有其他元素”。第9行get(3)key3升到了freq3层但minFreq是1而不是3——因为key4还待在freq1层。minFreq反映的是全局最小频次不是刚被touch的那个key的频次。这两行是最容易把minFreq写错的地方。 代码实现Python JavaPython版fromcollectionsimportdefaultdict,OrderedDictclassLFUCache:def__init__(self,capacity:int):self.capcapacity self.min_freq0self.key_to_val{}# key → valueself.key_to_freq{}# key → 使用频次self.freq_to_keysdefaultdict(OrderedDict)# freq → 该频次下的所有keyOrderedDict保序先入 更久未用def_touch(self,key:int)-None:命中一个已存在的key频次1换到新层freqself.key_to_freq[key]delself.freq_to_keys[freq][key]# 从旧层摘下# 规则2若被移走的key原来所在的层空了min_freq要1ifnotself.freq_to_keys[freq]andself.min_freqfreq:self.min_freq1self.key_to_freq[key]freq1self.freq_to_keys[freq1][key]None# 挂到新层defget(self,key:int)-int:ifkeynotinself.key_to_val:return-1self._touch(key)returnself.key_to_val[key]defput(self,key:int,value:int)-None:ifself.cap0:returnifkeyinself.key_to_val:self.key_to_val[key]value self._touch(key)# 已存在更新值 频次1returniflen(self.key_to_val)self.cap:# 容量满逐出min_freq层的最旧者evict_key,_self.freq_to_keys[self.min_freq].popitem(lastFalse)delself.key_to_val[evict_key]delself.key_to_freq[evict_key]self.key_to_val[key]value self.key_to_freq[key]1self.freq_to_keys[1][key]Noneself.min_freq1# 规则1新插入后min_freq必然是1Java版importjava.util.*;classLFUCache{privatefinalintcap;privateintminFreq;privatefinalMapInteger,IntegerkeyToVal;privatefinalMapInteger,IntegerkeyToFreq;privatefinalMapInteger,LinkedHashSetIntegerfreqToKeys;publicLFUCache(intcapacity){this.capcapacity;this.minFreq0;this.keyToValnewHashMap();this.keyToFreqnewHashMap();this.freqToKeysnewHashMap();}privatevoidtouch(intkey){intfreqkeyToFreq.get(key);LinkedHashSetIntegersetfreqToKeys.get(freq);set.remove(key);// 规则2层空了且是minFreq层 ⇒ minFreq 1if(set.isEmpty()minFreqfreq){minFreq;freqToKeys.remove(freq);}keyToFreq.put(key,freq1);freqToKeys.computeIfAbsent(freq1,k-newLinkedHashSet()).add(key);}publicintget(intkey){if(!keyToVal.containsKey(key))return-1;touch(key);returnkeyToVal.get(key);}publicvoidput(intkey,intvalue){if(cap0)return;if(keyToVal.containsKey(key)){keyToVal.put(key,value);touch(key);return;}if(keyToVal.size()cap){LinkedHashSetIntegersetfreqToKeys.get(minFreq);intevictset.iterator().next();// LinkedHashSet第一个 最久未用set.remove(evict);keyToVal.remove(evict);keyToFreq.remove(evict);}keyToVal.put(key,value);keyToFreq.put(key,1);freqToKeys.computeIfAbsent(1,k-newLinkedHashSet()).add(key);minFreq1;// 规则1}}⚠️防坑提醒必看put一个已存在的key必须让频次1——只更新值会导致淘汰顺序全错。minFreq在层空时要1——漏掉会导致“淘汰到一个空层”而崩溃。容量为0的边界所有put直接返回get恒为−1。OrderedDict/LinkedHashSet的“最旧”在头部——Python用popitem(lastFalse)Java用iterator().next()别取反了。实测O(1)淘汰 vs 朴素扫最小实现2万次操作cap500010万次操作cap20000淘汰复杂度双哈希表 minFreq6.92ms45.54msO(1)朴素淘汰时扫最小频次1899.95ms61002.72msO(cap)10万次操作下快1340×而且差距随容量扩大而扩大cap5000 时275×cap20000时1340×——这正是O(1)与O(cap)的典型表现。 面试追问模拟提前准备惊艳全场Q1如果只要求O(logn)呢用一个按(freq, timestamp)排序的TreeSet即可代码短得多。面试里先给O(logn)版本再优化到O(1)是很舒服的节奏——既展示思路又留出优化空间。Q2LFU的“频次衰减”问题怎么处理纯LFU有个缺陷一个曾经被疯狂访问的老热点频次会一路涨到很高之后即使再无人问津也永不淘汰。真实系统如Redis的LFU用两个手段解决①对数计数器——频次不是真的累加而是按概率递增8位就能表示很大的访问量②衰减因子——定期把所有key的频次按半衰期衰减。这样老热点会随时间“冷却”。Q3get一个不存在的key要不要影响频次不要。同理put一个新key时频次从1起算而不是0——因为“刚被使用过一次”。Q4LFU与LRU在工程中怎么选LRU更适合访问模式变化快的场景热点会迁移LFU更适合热点稳定的场景如CDN的静态资源。真实系统常用混合策略或带衰减的LFURedis4.0的allkeys-lfu就是LFU对数计数器 概率衰减。 总结主题核心题目一句话收获原地哈希上LC.41 / LC.448值域 下标域时数组就是哈希表while条件要问“家里住的是不是我自己”原地哈希下LC.442 / LC.287归位结果两面读一句“不改数组”就能否决循环排序前缀和同余LC.560 / LC.974 / LC.523换个匹配键就是新题Java 取模不修正46% 用例会错前缀积的边界LC.238 / LC.152乘法没有可逆的减法有负数时状态要扩成 (max, min)矩阵技巧LC.48 / LC.54 / LC.73不模拟算下标旋转 转置 行翻转自己推导别背单调栈补完LC.84 / LC.42找更大用递减栈、找更小用递增栈接雨水最优解是双指针LFULC.460LRU 一条链表LFU 一沓链表 minFreq 四条通道速查表本周最实用的一张表通道适用信号写法要点代表题下标即哈希值域 ⊆[1,n]问“缺了谁 / 谁重复”while nums[nums[i]-1] ! nums[i]不是nums[i] ! i1LC.41 / 448 / 442坐标即映射二维结构问“变换后长什么样”先推导下标复合映射再写代码LC.48 / 54 / 73前缀即状态连续子数组的“和 / 积 / 模”问题匹配键 前缀或其模值有负数时窗口失效LC.560 / 974 / 523 / 238栈里存下标找“左右第一个更大 / 更小”找更大用递减栈、找更小用递增栈宽度 i − st[-1] − 1LC.84 / 42判断顺序看到中等题 → 先用这四条过一遍 → 都落空了再去借结构。 “前缀”手法的适用边界图场景运算逆运算序是否稳定前缀手法例题区间求和加法减法 ✅✅✅前缀和LC.560区间和取模加法 mod同余 ✅✅✅前缀和模 KLC.974 / 523区间求积禁除法乘法除法被禁✅⚠️左右两趟前缀积LC.238区间求积有0 / 负数乘法除以0无意义 ❌❌ 负数翻转❌失效换DPLC.152求最值有负数——❌❌换DP状态扩成 (max, min)LC.152一句话判断遇到“区间聚合”类问题先问这个运算可逆吗序稳定吗有一个答不上来就别硬套前缀。 心法第十一条心法十一想不出用什么结构时先看输入本身能不能当结构用我们习惯了“遇到问题 → 找一个数据结构装它”。但有一大类中等题答案不需要新容器下标即哈希值域落在[1,n]的数组位置i就是值i1的家坐标即映射矩阵的旋转、螺旋、置零本质是下标的代数运算前缀即状态把“扫过的部分”压成一个数栈里存下标信息全在原数组栈只存位置判断顺序是先用这四条过一遍都落空了再去借结构。但要注意原地解法赢在空间未必赢在时间。本周实测——LC.41的原地哈希比哈希集慢4~5倍LC.448的循环排序比哈希集慢3倍。面试官要的是O(1)空间你就写原地工程上求快哈希集可能更好。先确认你要优化的是哪个指标。附十一条心法速览#心法1先写暴力再谈优化2找单调性3空间换时间4DP的灵魂是状态设计5画表格是理解算法最快的方式6面试要“讲出来”7求方案用回溯求最值用DP能证明无后效性才用贪心8贪心不是“感觉对”是“能证明”9选型先问变不变 / 查什么 / 改不改区间10动手前先问这是不是一道数学题11想不出用什么结构时先看输入本身能不能当结构用 
长河君 · 2026/10/30 6:54:22 · 阅读 1.2k 高频必考！LFU缓存：把LRU的一条链表升级成一沓链表
再讲LRU时我们在拓展表里写下了一行LC.460 LFU缓存困难按“使用频次”淘汰频次相同再比时间。双哈希表key→节点频次→该频次下的双向链表并维护minFreq。这不是简单地把LRU再讲一遍——LFU是LRU的结构升级版LRU是“一条链表按时间排序”LFU是“一沓链表按频次分层层内再按时间排序”。先看两者并排对照LFU的结构就一目了然了LRULFU淘汰依据最近使用时间使用频次同频再比时间数据结构哈希表 一条双向链表哈希表 一沓双向链表每个频次一条层内顺序链表尾 最久未用某频次层的链表尾 该频次下最久未用命中后移到链表头从freq层摘下挂到freq1层头部淘汰时删链表尾删minFreq层的链表尾维护变量无minFreq复杂度O(1) / O(1)O(1) / O(1)一句话概括差异LRU是一条链表按时间排序LFU是一沓链表按频次分层层内再按时间排序。 题目速览30秒读懂实现LFU缓存LFUCache(capacity)初始化get(key)存在则返回值使用计数1否则返回−1put(key, value)已存在则更新值并计数1不存在则插入容量满时逐出使用计数最低的键若多个键计数相同逐出最久未使用的那个要求get和put都必须是O(1)平均时间复杂度。官方示例本机已逐步跑通LFUCache lfu new LFUCache(2); lfu.put(1, 1); lfu.put(2, 2); lfu.get(1); // 返回1 key1频次变2 lfu.put(3, 3); // 容量满逐出key2频次1 lfu.get(2); // 返回-1 lfu.get(3); // 返回3 key3频次变2 lfu.put(4, 4); // 逐出key1频次同为2但1更久未用 lfu.get(1); // 返回-1 lfu.get(3); // 返回3 lfu.get(4); // 返回4 核心思路三层结构 两条minFreq规则三层结构要做到get/put都是O(1)需要三层配合① key → value O(1)定位某个key的值 ② key → freq O(1)知道某个key的当前频次 ③ freq → 有序集合 O(1)在某频次层内插入/删除且保序能取到最久未用 ④ minFreq O(1)直接知道该淘汰哪一层Python里③用OrderedDictpopitem(lastFalse)取最旧的Java用LinkedHashSet。minFreq的维护唯一难点只有两条规则讲清楚代码就不会错淘汰之后minFreq必然回到1。因为新插入的key频次是1而它刚插入不会被立刻淘汰。get使某key从minFreq层升到minFreq1层时若该层空了minFreq要1。注意只加1——因为被升走的key只是从f到f1f1层本来就可能存在。️ 图解算法手把手走一遍官方序列以capacity 2为例操作返回freq1层旧→新freq2层freq3层minFreq说明put(1,1)—[1]——1插入规则1minFreq 1put(2,2)—[1, 2]——1key1在前 更久未用get(1)1[2][1]—1freq1层还剩key2非空⇒ minFreq不变put(3,3)—[3][1]—1容量满逐出freq1层最旧者key2get(2)−1[3][1]—1key2已被逐出get(3)3[][1, 3]—2freq1层空了⇒ 规则2minFreq升为2put(4,4)—[4][3]—1逐出minFreq2层最旧者key1与key3同频但更旧get(1)−1[4][3]—1key1已被逐出 ✓get(3)3[4][][3]1key4仍在freq1层所以minFreq不是 3get(4)4[][4][3]2freq1层空了 ⇒ minFreq升为2两行值得单独看第3行get(1)key1从freq1升到freq2但freq1层还剩key2非空所以minFreq保持1。这说明规则2的判定条件是“被移走的key原来所在的层在移走后是否为空”而不是“minFreq层是否还有其他元素”。第9行get(3)key3升到了freq3层但minFreq是1而不是3——因为key4还待在freq1层。minFreq反映的是全局最小频次不是刚被touch的那个key的频次。这两行是最容易把minFreq写错的地方。 代码实现Python JavaPython版fromcollectionsimportdefaultdict,OrderedDictclassLFUCache:def__init__(self,capacity:int):self.capcapacity self.min_freq0self.key_to_val{}# key → valueself.key_to_freq{}# key → 使用频次self.freq_to_keysdefaultdict(OrderedDict)# freq → 该频次下的所有keyOrderedDict保序先入 更久未用def_touch(self,key:int)-None:命中一个已存在的key频次1换到新层freqself.key_to_freq[key]delself.freq_to_keys[freq][key]# 从旧层摘下# 规则2若被移走的key原来所在的层空了min_freq要1ifnotself.freq_to_keys[freq]andself.min_freqfreq:self.min_freq1self.key_to_freq[key]freq1self.freq_to_keys[freq1][key]None# 挂到新层defget(self,key:int)-int:ifkeynotinself.key_to_val:return-1self._touch(key)returnself.key_to_val[key]defput(self,key:int,value:int)-None:ifself.cap0:returnifkeyinself.key_to_val:self.key_to_val[key]value self._touch(key)# 已存在更新值 频次1returniflen(self.key_to_val)self.cap:# 容量满逐出min_freq层的最旧者evict_key,_self.freq_to_keys[self.min_freq].popitem(lastFalse)delself.key_to_val[evict_key]delself.key_to_freq[evict_key]self.key_to_val[key]value self.key_to_freq[key]1self.freq_to_keys[1][key]Noneself.min_freq1# 规则1新插入后min_freq必然是1Java版importjava.util.*;classLFUCache{privatefinalintcap;privateintminFreq;privatefinalMapInteger,IntegerkeyToVal;privatefinalMapInteger,IntegerkeyToFreq;privatefinalMapInteger,LinkedHashSetIntegerfreqToKeys;publicLFUCache(intcapacity){this.capcapacity;this.minFreq0;this.keyToValnewHashMap();this.keyToFreqnewHashMap();this.freqToKeysnewHashMap();}privatevoidtouch(intkey){intfreqkeyToFreq.get(key);LinkedHashSetIntegersetfreqToKeys.get(freq);set.remove(key);// 规则2层空了且是minFreq层 ⇒ minFreq 1if(set.isEmpty()minFreqfreq){minFreq;freqToKeys.remove(freq);}keyToFreq.put(key,freq1);freqToKeys.computeIfAbsent(freq1,k-newLinkedHashSet()).add(key);}publicintget(intkey){if(!keyToVal.containsKey(key))return-1;touch(key);returnkeyToVal.get(key);}publicvoidput(intkey,intvalue){if(cap0)return;if(keyToVal.containsKey(key)){keyToVal.put(key,value);touch(key);return;}if(keyToVal.size()cap){LinkedHashSetIntegersetfreqToKeys.get(minFreq);intevictset.iterator().next();// LinkedHashSet第一个 最久未用set.remove(evict);keyToVal.remove(evict);keyToFreq.remove(evict);}keyToVal.put(key,value);keyToFreq.put(key,1);freqToKeys.computeIfAbsent(1,k-newLinkedHashSet()).add(key);minFreq1;// 规则1}}⚠️防坑提醒必看put一个已存在的key必须让频次1——只更新值会导致淘汰顺序全错。minFreq在层空时要1——漏掉会导致“淘汰到一个空层”而崩溃。容量为0的边界所有put直接返回get恒为−1。OrderedDict/LinkedHashSet的“最旧”在头部——Python用popitem(lastFalse)Java用iterator().next()别取反了。实测O(1)淘汰 vs 朴素扫最小实现2万次操作cap500010万次操作cap20000淘汰复杂度双哈希表 minFreq6.92ms45.54msO(1)朴素淘汰时扫最小频次1899.95ms61002.72msO(cap)10万次操作下快1340×而且差距随容量扩大而扩大cap5000 时275×cap20000时1340×——这正是O(1)与O(cap)的典型表现。 面试追问模拟提前准备惊艳全场Q1如果只要求O(logn)呢用一个按(freq, timestamp)排序的TreeSet即可代码短得多。面试里先给O(logn)版本再优化到O(1)是很舒服的节奏——既展示思路又留出优化空间。Q2LFU的“频次衰减”问题怎么处理纯LFU有个缺陷一个曾经被疯狂访问的老热点频次会一路涨到很高之后即使再无人问津也永不淘汰。真实系统如Redis的LFU用两个手段解决①对数计数器——频次不是真的累加而是按概率递增8位就能表示很大的访问量②衰减因子——定期把所有key的频次按半衰期衰减。这样老热点会随时间“冷却”。Q3get一个不存在的key要不要影响频次不要。同理put一个新key时频次从1起算而不是0——因为“刚被使用过一次”。Q4LFU与LRU在工程中怎么选LRU更适合访问模式变化快的场景热点会迁移LFU更适合热点稳定的场景如CDN的静态资源。真实系统常用混合策略或带衰减的LFURedis4.0的allkeys-lfu就是LFU对数计数器 概率衰减。 总结主题核心题目一句话收获原地哈希上LC.41 / LC.448值域 下标域时数组就是哈希表while条件要问“家里住的是不是我自己”原地哈希下LC.442 / LC.287归位结果两面读一句“不改数组”就能否决循环排序前缀和同余LC.560 / LC.974 / LC.523换个匹配键就是新题Java 取模不修正46% 用例会错前缀积的边界LC.238 / LC.152乘法没有可逆的减法有负数时状态要扩成 (max, min)矩阵技巧LC.48 / LC.54 / LC.73不模拟算下标旋转 转置 行翻转自己推导别背单调栈补完LC.84 / LC.42找更大用递减栈、找更小用递增栈接雨水最优解是双指针LFULC.460LRU 一条链表LFU 一沓链表 minFreq 四条通道速查表本周最实用的一张表通道适用信号写法要点代表题下标即哈希值域 ⊆[1,n]问“缺了谁 / 谁重复”while nums[nums[i]-1] ! nums[i]不是nums[i] ! i1LC.41 / 448 / 442坐标即映射二维结构问“变换后长什么样”先推导下标复合映射再写代码LC.48 / 54 / 73前缀即状态连续子数组的“和 / 积 / 模”问题匹配键 前缀或其模值有负数时窗口失效LC.560 / 974 / 523 / 238栈里存下标找“左右第一个更大 / 更小”找更大用递减栈、找更小用递增栈宽度 i − st[-1] − 1LC.84 / 42判断顺序看到中等题 → 先用这四条过一遍 → 都落空了再去借结构。 “前缀”手法的适用边界图场景运算逆运算序是否稳定前缀手法例题区间求和加法减法 ✅✅✅前缀和LC.560区间和取模加法 mod同余 ✅✅✅前缀和模 KLC.974 / 523区间求积禁除法乘法除法被禁✅⚠️左右两趟前缀积LC.238区间求积有0 / 负数乘法除以0无意义 ❌❌ 负数翻转❌失效换DPLC.152求最值有负数——❌❌换DP状态扩成 (max, min)LC.152一句话判断遇到“区间聚合”类问题先问这个运算可逆吗序稳定吗有一个答不上来就别硬套前缀。 心法第十一条心法十一想不出用什么结构时先看输入本身能不能当结构用我们习惯了“遇到问题 → 找一个数据结构装它”。但有一大类中等题答案不需要新容器下标即哈希值域落在[1,n]的数组位置i就是值i1的家坐标即映射矩阵的旋转、螺旋、置零本质是下标的代数运算前缀即状态把“扫过的部分”压成一个数栈里存下标信息全在原数组栈只存位置判断顺序是先用这四条过一遍都落空了再去借结构。但要注意原地解法赢在空间未必赢在时间。本周实测——LC.41的原地哈希比哈希集慢4~5倍LC.448的循环排序比哈希集慢3倍。面试官要的是O(1)空间你就写原地工程上求快哈希集可能更好。先确认你要优化的是哪个指标。附十一条心法速览#心法1先写暴力再谈优化2找单调性3空间换时间4DP的灵魂是状态设计5画表格是理解算法最快的方式6面试要“讲出来”7求方案用回溯求最值用DP能证明无后效性才用贪心8贪心不是“感觉对”是“能证明”9选型先问变不变 / 查什么 / 改不改区间10动手前先问这是不是一道数学题11想不出用什么结构时先看输入本身能不能当结构用