如何实现 LRU-K 缓存？
题目与使用场景
实现一个固定容量的 LRU-K 缓存，支持 get、put 和淘汰。每个键记录最近 K 次访问；访问次数不足 K 次的条目属于历史不足区，应先于“已热”条目淘汰。需要说明 K、容量、更新已有键、并发调用和不存在键的行为。
面试官考察什么
- 能否准确维护访问历史与两类候选集合。
- 是否能用堆、哈希表或有序结构维持淘汰顺序，并分析复杂度。
- 能否处理重复写入、容量为零、K 非法和并发可见性。
- 是否理解 LRU-K 的目标是过滤一次性扫描，不等于所有工作负载都更快。
作答前的澄清问题
确认是否要求线程安全、是否允许近似淘汰、值是否可变、是否需要 TTL，以及是否要统计命中率。若要求严格顺序，通常需要锁或串行化更新；若追求吞吐，可采用分片和近似策略。
30 秒回答框架
我会为每个键保存值、最近 K 次时间戳和版本。候选分为历史不足区与已热区：容量超限时先淘汰历史不足区中最久未访问者，否则淘汰已热区中第 K 近时间最小者。哈希表负责 O(1) 定位，堆保存候选顺序，更新堆时用版本号丢弃过期节点。严格实现的 get 和 put 期望 O(log n)，空间 O(capacity·K)。
分步骤深入解答
1. 记录访问历史
每次命中或写入都追加逻辑时钟值，并只保留最近 K 次。逻辑时钟比墙上时间更适合比较顺序，也避免同一毫秒访问难以区分。已有键的 put 应更新值并计为一次访问，除非题目明确要求写入不计访问。
2. 维护淘汰候选
历史不足区的排序键是最近一次访问时间；已热区的排序键是第 K 近访问时间。两个最小堆分别存 (key, version, rank)。键再次访问时插入新节点并增加版本，弹出时验证版本和当前 rank，失效节点直接跳过。
3. 边界与并发
容量为零或负数时不缓存；K 为零或负数时应拒绝参数。淘汰和值更新必须在同一临界区内完成，避免两个线程同时看到空位而超容量。分片锁能提高吞吐，但跨分片的全局容量需要额外协调。
高质量示范回答
我先把条目分成历史不足和已热两区。每个条目保存值、最近 K 次逻辑时间与版本；访问更新历史后，把新排序节点压入对应最小堆。淘汰时先检查历史不足堆，再检查已热堆，并用版本校验跳过旧节点。这样定位是哈希表 O(1)，每次堆操作 O(log n)，空间为 O(capacity·K)。测试会覆盖 K=1 与普通 LRU 的等价性、重复访问晋级、一次性扫描、覆盖写、容量零、并发超容量、堆中失效节点和命中率。LRU-K 适合希望降低扫描污染的场景；Redis 的 LRU 是采样近似，PostgreSQL 使用 clock-sweep，不能把三者的复杂度和效果混为一谈。
常见错误
- 只维护一次访问时间，实际实现成普通 LRU。
- 把第 K 近访问时间误写成最近一次访问时间。
- 直接删除堆顶却不处理重复节点，导致错误淘汰或内存泄漏。
- 允许并发
put突破容量，或在锁外更新访问历史。 - 声称 LRU-K 在所有负载下都优于 LRU。
追问及应对
K=1 时应该发生什么？
每个条目第一次访问就进入已热语义，淘汰键按最近一次访问排序，因此退化为普通 LRU 的排序规则。
如何降低堆节点的内存成本？
可用索引和可变堆减少重复节点，或采用分代队列、采样淘汰等近似方案，但要明确顺序从严格变为近似，并重新测试命中率。
如何验证一次性扫描污染是否降低？
构造循环热点集合后插入大批只访问一次的键，比较 LRU 与 LRU-K 的热点命中率、淘汰数量、延迟和内存占用；同时测试热点集合大小接近容量的边界。