LRU和LFU缓存淘汰策略有什么区别?如何实现?
哪些公司问过
答案要点
- LRU 淘汰最久未访问的,LFU 淘汰访问频率最低的
- LRU:哈希表 + 双向链表,get/put O(1)
- LFU:key→节点哈希 + 频率→链表哈希 + 最小频率,O(1)
- LRU 易被批量扫描污染;LFU 保留长期热点,但有历史热点难淘汰问题
- LFU 常配合计数衰减,工程上有 Redis 近似 LRU/LFU、Caffeine 的 W-TinyLFU
易错点
- LRU 用单链表或数组实现,移动节点变成 O(n)
- LFU 同频率时不处理先后顺序
- 不提 LFU 的历史热点和冷启动问题
面试官常见追问
- 缓存的插入、更新、删除时间复杂度分别是多少?
- Redis 的 LRU 是精确的吗?
- 为什么 LRU 要用双向链表而不是单向链表?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。