某在线服务在内存里用哈希表做会话路由（约 2000 万 key，负载因子 0.75）。扩容触发的一次 rehash 造成约 200ms 停顿，大促期间 P99 要求低于 20ms；另外历史上曾被人构造大量落入同一槽位的 key，导致查询退化成链表扫描。请给出一条能平滑上线的改造路径：怎么消除扩容停顿、怎么防退化，以及分片之后如果还要再扩缩容，跨分片迁移怎么推进。

面试官在考什么

考察候选人能否把哈希表的内部行为（rehash、冲突退化）映射成线上延迟与安全指标，并给出可灰度的演进路径与跨团队迁移方案。

哈希表

回答框架 · 前两步

1. 停顿的根源是单次全量 rehash；解法是把迁移摊到多次操作上，比如渐进式 rehash（每次 put 或 get 顺带搬若干个桶），或者分片后逐片迁移，把一次 200ms 切成多个可观测的小段。
2. 渐进式 rehash 必须定义迁移期间的读写语义：通常 get 先查新表再查旧表，put 统一写新表或写旧表并打标记，删除要两边都删；迁移完成要有明确判据和状态机。

延伸阅读

• 避坑与冲刺：简历自洽、六种扣分话术、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 秒导致队列满时，你的策略是阻塞生产者、丢弃、还是落盘？如果改成单生产者单消费者的无锁环形缓冲区，生产者和消费者各需要维护什么状态，怎么判断'空'和'满'？