文章目录
- 摘要
- 描述
- 题解答案
- 题解代码分析
- 节点需要存什么信息？
- 为什么要用「频次 → 双向链表」？
- LFUCache 的核心结构
- get 操作怎么做？
- put 操作的关键点
- 更新频次是整个设计的核心
- 示例测试及结果
- 与实际场景结合
- 时间复杂度
- 空间复杂度
- 总结
摘要
LFU 缓存是缓存算法里的“进阶关卡”。
LRU 大家都很熟，但 LFU 往往是很多人刷 LeetCode 时第一次真正感受到：
“原来 O(1) 的设计不是写得快，而是数据结构选得对。”
这道题不只是让你写一个缓存，而是在逼你回答三个工程级问题：
- 怎么在 O(1) 内找到最少使用的 key？
- 使用次数相同时，怎么再按 LRU 淘汰？
- get / put 都要是 O(1)，不能靠排序、遍历硬撑。
描述
题目要求你实现一个 LFUCache，支持：
get(key)- 存在：返回 value，并且使用次数 +1
- 不存在：返回 -1
put(key, value)key 已存在：更新 value，并且使用次数 +1
key 不存在：
如果缓存没满，直接插
如果缓存满了：
- 先淘汰使用次数最少
- 如果次数相同，淘汰最久没用的
并且有一个非常重要的硬指标：
get和put的平均时间复杂度必须是O(1)
这直接排除了所有“排序 / 每次扫描一遍”的方案。
题解答案
真正能跑通并满足 O(1) 的解法，核心是三层结构：
- key → Node 映射
- freq → 双向链表 映射
- 一个全局的minFreq
一句话总结：
用 HashMap 快速定位节点，用「频次分桶 + LRU 链表」来控制淘汰顺序。
题解代码分析
节点需要存什么信息？
每一个缓存项，至少要知道：
- key
- value
- 当前使用频率 freq
- 在链表里的前后指针（为了 O(1) 删除）
classNode{letkey:Intvarvalue:Intvarfreq:Int=1varprev:Node?varnext:Node?init(_key:Int,_value:Int){self.key=keyself.value=value}}为什么要用「频次 → 双向链表」？
因为 LFU 有一个隐藏条件：
同一个频次下，要按 LRU 淘汰
所以每个频次桶，本质上是一个LRU 链表。
classDoublyLinkedList{lethead=Node(0,0)lettail=Node(0,0)varsize=0init(){head.next=tail tail.prev=head}funcaddToHead(_node:Node){node.next=head.next node.prev=head head.next?.prev=node head.next=node size+=1}funcremove(_node:Node){node.prev?.next=node.next node.next?.prev=node.prev size-=1}funcremoveLast()->Node?{guardsize>0,letlast=tail.prev,last!==headelse{returnnil}remove(last)returnlast}}LFUCache 的核心结构
classLFUCache{privateletcapacity:IntprivatevarminFreq=0privatevarkeyToNode=[Int:Node]()privatevarfreqToList=[Int:DoublyLinkedList]()keyToNode：O(1) 找节点freqToList：O(1) 找某个频次的 LRU 链表minFreq：O(1) 知道该淘汰谁
get 操作怎么做？
核心逻辑只有三步：
- 查 key 是否存在
- 从旧 freq 链表中移除
- freq +1，放进新链表
funcget(_key:Int)->Int{guardletnode=keyToNode[key]else{return-1}updateFreq(node)returnnode.value}put 操作的关键点
capacity 为 0，直接返回
key 已存在：更新 value + 更新 freq
key 不存在：
如果满了：
- 从
minFreq对应的链表里，删最久未使用
- 从
插入新节点，freq = 1
funcput(_key:Int,_value:Int){ifcapacity==0{return}ifletnode=keyToNode[key]{node.value=valueupdateFreq(node)return}ifkeyToNode.count==capacity{ifletlist=freqToList[minFreq],letremoved=list.removeLast(){keyToNode.removeValue(forKey:removed.key)}}letnewNode=Node(key,value)keyToNode[key]=newNodeletlist=freqToList[1]??DoublyLinkedList()list.addToHead(newNode)freqToList[1]=list minFreq=1}更新频次是整个设计的核心
privatefuncupdateFreq(_node:Node){letfreq=node.freqifletlist=freqToList[freq]{list.remove(node)iffreq==minFreq&&list.size==0{minFreq+=1}}node.freq+=1letnewList=freqToList[node.freq]??DoublyLinkedList()newList.addToHead(node)freqToList[node.freq]=newList}这里做了三件事：
- 从旧频次链表移除
- 如果刚好是 minFreq 且链表空了，更新 minFreq
- 插入新频次链表头部
示例测试及结果
letlfu=LFUCache(2)lfu.put(1,1)lfu.put(2,2)print(lfu.get(1))// 1lfu.put(3,3)print(lfu.get(2))// -1print(lfu.get(3))// 3lfu.put(4,4)print(lfu.get(1))// -1print(lfu.get(3))// 3print(lfu.get(4))// 4输出结果：
1 -1 3 -1 3 4和题目示例完全一致。
与实际场景结合
LFU 在真实项目里比你想象中常见，比如：
- CDN 本地缓存
- App 内图片 / 数据缓存
- 后端热点数据保护
- 推荐系统中的候选集缓存
相比 LRU，LFU 更适合：
“长期高频访问的数据，不能因为短期冷却就被干掉”
比如用户主页、配置数据、热门商品列表。
时间复杂度
get：O(1)put：O(1)
这是通过HashMap + 双向链表 + minFreq联合保证的。
空间复杂度
O(capacity)所有节点、链表总数都和缓存容量线性相关。
总结
LFU 这道题，真正难的不是代码多，而是：
- 你能不能拆清楚“频次”和“时间”这两个维度
- 你能不能在 O(1) 下把这两个维度同时维护住
如果你能完整写出这道题，其实已经具备了：
- 设计复杂缓存系统的能力
- 面试中讲清楚“为什么这样设计”的底气
- 把算法真正落地成工程代码的经验
