# 1. 缓存替换策略的复杂度与实现代价中 LRU（哈希+双向链表 O(1)）、LFU（频次桶 O(1)）、ARC（四链表 O(1)）、W-TinyLFU（sketch+SLRU）各自的数据结构？ A LFU 只需一个哈希表配合该键最后一次访问时间即可实现 O(1) B LRU 用哈希表定位、双向链表维护访问顺序，可做到 get/put 均为 O(1) ✓ 正确答案 C ARC 只用两个双向链表即可实现 recent/frequent 自适应 D W-TinyLFU 用精确计数表替代近似 sketch 以降低内存占用
# 2. 缓存算法的评估方法中如何在给定 trace（Zipf 分布、扫描型、循环型访问）下公平比较 FIFO/LRU/LFU/Clock 的命中率与实现复杂度？ A 扫描型访问是 LFU 的最坏情况，命中率会归零 B Zipf 分布下 FIFO 命中率显著高于 LRU C 循环型访问下 LRU 与 FIFO 命中率差异通常很小 ✓ 正确答案 D 实现复杂度评估必须与命中率无关地单独进行
# 3. LHD（Learning Hit Density）淘汰策略中为什么按'命中密度（单位空间的预期命中）'而非访问频率淘汰，与 LRU/LFU 在对象大小不均时的差异？ A LHD 按对象访问频率从低到高淘汰，与 LFU 等价 B LHD 与 LRU 一样只依赖最近访问时间，不做预测 C LHD 淘汰"单位空间预期命中数最小"的对象，能适配对象大小不均 ✓ 正确答案 D LHD 在对象大小一致时表现必然差于 LFU
# 4. Clock-Pro 的冷热双列表中为什么用冷/热 hand 调节列表长度能兼顾 LRU 的近期性与 LFU 的频率性，与 ARC 的异同？ A 它只记录访问频率，不保留近期性信息 B 它依赖四个幽灵列表记录被淘汰页的访问历史 C 它必须借助 Bélády 预知未来才能工作 D 冷/热双 hand 通过负反馈调节冷热列表长度，兼顾近期性与频率性 ✓ 正确答案
# 5. BigCache/fastcache 的零 GC 设计中为什么用分片+字节数组（无指针）存储能避免 GC 扫描，命中率与淘汰策略（TTL 为主）的局限？ A 用连续字节数组和偏移量替代指针，避免 GC 逐条扫描堆对象 ✓ 正确答案 B 它们的特点是每个条目独立小对象，便于 GC 快速回收 C 零 GC 意味着完全不需要任何内存分配 D 它们用精确的 LFU 频次桶实现高命中率
# 6. S3-FIFO 的队列结构中 small/main/ghost 三段 FIFO 加 visited 位就能逼近 LRU 命中率，其扫描抵抗性来自哪里？ A 只有 main 段存储条目，small 与 ghost 用于记录统计 B ghost 队列直接保存完整条目供 LRU 复用 C visited 位标记"是否被再次访问"，决定条目能否晋升到 main ✓ 正确答案 D S3-FIFO 的扫描抵抗性来自额外的随机抽样
# 7. 离线缓存 trace 评估中如何录制真实访问 trace 并回放计算 OPT/LRU/LFU 的命中率与字节命中率，评估工具有哪些？ A 命中率与字节命中率在任意 trace 下数值总是相等 B OPT 需要预知未来访问，因此只能离线回放计算 ✓ 正确答案 C trace 只需记录 key，无需记录对象大小 D 回放评估必须在线实时执行才有意义
# 8. 如何为不同的业务对象选择 LRU、LFU、ARC、W-TinyLFU、SLRU 等替换策略？ A LFU 在所有访问模式下命中率都必然高于 LRU B 访问有稳定热点且会受扫描攻击时，W-TinyLFU 凭借 sketch 抗扫描能力优于纯 LRU ✓ 正确答案 C SLRU 只适合数据量极小的缓存 D ARC 实现最简单，适合所有场景
# 9. LFU 如何用"频次桶 + 同频双向链表"实现 O(1) 操作 A 需要维护每个频次桶内的有序链表以保证 O(1) 淘汰 B minFreq 指针配合每个频次桶内按插入顺序的集合，可 O(1) 找到淘汰目标 ✓ 正确答案 C 频次更新时需对全表排序，复杂度为 O(n) D 命中时总是把节点移到频次最低的桶
# 10. LRU 如何用"哈希表 + 双向链表"实现 O(1) get/put A 单向链表即可实现 O(1) 删除尾节点 B 哈希表负责 O(1) 定位，双向链表负责维护访问顺序 ✓ 正确答案 C get 命中时不用更新链表顺序 D 哨兵节点会增加访问操作的复杂度
# 11. Caffeine 的 W-TinyLFU 相比 Guava LRU 的命中率优势中频率 sketch 的抗扫描能力、window 大小与 main 段比例如何调优？ A window 只用于存储淘汰历史，不缓存任何条目 B main 段默认占全部容量的 100%，window 无容量 C 频率 sketch 让低频一次性访问难以进入 main 段，从而抗扫描 ✓ 正确答案 D W-TinyLFU 与 Guava LRU 的命中率在任意负载下完全一致
# 12. 堆外（Off-heap）缓存的取舍中为什么大对象/长生命周期数据适合堆外存储，序列化开销与 DirectByteBuffer/Unsafe 的管理、回收细节？ A 堆外内存不受 JVM GC 管理，适合大对象和长生命周期数据 ✓ 正确答案 B 堆外存储完全没有序列化开销 C DirectByteBuffer 与 Unsafe 都无需手动释放内存 D 堆外缓存永远不会发生内存泄漏
# 13. Bélády 最优（OPT）作为离线上限中 OPT 需要预知未来访问序列，如何用 trace 回放计算 OPT 命中率并评估 LRU/ARC 的差距？ A OPT 可以在线实现，只要缓存容量足够大 B OPT 的命中率必然低于所有在线策略 C 计算 OPT 命中率不需要访问序列，只用访问频率 D OPT 淘汰"未来最晚被访问"的对象，需要预知未来，只能作离线参考 ✓ 正确答案
# 14. LFU 的扫描污染问题中纯 LFU 对'一次性大量访问'敏感，与 LRU 相比在突发访问下的命中率退化如何发生？ A 一次性大量访问让低频 key 计数虚高，长期占据缓存且抑制新热点 ✓ 正确答案 B 扫描污染只影响缓存命中率统计，不影响实际访问 C 提高缓存容量即可完全消除 LFU 的扫描污染 D LFU 与 LRU 一样不受扫描污染影响
# 15. ARC 的自适应机制中 T1/T2 与 B1/B2 四个列表如何根据 recent/frequent 访问动态调整容量分配，与 LRU/LFU 的关系？ A 命中 B1 幽灵列表说明负载偏近期，会增大 T1 的容量目标 ✓ 正确答案 B ARC 固定把容量对半分给 T1 和 T2，永不调整 C ARC 只有 T1/T2 两个列表，没有幽灵列表 D ARC 完全不保存任何缓存数据
# 16. 2Q 算法与 LRU-2 中 2Q 用 A1in/A1out/Am 三段近似'第二次访问间隔'，其空间开销与命中率相比 LRU 如何？ A 2Q 只用 A1in 一个队列，无需 Am B A1out 会保存完整数据以提升命中率 C 2Q 与 LRU 在扫描负载下命中率完全相同 D A1out 只保存 key 不保存数据，用于感知被淘汰后的再次访问 ✓ 正确答案
# 17. FIFO 与 LRU 的边界中什么访问模式下 FIFO 的命中率接近 LRU（如 Zipf 分布），什么模式（循环扫描）下差距显著？ A Zipf 分布下 FIFO 与 LRU 命中率通常比较接近 ✓ 正确答案 B 循环扫描时 FIFO 与 LRU 命中率完全相同 C LRU 在所有访问模式下都优于 FIFO D 任意访问模式下 FIFO 命中率都显著低于 LRU
# 18. Bélády 最优算法的不可实现性中'预知未来'使其只能作为离线上限，在线缓存算法（LRU/FIFO）的竞争比如何界定与 OPT 的差距？ A LRU 可以预知未来并实现与 OPT 相同的命中率 B OPT 需要预知未来，只能作离线上限；在线算法用竞争比界定与 OPT 的最坏差距 ✓ 正确答案 C FIFO 与 OPT 的命中率在任意序列下完全相等 D 竞争比描述的是平均情况而非最坏情况差距
# 19. Clock（二次机会）与 LRU 的近似误差中为什么 Clock 用循环扫描+参考位近似 LRU 顺序，参考位的设置/重置策略对命中率的影响？ A 参考位能精确记录每个页的完整访问顺序 B Clock 与精确 LRU 在所有情况下命中率完全相同 C 用环形数组加参考位近似 LRU，扫描时把参考位为 1 的页清零后给二次机会 ✓ 正确答案 D Clock 需要双向链表维护精确的最近顺序
# 20. SIEVE 缓存的简化设计中单队列+单个 hand 指针+visited 位就能工作，其扫描抵抗性与 LRU/FIFO 的实测对比如何？ A SIEVE 需要双向链表维护精确访问顺序 B SIEVE 的扫描抵抗性来自每个条目设置多个计数位 C 单人队列 + 单 hand 指针 + visited 位即可工作，实测命中率接近 LRU ✓ 正确答案 D SIEVE 的命中率在任意负载下都严格低于 FIFO
# 21. ARC（自适应替换）如何结合 LRU 与 LFU 思想提升命中 A ARC 完全抛弃 LRU 思想，只按频率工作 B ARC 的容量分配是固定的，与负载无关 C T1 承载 LRU 的近期性、T2 承载 LFU 的频率性，用幽灵列表反馈动态调整容量 ✓ 正确答案 D ARC 只用一个列表，无法区分近期与频率
# 22. LRU 在并发环境加锁对整个缓存的吞吐瓶颈 A 用读锁即可完全避免 LRU 的并发竞争 B 分段 LRU 无法减少锁竞争 C LRU 的 get 是纯读操作，天然可并发 D LRU 命中也会移动链表节点，使读操作也要写共享状态，导致全局锁成瓶颈 ✓ 正确答案
# 23. 为何只用哈希表无法维护访问顺序，必须配链表 A 只用哈希表就能 O(1) 找到最久未使用的 key B 哈希表本身就维护访问顺序 C 双向链表可以代替哈希表完成 O(1) 定位 D 哈希表负责 O(1) 定位，双向链表负责 O(1) 维护访问顺序，缺一不可 ✓ 正确答案
# 24. 分段 LRU（sharded）如何用多把锁降低竞争 A 分段 LRU 完全不需要加锁 B 通过哈希把 key 分散到多个独立加锁的段，降低锁竞争，但可能损失命中率 ✓ 正确答案 C 分段 LRU 无法分散并发竞争 D 分段数越多，命中率损失越小且有严格上界
# 25. Markov 预取（Markov prefetcher）如何用访问序列的转移概率预测下一缓存行，与顺序/步幅预取在命中率与带宽浪费上的取舍？ A 用历史转移概率预测下一地址，能捕捉不规则模式，但可能误预取浪费带宽 ✓ 正确答案 B Markov 预取与顺序预取在命中率上永远完全相同 C 预取器只需要关注命中率，无需考虑带宽浪费 D Markov 预取无法处理任何访问模式
# 26. W-TinyLFU 的结构与准入中 Caffeine 中 window LRU（默认 1%）与 main SLRU（99%）如何分工，TinyLFU 频率 sketch 如何决定新条目能否进入 main？ A window 承接新条目，main 用 sketch 频率比较决定是否准入，频率低的一次性访问被挡在 main 外 ✓ 正确答案 B 所有新条目都直接进入 main 段，无需频率比较 C main 段不保存任何条目，只记录统计 D window 占全部容量，main 仅作辅助
# 27. SLRU 的两段结构（probation/protected）中条目如何从 probation 晋升到 protected、从 protected 淘汰，与 LRU-2 在命中率上的关系？ A 所有条目一进入就直接到 protected 段 B protected 段淘汰的条目直接被丢弃，不再回 probation C SLRU 与 LRU-2 的"二次访问"核心思想无关 D 新条目先进 probation，probation 内再次访问才晋升 protected，protected 淘汰回 probation ✓ 正确答案
# 28. TinyLFU 的频率近似中用 Count-Min sketch 近似访问频率而非精确计数，freshness 机制（定期衰减）如何避免历史频率压制新热点？ A Count-Min sketch 提供精确的频率计数，无任何误差 B freshness 会永久保留历史频率，不影响新热点 C Count-Min sketch 用固定内存近似频率，freshness 定期衰减避免旧热点压制新热点 ✓ 正确答案 D TinyLFU 需要为每个 key 单独分配计数器
# 29. 本地缓存（Guava/Caffeine）在水平扩展下的命中率与一致性中每实例独立缓存会放大 miss，如何用 Redis 二级缓存与失效广播缓解？ A 水平扩展不会降低本地缓存命中率 B 每实例独立缓存会放大整体 miss，需要用 Redis 二级缓存和失效广播缓解 ✓ 正确答案 C Redis 二级缓存无法提高命中率 D 本地缓存天然跨实例一致，无需失效处理
# 30. 缓存穿透与击穿的治理中如何区分'查不到的数据'与'热点同时过期'，布隆过滤器、空值缓存与互斥重建分别解决哪个问题？ A 布隆过滤器解决的是热点同时过期问题 B 布隆/空值缓存针对"不存在 key"的穿透，互斥重建针对"热点过期"的击穿 ✓ 正确答案 C 穿透与击穿是同一问题，治理手段完全相同 D 互斥重建用于解决"数据不存在"的穿透
# 31. Caffeine 的分段（sharded）并发设计中多个 segment 各自独立淘汰如何减少锁竞争，段数与命中率损失、内存开销的权衡？ A Caffeine 只用一把全局锁，无分段 B 分段设计无法减少锁竞争 C 段数越多命中率必然越高 D 多段各自独立淘汰与加锁减少竞争，但段数过多会损失命中率并增加内存 ✓ 正确答案
# 32. FreeCache 的 ring buffer 与零 GC 中如何用环形缓冲区+偏移量代替指针管理缓存条目，内存碎片与容量上限如何处理？ A FreeCache 用精确 LRU 淘汰，无空间覆盖问题 B 环形缓冲区可以无限动态扩展容量 C FreeCache 用指针对象存储每个条目 D 用环形缓冲区加偏移量定位条目，避免指针，实现零 GC ✓ 正确答案
# 33. 进程内缓存 vs 分布式缓存中 BigCache/本地 Caffeine 与 Redis 在延迟、吞吐、一致性上的取舍，什么场景需要两级结合？ A Redis 延迟低于本地内存缓存 B 本地缓存天然跨实例一致，无需失效处理 C 本地缓存延迟低但跨实例一致性和命中率差，Redis 反之，两级结合可兼顾 ✓ 正确答案 D 两级缓存无法结合本地与 Redis 的优点
# 34. TinyLFU / W-TinyLFU 的频 Sketch 如何抗扫描污染 A 扫描 key 在 sketch 中频率很高，会被优先保留 B W-TinyLFU 与纯 LFU 一样容易受扫描污染 C freshness 会导致扫描污染更严重 D 扫描 key 每个只访问一次、频率低，被频率门槛挡在 main 外，从而保护热点 ✓ 正确答案
# 35. 面试中如何从无锁思路讨论并发 LRU 的工程难点 A LRU 的 get 是纯读操作，天然可无锁并发 B Caffeine 维护的是严格 LRU 顺序，无任何近似 C 无锁双向链表没有任何难点 D LRU 命中需移动链表节点（写共享状态），严格无锁实现多指针一致性极难，通常用近似+分段+读路径优化 ✓ 正确答案
