Redis原理篇-Dict的rehash

**

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

Dict的rehash并不是一次性完成的。试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下：

1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
   1. 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
   2. 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]。让dict字典同时持有 ht[0] 和 ht[1] 两个哈希表。
3. 设置dict.rehashidx = 0，标示开始rehash

可以把rehashidx理解成 进行 渐进式 Rehash 时的“进度条”

5. 将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1]
6. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新操作时，会先检查dict.rehashidx是否大于-1，然后程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在 rehashidx索引(table[rehashidx]桶上的链表)上的所有键值对rehash到ht[1]上，当rehash工作完成之后，将rehashidx属性的值增一，表示下一次要迁移链表所在桶的位置。直到dict.ht[0]的所有数据都rehash到dict.ht[1]
7. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
8. **将rehashidx赋值为-1，代表rehash结束
9. 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空**