Redis采用渐进式rehash而非一次性全量迁移，因后者会导致主线程阻塞、引发P99延迟毛刺；其通过双哈希表（ht[0]和ht[1]）、rehashidx进度标记及每次操作顺带迁移一个桶的方式，实现平滑扩容缩容，保障高并发下的低延迟与数据一致性。
哈希表扩容不是“一次性全量搬数据”，而是渐进式重哈希——否则插入时卡顿明显，尤其在高吞吐场景下会直接暴露为 P99 延迟毛刺。
为什么 rehash() 不能解决所有扩容问题
标准库的 unordered_map::rehash(size_t n) 是立即触发全量重散列：分配新桶数组、遍历旧表所有元素、逐个 hash(key) % new_bucket_count 计算新位置、链表/节点迁移。这在 n 较大（比如从 1024 扩到 2048）且元素密集时，可能阻塞主线程数十微秒甚至毫秒级。对延迟敏感服务（如高频交易网关、实时推荐特征拼接）不可接受。
常见误用：map.rehash(map.bucket_count() * 2) 放在插入前做“预扩容”，看似规避了临界点抖动，实则把延迟提前集中释放，且无法应对突发流量。
- 它不感知当前负载节奏，无法拆分工作量
- 不兼容多线程写入（STL 容器非线程安全）
- 无法与业务逻辑协同（比如只在空闲 tick 或 GC 阶段执行迁移）
渐进式扩容的核心是“桶迁移状态机”
关键不在“要不要搬”，而在“每次搬多少、搬哪几个、怎么保证读写一致性”。典型设计包含三个状态字段：
old_buckets（只读旧桶数组）、new_buckets（可写新桶数组）、migration_index（下一个待迁移桶索引）
每次插入/查找操作后，检查是否需推进迁移；每次只迁移一个桶（或固定小批量），避免单次开销过大。迁移中，读请求需同时查两个桶：先查 new_buckets，未命中再查 old_buckets；写请求一律写入 new_buckets，并标记对应旧桶为“已迁移完成”。
- 迁移过程完全无锁（若用原子整数管理
migration_index） - 旧桶数组仅用于读，生命周期可控，最后由析构函数统一回收
- 迁移进度可监控：
(migration_index * 100) / old_bucket_count
string 类型哈希值计算与取模陷阱
自定义哈希表常直接用 key % bucket_count，但 std::string 不支持取模运算，必须先通过 std::hash<:string>{}(key) 转成 size_t。此时真正危险的是后续取模操作：
若桶数量 bucket_count 是 2 的幂（如 1024），hash_value & (bucket_count - 1) 虽快，但会放大低位哈希碰撞——因为 std::hash<:string> 输出的低位往往相关性高（尤其短字符串）。
- 务必让
bucket_count为质数，例如 1021、2039、4093 - 避免手写
hash_value % bucket_count，改用编译器优化后的__builtin_umod（GCC）或确保除法被常量折叠 - 若用开放寻址法，探测步长也应避开 2 的幂，推荐使用黄金比例乘法：
(hash_value * 2654435761U) & (bucket_count - 1)（仅当bucket_count是 2 的幂时成立，否则仍需取模）
重哈希时迭代器失效与引用稳定性
STL 的 unordered_map 在 rehash() 后所有迭代器失效，这是标准要求。但自研高性能哈希表可保留 value 引用稳定性：只要不移动 value 内存（即用指针/句柄间接访问），只挪动桶内指针或索引即可。
例如，value 存于独立内存池，每个桶存的是 value* 或 uint32_t offset；重哈希时只更新这些指针/偏移，value 对象本身不动。这样上层业务持有的 &value 依然有效。
- 代价是额外一层间接访问（一次 cache miss）
- 适用于 value 较大（>64B）且上层频繁取地址的场景（如图数据库顶点属性缓存）
- 必须禁用
std::allocator的 move 构造，改用 placement-new + 显式析构
渐进式扩容真正的难点不在代码行数，而在于状态边界——比如迁移中途崩溃，如何保证恢复后不丢数据、不重复迁移、不卡死在中间状态。这需要把迁移索引持久化到 WAL 或至少原子写入共享内存，而不是只存在栈或寄存器里。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
