渐进式哈希（Progressive Hashing）是一种用于优化哈希表操作性能的技术，在Redis等系统中有着广泛应用。
- 基本概念：渐进式哈希是一种渐进式地迁移数据的方式，它将哈希表的重哈希（Rehash）操作分解成多个小步骤，每次只迁移一小部分数据，以避免一次性操作造成的性能抖动。
- 触发条件：以Redis为例，当哈希表的负载因子（键数量/桶数量）超过阈值时会触发渐进式哈希。具体来说，当负载因子大于等于1，并且Redis没有在执行RDB快照或AOF重写操作时，会进行rehash操作；当负载因子大于等于5时，不管有没有在执行RDB快照或AOF重写，都会强制进行rehash操作。
- 实现原理：
- 维护两个哈希表：Redis会维护两个哈希表，即旧表
ht(0)和新表ht(1)。当触发Rehash时，会创建一个更大（或更小）的新哈希表ht(1)，而旧表ht(0)仍然保留。 - 逐步迁移数据：Redis使用一个
rehashidx指针记录当前迁移的桶位置，每次对字典执行添加、删除、查找或者更新操作时，除了执行指定的操作外，还会顺带将ht(0)哈希表在rehashidx索引上的所有键值对迁移到ht(1)。迁移完成后，ht(1)成为新的主哈希表，ht(0)被清空并释放。 - 查询操作处理：在迁移期间，查询操作会同时在
ht(0)和ht(1)中进行，确保数据访问无中断。例如，查找一个键的值时，先会在ht(0)里面进行查找，如果没找到，就会继续到ht(1)里面进行查找。
- 维护两个哈希表：Redis会维护两个哈希表，即旧表
注意：本文归作者所有，未经作者允许，不得转载
