rehash过程_contenthash

大家好，又见面了，我是你们的朋友全栈君。

步骤

1） 首先创建一个比现有哈希表更大的新哈希表（expand） 2） 然后将旧哈希表的所有元素都迁移到新哈希表去（rehash）

dictAdd 对字典添加元素的时候， _dictExpandIfNeeded 会一直对 0 号哈希表的使用情况进行检查。

当 rehash 条件被满足的时候，它就会调用 dictExpand 函数，对字典进行扩展。

static int _dict ExpandIfNeeded(dict *d) { // 当 0 号哈希表的已用节点数大于等于它的桶数量， // 且以下两个条件的其中之一被满足时，执行 expand 操作： // 1) dict_can_resize 变量为真，正常 expand // 2) 已用节点数除以桶数量的 比率超过变量 dict_force_resize_ratio ，强制 expand // (目前版本中 dict_force_resize_ratio = 5) if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2); } }

将新哈希表赋值给 1 号哈希表，并将字典的 rehashidx 属性从 -1 改为 0： int dictExpand(dict *d, unsigned long size) { // 被省略的代码… // 计算哈希表的(真正)大小 unsigned long realsize = _dictNextPower(size); // 创建新哈希表 dictht n; n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; // 字典的 0 号哈希表是否已经初始化？ // 如果没有的话，我们将新建哈希表作为字典的 0 号哈希表 if (d->ht[0].table == NULL) { d->ht[0] = n; } else { // 否则，将新建哈希表作为字典的 1 号哈希表，并将它用于 rehash d->ht[1] = n; d->rehashidx = 0; } // 被省略的代码… }

渐增式rehash和平摊操作

集中式的 rehash 会引起大量的计算工作。

渐增式 rehash将 rehash 操作平摊到dictAddRaw 、dictGetRandomKey 、dictFind 、dictGenericDelete这些函数里面，每当上面这些函数被执行的时候, _dictRehashStep 函数就会执行，将 1 个元素从 0 号哈希表 rehash 到 1 号哈希表，这样就避免了集中式的 rehash 。

以下是 dictFind 函数，它是其中一个平摊 rehash 操作的函数： dictEntry *dictFind(dict *d, const void *key) { // 被忽略的代码… // 检查字典(的哈希表)能否执行 rehash 操作 // 如果可以的话，执行平摊 rehash 操作 if (dictIsRehashing(d)) _dictRehashStep(d); // 被忽略的代码… } 其中 dictIsRehashing 就是检查字典的 rehashidx 属性是否不为 -1 ：#define dictIsRehashing(ht) ((ht)->rehashidx != -1) 如果条件成立成立的话， _dictRehashStep 就会被执行，将一个元素从 0 号哈希表转移到 1 号哈希表： static void _dictRehashStep(dict *d) { if (d->iterators == 0) dictRehash(d,1); } （代码中的 iterators == 0 表示在 rehash 时 不能有迭代器，因为迭代器可能会修改元素，所以不能在有迭代器的情况下进行 rehash 。）

0 号哈希表的元素被逐个逐个地，从 0 号 rehash 到 1 号，最终整个 0 号哈希表被清空，这时 _dictRehashStep 再调用 dictRehash ，被清空的 0 号哈希表就会被删除，然后原来的 1 号哈希表成为新的 0 号哈希表。

当 rehashidx 不等于 -1 ，也即是 dictIsRehashing 为真时，所有新添加的元素都会直接被加到 1 号数据库，这样 0 号哈希表的大小就会只减不增。

哈希表的大小

我们知道哈希表最初的大小是由 DICT_HT_INITIAL_SIZE 决定的，而当 rehash 开始之后，根据给定的条件，哈希表的大小就会发生变动： static int _dictExpandIfNeeded(dict *d) { // 被省略的代码… if (d->ht[0].used >= d->ht[0].size && (dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) { return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2); } // 被省略的代码… } 可以看到， d->ht[0].size 和 d->ht[0].used 两个数之间的较大者乘以 2 ，会作为 size 参数被传入 dictExpand 函数，但是，尽管如此，这个数值仍然还不是哈希表的最终大小，因为在 dictExpand 里面，_dictNextPower 函数会根据传入的 size 参数计算出真正的表大小： int dictExpand(dict *d, unsigned long size) { // 被省略的代码… // 计算哈希表的(真正)大小 unsigned long realsize = _dictNextPower(size); // 创建新哈希表 dictht n; n.size = realsize; n.sizemask = realsize-1; n.table = zcalloc(realsize*sizeof(dictEntry*)); n.used = 0; // 被省略的代码… } 至于 _dictNextPower 函数，它不断计算 2 的乘幂，直到遇到大于等于 size 参数的乘幂，就返回这个乘幂作为哈希表的大小： static unsigned long _dictNextPower(unsigned long size) { unsigned long i = DICT_HT_INITIAL_SIZE; if (size >= LONG_MAX) return LONG_MAX; while(1) { if (i >= size) return i; i *= 2; } }

1） 哈希表的大小总是 2 的乘幂（也即是 2^N，此处 N 未知） 2）1 号哈希表的大小总比 0 号哈希表大

最后， 我为 redis 的源码分析项目专门建立了一个 github project ，上面有完整的源码文件，大部分加上了注释（目前只有 dict.c 和 dict.h），如果对代码的完整细节有兴趣，可以到上面去取： https://github.com/huangz1990/reading_redis_source

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/168252.html原文链接：https://javaforall.cn