第 285 题：实现推荐结果的缓存策略，LRU与LFU的混合。
题目
实现推荐结果的缓存策略，LRU与LFU的混合。
完整讲解
一、推荐结果缓存的需求
- 同一用户短时间内的推荐请求可能重复（如刷新、多端）；缓存可降低延迟与算力。缓存策略需在命中率、新鲜度与存储成本间权衡；LRU 与 LFU 各有优劣，混合可兼顾。
二、LRU（Least Recently Used）
- 规则：淘汰最久未访问的项。实现：双向链表 + 哈希表，访问时移到头，满时删尾。特点：对「最近用过」友好，适合有明显时间局部性的请求；但对突发流量或扫描会挤出热点。
- 复杂度：读写 O(1)；实现简单，生产常用。
三、LFU（Least Frequently Used）
- 规则：淘汰访问次数最少的项。实现：按频次分桶（如 1次、2次…），每桶内可再 LRU；或小堆 + 哈希。特点：保护热点、抗扫描；但新项易被淘汰（冷启动差），历史热点会长期占位。
- 复杂度：更新频次与淘汰需谨慎实现，可 O(1) 或 O(log n) 取决于结构。
四、混合策略
- LRU + LFU 混合：如两级缓存，L1 用 LRU（小、热）、L2 用 LFU 或 LRU；或单 cache 用「加权分」：score = α·recency + β·frequency，按 score 淘汰。也可 TinyLFU：用 Count-Min Sketch 近似频次，定期衰减，再结合 LRU 窗口避免新项立刻被淘汰。
- 推荐场景：key 常为 (user_id, 场景, 版本)；TTL 可设较短（如分钟级）保证一定新鲜度；大 key（列表）可压缩或只缓存 top 部分。混合策略可提高命中率并减轻缓存污染。
面试要点
- 能说清 LRU 与 LFU 的规则、实现要点与优缺点（LRU 重时间局部性，LFU 重频次、冷启动差）。
- 能说明混合思路：两级 LRU+LFU、加权分、TinyLFU；以及推荐场景的 key 设计与 TTL。
记忆要点
- LRU：淘汰最久未用，O(1)；LFU：淘汰频次最低，护热点但冷启动差。
- 混合：两级、加权 score、TinyLFU；推荐可 key=user+场景、短 TTL。