redis 学习笔记：hash表的渐进式rehash
redis的数据库使用字典来作为底层实现的，对数据库的增删查改操作也是构建在对字典的操作之上。redis的字典使用hash表作为底层实现。
redis作为一个广泛使用的内存数据库，时间和空间效率都是至关重要的。为了使时间效率和空间效率达到最大化，redis中的hash表设计普通的hash表又有什么区别呢？
我们知道当hash表满员时（或负载因子高于阈值时）会进行rehash,也就是重新调整空间大小，并拷贝原来的数据。这里rehash就是优化效率的关键。例如假设有1w个元素，rehash时要拷贝1w元素到新的空间，这样势必会成为很大的负担。
redis采用渐进式rehash来解决这个问题。
何为渐进式rehash？就是把拷贝节点数据的过程平摊到后续的操作中，而不是一次性拷贝。
所谓平摊到后续的操作中，就是对节点操作，例如再次插入，查找，删除，修改时都会进行拷贝。
要想实现这个过程，一个hash结构必须要有以下字段：
两个hash表。一个表拷贝到另一个表的容器
一个标识rehashidx来表明是否在进行rehash中。如果是，那么对节点的操作启动rehash过程。
何时启动rehash？当hash结构的第一个hash表ht[0]达到扩容条件就可以启动了。此时重新调整并分配新的空间，将hash结构的第二个hash表ht[1]指向这个空间。
rehash的过程很简单，具体过程为：
1 通过rehashidx索引找到要搬移节点的位置，如果是空，则向后跳
2 计算要搬移节点的hash值，得出要插入到新hash表的位置
3 写入到新节点中，如果节点是链式的，则还要搬移后面所有在链表中的节点
4 更新hash表计数
当全部节点搬移完成之后需要做什么呢？
由于只有两个hash表容器（也只要两个hash表容器就够了），如果ht[1]需要rehash时再搬移到ht[0]吗？这样是没有问题的，但是显得有点混乱，因为搞不清楚哪个容器是要搬移的。巧妙的做法是搬移完成之后，让ht[0]指向新的hash容器。这样ht[0]永远是那个要被搬移的对象，dt[1]是搬移过程中的中转。
rehash的代码如下：
int dictRehash(dict *d, int n) {
if (!dictIsRehashing(d)) return 0;
while (n--) {
dictEntry *de, *nextde;
if (d->ht[0].used == 0) { // 如果 0 号哈希表为空，那么表示 rehash 执行完毕
zfree(d->ht[0].table);
d->ht[0] = d->ht[1];
_dictReset(&d->ht[1]);
d->rehashidx = -1;
return 0;
}
// Note that rehashidx can't overflow as we are sure there are more
// elements because ht[0].used != 0
// 确保 rehashidx 没有越界
assert(d->ht[0].size > (unsigned)d->rehashidx);
while (d->ht[0].table[d->rehashidx] == NULL) d->rehashidx++; // 略过数组中为空的索引，找到下一个非空索引
de = d->ht[0].table[d->rehashidx];
while (de) {
unsigned int h;
nextde = de->next;
// 计算新哈希表的哈希值，以及节点插入的索引位置
h = dictHashKey(d, de->key) & d->ht[1].sizemask;
// 插入节点到新哈希表,而且是插入到表头
de->next = d->ht[1].table[h];
d->ht[1].table[h] = de;
d->ht[0].used--;
d->ht[1].used++;
de = nextde;
}
// 将刚迁移完的哈希表索引的指针设为空
d->ht[0].table[d->rehashidx] = NULL;
d->rehashidx++;
}
return 1;
}
需要注意的是因为在渐进式rehash的过程中，字典同时会使用ht[0],ht[1]两个hash表。所以在这个过程中，删除，查找，更新等操作会在这两个hash表上进行。例如要在字典里查找一个key的话，会先在ht[0]里面进行查找，如果没有找到的话，就会继续到ht[1]里面进行查找。
另外，在渐进式rehash执行期间，新添加到字典的key-val一律会被保存到ht[1]里面，而ht[0]不再进行任何添加操作，这一措施保证了ht[0]包含的key-val对数量只增不减，并随着rehash操作的执行而最终变成空表。