渐进式 RehashIncremental rehash
把哈希表迁移分散到多个操作或维护步骤。
- 核心约束
- 迁移期必须能够在新旧表中正确找到键。
- 适用问题
- 减少一次性扩容带来的长停顿。
- 边界与取舍
- 双表占用额外内存；不等于严格恒定的单次延迟。
常见操作#
n 为条目数，b 为单步实际搬迁条目数；针对 Redis 7.2 的链式哈希迁移。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 启动扩容 | 分配并初始化新桶数组 | 渐进搬迁不代表新桶数组初始化也一定按同样粒度渐进执行。 |
| 推进一个迁移步骤 | ，另计跳过空桶 | 一次迁移整个非空桶的冲突链；限定桶数不等于限定条目数或严格墙钟预算。 |
| 迁移期间查询 | 查询新旧两表的相应桶 | 在良好分布和负载控制下仍可期望 ，最坏冲突成本依实现。 |
时间与空间#
- 时间复杂度
- 全量条目搬迁 ，分摊到多个步骤
- 辅助空间
- 新旧桶数组并存，条目节点逐个转移
分散时延需要额外状态和双表分支。扩容幅度、键哈希和空桶扫描都影响单步成本。
工程中的应用#
1 个案例 · 附源码Redis 7.2.0 的字典扩缩容保留新旧两张哈希表，逐桶迁移，降低一次性搬迁全部条目的停顿。
附源码片段 · 索引与查找
基础原理参考资料
Redis 7.2 · dict.cdictRehash、dictFind、dictRehashMilliseconds 的双表及桶级推进。