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操作的执行而最终变成空表。