线上一个用哈希表（拉链法）做本地缓存的模块，key 是字符串，稳态约 800 万个 entry，负载因子 0.75，扩容策略是容量翻倍。写入 QPS 很稳定，但监控显示 P99 延迟每隔几十分钟会从 0.5ms 飙到 50ms，之后恢复正常。说说你怎么定位根因，以及打算怎么改。

面试官在考什么

判断候选人能否把「哈希表扩容是一次同步的全量 rehash」这个知识点，落到线上延迟毛刺的定位与治理上。

哈希表

回答框架 · 前两步

1. 根因假设：容量翻倍触发的全量 rehash——一次性重新分配 1600 万个桶、把 800 万个 entry 全部重新算哈希并搬迁，这段在写入路径上是同步阻塞的，直接体现为 P99 毛刺。
2. 验证手段：给 rehash 起止打点记录耗时；观察毛刺周期是否与 entry 数跨过容量阈值（0.75 × 当前容量）一致；用 CPU profile 看毛刺期间耗时是否集中在 rehash 相关函数。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、D-7 准备表

想看这个方向的整体准备路线？ 进入「数据结构与算法」方向页

同一能力域的其他题

• 有个排行榜模块：N=10^6 个用户按分数从高到低存在一个容器里，读取非常频繁（每秒约 10^5 次「取第 k 名」和「取某用户的排名」），写入很少（每秒约 10 次插入/删除，插入位置随机分布在容器中部）。同事建议用双向链表，理由是插入删除 O(1)；你倾向用哪一种？请从内存布局、常数开销和这两类操作的实际耗时量级给出判断依据。
• 内存里要维护 50 万条按时间排序的订单快照，需要支持三种操作：① 按下标随机读取（约 5000 QPS，要拿到第 k 早的订单）；② 在任意位置插入新订单（约 200 次/秒，插入位置在 [0, 50万] 上近似均匀分布）；③ 按订单号删除（约 200 次/秒，位置同样近似均匀分布）。你会选动态数组还是双向链表？请给出量化判断依据：涉及哪些开销、量级差多少。如果业务要求三种操作都不能慢，你会怎么改造这个结构？
• 某服务在内存里维护一份“最近 N 条记录”的有序表（N=100 万，单条记录 64B），线上埋点统计的操作占比是：尾部追加 90%，按序号随机读取 9%，在中间指定位置插入或删除 1%。现有实现是动态数组，中间插入需要 memmove 平均约 50 万条记录（约 32MB）。有同学提议整体换成双向链表，理由是“链表插入删除是 O(1)”。作为技术负责人，你怎么做这个决策？请给出你的判断依据、你要补测的数据，以及最终方案。
• 在一个长度为 100 万的整型序列上，需要执行 10 万次操作。其中 90% 是在序列头部插入一个元素，10% 是按索引随机读取一个元素。你会选择数组还是单链表？请分别估算两种选择下这 10 万次操作的相对代价（不需要精确时间，说明量级即可）。如果把比例改成 90% 随机读取、10% 头部插入，你的选择会变吗？为什么？
• 给你一个长度 n=10^7 的整数数组和一个固定窗口大小 k=1000，要求输出每个窗口内的最大值，总时间必须是 O(n)。你会用什么结构？请具体说明：队列里存元素值还是下标、什么时候从队尾弹出、队首元素什么时候失效、以及为什么这套操作合起来是 O(n) 而不是 O(nk)。
• 一个下单服务每秒产生约 8 万条事件，由一个后台线程批量拉取（每 50ms 一次）后写下游消息队列。缓冲放在进程内存里，消费者偶发卡顿 2~3 秒。请给出你选的有界队列实现和容量参数：为什么不用无界的 LinkedBlockingQueue？容量大概设多少、内存占多少？消费者卡顿 3 秒导致队列满时，你的策略是阻塞生产者、丢弃、还是落盘？如果改成单生产者单消费者的无锁环形缓冲区，生产者和消费者各需要维护什么状态，怎么判断'空'和'满'？