渐进式 rehash 是什么？为什么能避免哈希表扩容时长时间卡顿？
简化版
渐进式 rehash 是把一次性搬迁整个哈希表，拆成多次小迁移。扩容后同时保留新旧两个表，每次读写顺手迁移一部分桶，直到旧表搬空，从而避免单次 rehash 阻塞太久。
详细版
普通 rehash 会创建更大的表，然后把旧表所有元素重新计算位置并搬过去。数据量大时，这次操作可能造成明显延迟尖峰。
渐进式 rehash 的思路：
- 分配新表，但不一次搬完。
- 维护一个迁移进度下标。
- 查找时可能同时查旧表和新表。
- 插入通常进入新表。
- 每次操作顺带迁移若干旧桶。
- 旧表迁移完成后释放。
它用实现复杂度换延迟平滑，常见于对响应时间敏感的哈希结构。
完整版教学
一、一次性 rehash 为什么会卡顿
哈希表扩容不是只换一个容量数字。所有元素的位置都依赖容量，容量变了，桶下标也可能变。
oldIndex = hash % oldCapacity
newIndex = hash % newCapacity如果表里有 1000000 个元素，一次性 rehash 就要遍历这些元素并重新插入新表。即使总复杂度仍然摊还 O(1)，某一次操作可能突然耗时很长。
二、渐进式 rehash 的核心结构
渐进式 rehash 通常同时维护两张表：
oldTable：正在迁移
newTable：接收新写入
rehashIndex：当前迁移到哪个桶扩容开始后，新写入可以直接进入新表。查找时先查新表，再查旧表中尚未迁移的部分。每次普通操作附带迁移 1 个或多个旧桶。
这相当于把一次大搬家拆成很多次顺手搬箱子。
三、迁移一个桶是什么意思
如果旧表采用拉链法，一个桶可能挂着多个节点。迁移一个桶就是把这个桶里的所有元素重新计算新表位置，并插入新表。
old[3]: A -> B -> C
迁移后：
new[hash(A)%newCap] 加 A
new[hash(B)%newCap] 加 B
new[hash(C)%newCap] 加 C
old[3] 置空
rehashIndex 前进如果某些旧桶为空，可以快速跳过。每次迁移多少桶会影响单次延迟和完成速度。
四、查询为什么要看两张表
迁移尚未完成时，元素可能在旧表，也可能在新表。查找必须覆盖两边，否则会出现误判不存在。
value = find(newTable, key)
if not found and rehashing:
value = find(oldTable, key)为了减少重复，有些实现保证被迁移过的旧桶不再查询。逻辑上无论如何，都要保证迁移期间读写结果和单表状态一致。
五、写入和删除怎么处理
扩容期间新插入通常进入新表，避免刚插入旧表又被迁移。删除则要在可能存在的表中删除，或者根据迁移进度判断去哪删。
| 操作 | 渐进式 rehash 期间的处理 |
|---|---|
| 查找 | 新表 + 旧表 |
| 插入 | 通常进新表 |
| 删除 | 可能两边查找并删除 |
| 更新 | 找到所在表后更新，或统一迁入新表 |
实现要小心一致性，尤其是同一个 key 不能在新旧表里出现两份有效记录。
六、收益和代价如何权衡
渐进式 rehash 的收益是降低单次延迟尖峰。代价是实现复杂、查询可能要查两张表、迁移期间内存占用更高。
记忆钩子：普通 rehash 是“一次搬完”，渐进式 rehash 是“边服务边搬家”；它优化的是延迟尖峰，不是总搬迁工作量。
七、常见误区与追问
- 误区：渐进式 rehash 减少了总复杂度。 总迁移工作量仍然存在，只是被拆散到多次操作中。
- 误区：扩容后只查新表。 迁移未完成时旧表仍有元素，必须能查到。
- 误区：迁移期间内存更省。 同时保留新旧表，短时间内内存占用更高。
- 追问：如果没有后续请求，迁移会不会停住？ 可能会，所以有些系统会后台定时推进迁移。
- 追问：插入为什么通常进入新表？ 避免新元素进入旧表后又被迁移，简化迁移路径。
八、加强记忆
渐进式 rehash 要记住三件事：两张表、一个迁移进度、每次操作顺带搬一点。它不让扩容那一刻把所有用户请求卡住，但读写逻辑更复杂，迁移期间还要承担双表内存和双表查询成本。