透过 Redis 源码探究 Hash 表的实现，你学废了吗？

作者：Java快了！

2022 年 9 月 09 日
湖南
本文字数：5389 字
阅读完需：约 18 分钟

概述 #

我们在学习 Redis 的 Hash 表的时候难免脑子里会想起其他 Hash 表的实现，然后进行一番对比。通常我们如果要设计一个 Hash 表，那么我们需要考虑这几个问题：

有没有并发操作；
Hash 冲突如何解决；
以什么样的方式扩容。

对 Redis 来说，首先它是单线程的工作模式，所以不需要考虑并发问题，这题 pass。

对于 Hash 冲突的解决，通常来说有，开放寻址法、再哈希法、拉链法等。但是大多数的编程语言都用拉链法实现哈希表，它的实现复杂度也不高，并且平均查找的长度也比较短，各个用于存储节点的内存都是动态申请的，可以节省比较多的存储空间。

所以对于 Redis 来说也是使用了拉链法来解决 hash 冲突，如下所示，通过链表的方式把一个个节点串起来：

至于为什么没有向 JDK 的 HashMap 一样红黑树来解决冲突，我觉得其实有两方面，一方面是链表转红黑数其实也是需要时间成本的，会影响链表的操作效率；另一方面就是红黑树其实在节点比较少的情况下效率是不如链表的。

再来看看扩容，对于扩容来说，一般要新起一块内存，然后将旧数据迁移到新的内存块中，这个过程中因为是单线程，所以在扩容的时候，不能阻塞主线程很长时间，在 Redis 中采用的是渐进式 rehash + 定时 rehash 。

渐进式 rehash 会在执行增删查改前，先判断当前字典是否在执行 rehash。如果是，则 rehash 一个节点。这其实是一种分治的思想，通过通过把大任务划分成一个个小任务，每个小任务只执行一小部分数据，最终完成整个大任务。

定时 rehash 如果 dict 一直没有操作，无法渐进式迁移数据，那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据，并限制如果一次操作耗时超时 1ms 就结束本次任务，待下次再次触发迁移

Redis 在结构体中设置两个表 ht[0] 和 ht[1]，如果当前 ht[0]的容量是 0 ，那么第一次会直接给 4 个容量；如果不是 0 ，那么容量会直接翻倍，然后将新内存放入到 ht[1]中返回，并设置标记 0 表示在扩容中。

迁移 hash 桶的操作会在增删改查哈希表时每次迁移 1 个哈希桶从 ht[0] 迁移到 ht[1]，在迁移拷贝完所有桶之后会将 ht[0] 空间释放，然后将 ht[1]赋值给 ht[0] ，并把 ht[1]大小重置为 0 ，并将表示设置标记 1 表示 rehash 结束了。

对于查找来说，在 rehash 的过程中，因为没有并发问题，所以查找 dict 也会依次先查找 ht[0] 然后再查找 ht[1]

设计与实现 #

Redis 的 hash 实现主要在 dict.h 和 dict.c 这两个文件中。

hash 表的数据结构大致如下所示，我就不贴出结构体的代码了，字段都标注在图上了：

从上面的图上也可以看到 hash 表中有一个空间为 2 的 dictht 数组，这个数组就是用来做 rehash 时交替保存数据用的，其中 dict 里面的 rehashidx 用来表示是否在进行 rehash 。

何时触发扩缩容？#

很多 hash 表都只有扩容，但是 dict 在 Redis 中是既有扩容，也有缩容。

扩容 #

扩容其实就是一般是在 add 元素的时候校验一下是否达到某个阈值，然后决定要不要进行扩容。所以经过搜索可以看到添加元素会调用 dictAddRaw 这个函数，我们通过函数的注释也可以知道它是 add 或查找的底层的函数。

Low level add or find:
This function adds the entry but instead of setting a value returns the dictEntry structure to the user, that will make sure to fill the value field as he wishes.

dicAddRaw 函数会调用到 _dictKeyIndex 函数，这个函数会调用 _dictExpandIfNeeded 判断是否需要扩容。

Copy ┌─────────────┐     ┌─────────┐      ┌─────────────┐      ┌─────────────────────┐ │ add or find ├────►│dicAddRaw├─────►│_dictKeyIndex├─────►│ _dictExpandIfNeeded │ └─────────────┘     └─────────┘      └─────────────┘      └─────────────────────┘

复制代码

_dictExpandIfNeeded 函数判断了大致有三种情况会进行扩容：

如果 hash 表的 size 为 0，那么创建一个容量为 4 的 hash 表；
服务器目前没有在执行 rdb 或者 aof 操作，并且哈希表的负载因子大于等于 1；
服务器目前正在执行 rdb 或者 aof 操作，并且哈希表的负载因子大于等于 5 ；

其中哈希表的负载因子可以通过公式：

Copy// load ratio = the number of elements / the bucketsload_ratio = ht[0].used / ht[0].size

复制代码

比如说，对于一个大小为 4 ，包含 4 个键值对的哈希表来说，这个哈希表的负载因子为：

Copyload_ratio = 4 / 4 = 1

复制代码

又比如说，对于一个大小为 512 ，包含 256 个键值对的哈希表来说，这个哈希表的负载因子为：

Copyload_ratio = 256 / 512 = 0.5

复制代码

为什么要根据 rdb 或者 aof 操作联合负载因子来判断是否应该扩容呢？其实源码的注释中也有提到：

as we use copy-on-write and don't want to move too much memory around when there is a child performing saving operations.

也就是说在 copy-on-write 时提高执行扩展操作所需的负载因子，可以尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存，提高子进程的操作的性能。

逻辑我们说完了，下面我们看看源码：

Copystatic int _dictExpandIfNeeded(dict *d){     // 正在扩容中    if (dictIsRehashing(d)) return DICT_OK;     // 如果 hash 表的size为0，那么创建一个容量为4的hash表    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    // hash表中元素的个数已经大于hash表桶的数量    if (d->ht[0].used >= d->ht[0].size &&        //dict_can_resize 表示是否可以扩容        (dict_can_resize ||        // hash表中元素的个数已经除以hash表桶的数量是否大于5         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))    {        return dictExpand(d, d->ht[0].used*2); // 容量扩大两倍    }    return DICT_OK;}

复制代码

通过上面的源码我们可以知道，如果当前表的已用空间大小为 size，那么就将表扩容到 size*2 的大小。新的 dict hash 表是通过 dictExpand 来进行创建的。

Copyint dictExpand(dict *d, unsigned long size){    //正在扩容，直接返回    if (dictIsRehashing(d) || d->ht[0].used > size)        return DICT_ERR;
    dictht n;      // _dictNextPower会返回 size 最接近的2的指数值    // 也就是size是10，那么返回 16，size是20，那么返回32    unsigned long realsize = _dictNextPower(size);      // 校验扩容之后的值是否和当前一样    if (realsize == d->ht[0].size) return DICT_ERR; 	// 初始化 dictht 成员变量    n.size = realsize;    n.sizemask = realsize-1;    n.table = zcalloc(realsize*sizeof(dictEntry*)); // 申请空间是 size * Entry的大小    n.used = 0;
    //校验hash 表是否初始化过，没有初始化不应该进行rehash    if (d->ht[0].table == NULL) {        d->ht[0] = n;        return DICT_OK;    }    //将新的hash表赋值给 ht[1]    d->ht[1] = n;    d->rehashidx = 0;    return DICT_OK;}

复制代码

这一段代码还是比较清晰的，可以跟着上面的注释稍微看一下就好了。

缩容 #

讲完了扩容，那么来看一下缩容。熟悉 Redis 的同学都知道，在 Redis 里面对于清理过期数据一个是惰性删除，另一个是定期删除，缩容其实也是在定期删除里面做的。

Redis 的定时器会每 100ms 调用一次 databasesCron 函数，它会调用到 dictResize 函数进行缩容：

Copy ┌─────────────┐   ┌──────────────────┐   ┌──────────┐   ┌──────────┐ │databasesCron├──►│tryResizeHashTable├──►│dictResize├──►│dictExpand│ └─────────────┘   └──────────────────┘   └──────────┘   └──────────┘

复制代码

同样的 dictResize 函数中也会判断一下是否正在执行 rehash 以及校验 dict_can_resize 是否在进行 copy on write 操作。然后将 hash 表的 bucket 大小缩小为和被键值对同样大小：

Copyint dictResize(dict *d){    int minimal;	    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;    minimal = d->ht[0].used; // 将bucket 缩小为和被键值对同样大小    if (minimal < DICT_HT_INITIAL_SIZE)        minimal = DICT_HT_INITIAL_SIZE;    return dictExpand(d, minimal);}

复制代码

最后同样调用 dictExpand 创建新的空间赋值给 ht[1]。

数据迁移如何进行？#

上面我们也提到了，无论是扩容还是缩容，创建的新的空间都会赋值给 ht[1] 以便进行数据迁移。然后在两个地方分别执行数据迁移，一个是增删改查哈希表时触发，另一个是定时触发

增删改查哈希表时触发 #

增删改查操作的时候都会检查 rehashidx 参数，校验是否正在迁移，如果正在迁移那么会调用 _dictRehashStep 函数，然后会调用到 dictRehash 函数。

但是需要注意的是，这里调用 dictRehash 函数传入的大小是 1 ，也就意味着每次只迁移 1 个 bucket。下面我们来看看 dictRehash 函数，这是整个迁移过程中最重要的函数。这个函数主要做了以下几件事：

校验当前迁移的 bucket 数量是否已达上线，并且 ht[0]是否还有元素；
判断当前的迁移的 bucket 槽位是否为空，最大访问的空槽数量不能超过 n*10，n 是本次迁移 bucket 数量；
获取到非空槽位里面 entry 链表进行循环迁移；首先获取 ht[1]新槽位的 index；一个个节点放置到新 bucket 的头部；直到全部迁移完毕；
迁移完了将旧的 hash 表 ht[0]对应的 bucket 置空；
检查如果已经 rehash 完了，那么需要 free 掉内存占用，并将 ht[1]赋值给 ht[0]；

感兴趣的可以看看下面源码，已标注好注释：

Copyint dictRehash(dict *d, int n) {    // 最大的空bucket访问次数    int empty_visits = n*10; /* Max number of empty buckets to visit. */    if (!dictIsRehashing(d)) return 0;	// 校验当前迁移的bucket数量是否已达上线，并且ht[0]是否还有元素；    while(n-- && d->ht[0].used != 0) {        dictEntry *de, *nextde;         assert(d->ht[0].size > (unsigned long)d->rehashidx);        // 判断当前的迁移的bucket槽位是否为空        while(d->ht[0].table[d->rehashidx] == NULL) {            d->rehashidx++;            if (--empty_visits == 0) return 1;        }        // 获取到槽位里面 entry 链表        de = d->ht[0].table[d->rehashidx];         // 从老的bucket迁移数据到新的bucket中        while(de) {            uint64_t h;             nextde = de->next;             // hash之后获取新hash表的bucket槽位            h = dictHashKey(d, de->key) & d->ht[1].sizemask;            // 一个个节点放置到新bucket的头部            de->next = d->ht[1].table[h];            d->ht[1].table[h] = de;            d->ht[0].used--;            d->ht[1].used++;            de = nextde;        }        // 迁移完了将旧的hash表对应的bucket置空        d->ht[0].table[d->rehashidx] = NULL;        d->rehashidx++;    }     // 如果已经rehash完了，那么需要free掉内存占用，并将ht[1]赋值给ht[0]    if (d->ht[0].used == 0) {        zfree(d->ht[0].table);        d->ht[0] = d->ht[1];        _dictReset(&d->ht[1]);        d->rehashidx = -1;        return 0;// 返回0表示迁移已完成    }     return 1; // 返回1表示迁移未完成}折叠

复制代码

定时触发 #

定时触发是由 databasesCron 函数进行定时触发，这个函数会每 100ms 运行一次，最终会通过 dictRehashMilliseconds 函数调用到我们上面提到的 dictRehash 函数。

Copy  ┌─────────────┐   ┌───────────────────┐   ┌──────────────────────┐   ┌──────────┐  │databasesCron├──►│incrementallyRehash├──►│dictRehashMilliseconds├──►│dictRehash│  └─────────────┘   └───────────────────┘   └──────────────────────┘   └──────────┘

复制代码

dictRehashMilliseconds 函数传入的 ms 参数表示可以运行多长时间，默认传入的是 1，也就是运行 1ms 就会退出这个函数：

Copyint dictRehashMilliseconds(dict *d, int ms) {    long long start = timeInMilliseconds();    int rehashes = 0;	// 每次会迁移 100 个 bucket    while(dictRehash(d,100)) {        rehashes += 100;        if (timeInMilliseconds()-start > ms) break;    }    return rehashes;}

复制代码

调用 dictRehash 函数的时候每次会迁移 100 个 bucket。

总结 #

之所有要讲 hash 表的实现是因为 Redis 中凡是需要 O(1) 时间获取 kv 数据的场景，都使用了 dict 这个数据结构，而 Redis 用的最多的也就是这种 kv 获取的场景，所以通过这篇文章我们可以清楚的了解到 Redis 的 kv 存储是怎么存放数据的，何时扩容，以及扩容是如何迁移数据的。

发布于: 刚刚阅读数: 3

Java快了！

关注

还未添加个人签名 2022.09.03 加入

还未添加个人简介

发布

暂无评论

创作场景

透过 Redis 源码探究 Hash 表的实现，你学废了吗？

概述 #

设计与实现 #

何时触发扩缩容？#

扩容 #

缩容 #

数据迁移如何进行？#

增删改查哈希表时触发 #

定时触发 #

总结 #

Java快了！

评论