Redis 的哈希表如何处理冲突和渐进式 rehash？

Redis 广泛使用字典结构保存 Key 与其他索引。以 Redis 7.2 的经典实现为例，字典用哈希函数定位桶，冲突时通过链式结构组织条目；扩容或收缩时采用渐进式 rehash，分批迁移桶，减少一次迁移整个大表导致的长暂停。

为什么需要两个表？#

rehash 期间同时存在旧表和新表，并记录当前迁移位置。查找要考虑两张表，新的插入通常进入新表；每次推进迁移，就把旧表某些桶中的条目按新表大小重新计算位置。旧表迁移完毕后释放，新表成为当前表。

可以把它看成逐步搬仓库：旧仓和新仓都可能有货，收新货放进新仓，查货时同时考虑两个仓库。迁移不改变字典对外语义，但会增加暂时的内存与维护开销。

渐进式并不意味着每次操作严格只花固定时间。一个桶可能有多个冲突条目，分配新表本身也有成本。Redis 会在字典操作及后台工作中推进迁移，并在某些遍历或后台子进程情境下控制迁移，避免影响迭代或扩大 COW。具体策略属于版本实现细节。

哈希查找的常见平均成本接近 O(1)，但取决于散列分布、负载和碰撞情况。极端冲突会增加遍历成本。Redis 采用合适的散列方式降低可预测碰撞风险，但平均复杂度不能被当成严格最坏情况保证。

不是。rehash 调整内部哈希桶位置，业务 Key 的名字和 Value 不变；Cluster 扩缩容的哈希槽迁移是另一个层面的分片过程。

大字典整体迁移会长期占用主线程，影响所有客户端。分批推进能把工作分摊到多次操作，但仍需监控尾延迟。

会同时保留旧表和新表的桶数组，条目逐步移动。不能把两个表理解为完整复制两份所有 Value，但额外表空间不可忽略。

不是。较小的 Hash 在相应版本中可以使用 listpack 等紧凑编码，只有符合条件转换后才使用字典存储。