03 | 如何实现一个性能优异的Hash表？

说下我是怎么找到这个 Hash 函数的吧。有点艰辛... （1）文中也提到了 rehash 的主要函数就是 dictRehash 函数，所以我们可以直接在这个函数里面找： h = dictHashKey(d, de->key) & d->ht[1].sizemask; 代码含义：根据扩容后的哈希表ht[1]大小，计算当前哈希项在扩容后哈希表中的bucket位置。 （2）点进这个方法里面，发现如下： \#define dictHashKey(d, key) (d)->type->hashFunction(key) 最后调用的是一个 hashFunction，但是你会发现，不能跳转到这个方法里面。这样来看似乎线索断了。 （3）我们可以 hashFunction 是被 type 调用的，那么这个 type 其实 dict 的一个属性。那我们就直接去看下 dict 结构体，再 dict.h 中定义了 struct dict。里面可以找到 type 属性： dictType *type; 那这个 dictType 又是什么呢？ （4）我们点进去看下，发现 dictType 也是一个结构体，定义了 hash 函数的指针： uint64_t (*hashFunction)(const void *key); 但是这里还是没有看到指针指向哪个 hash 函数，线索似乎又断了。 （5）这个时候，只能到 dict.c 中看下有没有线索。发现有一个 dictCreate 函数，里面指定了 type： dict *dictCreate(dictType *type, void *privDataPtr) 所以我们只要找到调用 dictCreate 的地方，看下传的什么 type 就知道调用的是哪个 hash 函数了。 （6）全局搜 dictCreate 函数。发现有 53 个地方调用了，第一个文件时 deps\hiredis\async.c，到这里，其实再点进去没有意义了，因为 deps 文件夹属于第三方依赖库，和 redis 的核心源码没有关系，那就继续找。 （7）把 deps 排除掉，剩余 49 个结果，第一个是 cluster.c 中调用的，cluster 是 Redis 集群初始化相关的 server.cluster->nodes = dictCreate(&clusterNodesDictType,NULL); 这里用到的 clusterNodesDictType 中指定了 Hash 函数：dictSdsHash （8）dictSdsHash 点进去，发现还是回到了 dict.c 文件中，调用了 dictGenHashFunction 函数，如下所示： uint64_t dictGenHashFunction(const void *key, int len) { return siphash(key,len,dict_hash_function_seed); } 调用的就是 siphash 函数，这就是我们要找的 hash 函数。 （9）siphash 点进去，跳转到了 siphash.c 文件，定义了 siphash 函数。 （10）第 7 步中，搜索结果我是看的 cluster.c 文件，如果想看下 Redis 服务端初始化相关的代码，就在 server.c 中找。搜索结果中有一条相关的，初始化 Redis 数据库： server.db[j].dict = dictCreate(&dbDictType,NULL); dbDictType 点进去，发现用到了 dictSdsHash 函数： 再从 dictSdsHash 函数点进去，发现还是用到了 dict.c 中的 dictGenHashFunction 函数，和第十步找到的一样，同一个 dictGenHashFunction 函数，顿时感觉神清气爽。 ------ 总结： 1. 其实可以直接从 server.c 中来找创建 dict 的地方，会省很多步，这是一个正向的思维，但往往排查问题时，我们用的是逆向思维，虽然逆向思维苦了点，但是会有一种柳暗花明又一村的感觉。 2. 寻找的过程比较艰辛，但是对源码理解更深了。 3. 可以看 Redis 5 设计与源码实现作为本专栏的补充。比如缩容时也会触发渐见式 hash。当使用量不到总空间 10% 时，则进行缩容。缩容时空间大小则为能恰好包含 d->ht[0].used 个节点的 2^N 次方幂整数，并把字典中字段 rehashidx 标识为 0。在 server.h 文件中有定义：#define HASHTABLE_MIN_FILL 10。

老师，您好！我有个疑问，dictRehash 进行迁移n个桶 ，这个n是固定吗？如果不是固定怎么确定呢？

老师，当负载因子 > 5 的时候，是不是就不再考虑有没有 RDB 或者 AOF 进程在运行？？

1、Redis 中的 dict 数据结构，采用「链式哈希」的方式存储，当哈希冲突严重时，会开辟一个新的哈希表，翻倍扩容，并采用「渐进式 rehash」的方式迁移数据 2、所谓「渐进式 rehash」是指，把很大块迁移数据的开销，平摊到多次小的操作中，目的是降低主线程的性能影响 3、Redis 中凡是需要 O(1) 时间获取 k-v 数据的场景，都使用了 dict 这个数据结构，也就是说 dict 是 Redis 中重中之重的「底层数据结构」 4、dict 封装好了友好的「增删改查」API，并在适当时机「自动扩容、缩容」，这给上层数据类型（Hash/Set/Sorted Set）、全局哈希表的实现提供了非常大的便利 5、例如，Redis 中每个 DB 存放数据的「全局哈希表、过期key」都用到了 dict： // server.h typedef struct redisDb { dict *dict; // 全局哈希表，数据键值对存在这 dict *expires; // 过期 key + 过期时间 存在这 ... } 6、「全局哈希表」在触发渐进式 rehash 的情况有 2 个： - 增删改查哈希表时：每次迁移 1 个哈希桶（文章提到的 dict.c 中的 _dictRehashStep 函数） - 定时 rehash：如果 dict 一直没有操作，无法渐进式迁移数据，那主线程会默认每间隔 100ms 执行一次迁移操作。这里一次会以 100 个桶为基本单位迁移数据，并限制如果一次操作耗时超时 1ms 就结束本次任务，待下次再次触发迁移（文章没提到这个，详见 dict.c 的 dictRehashMilliseconds 函数） （注意：定时 rehash 只会迁移全局哈希表中的数据，不会定时迁移 Hash/Set/Sorted Set 下的哈希表的数据，这些哈希表只会在操作数据时做实时的渐进式 rehash） 7、dict 在负载因子超过 1 时（used: bucket size >= 1），会触发 rehash。但如果 Redis 正在 RDB 或 AOF rewrite，为避免父进程大量写时复制，会暂时关闭触发 rehash。但这里有个例外，如果负载因子超过了 5（哈希冲突已非常严重），依旧会强制做 rehash（重点） 8、dict 在 rehash 期间，查询旧哈希表找不到结果，还需要在新哈希表查询一次 课后题：Hash 函数会影响 Hash 表的查询效率及哈希冲突情况，那么，你能从 Redis 的源码中，找到 Hash 表使用的是哪一种 Hash 函数吗？ 找到 dict.c 的 dictFind 函数，可以看到查询一个 key 在哈希表的位置时，调用了 dictHashKey 计算 key 的哈希值： dictEntry *dictFind(dict *d, const void *key) { // 计算 key 的哈希值 h = dictHashKey(d, key); ... } 继续跟代码可以看到 dictHashKey 调用了 struct dict 下 dictType 的 hashFunction 函数： // dict.h dictHashKey(d, key) (d)->type->hashFunction(key) 而这个 hashFunction 是在初始化一个 dict 时，才会指定使用哪个哈希函数的。 当 Redis Server 在启动时会创建「全局哈希表」： // 初始化 db 下的全局哈希表 for (j = 0; j < server.dbnum; j++) { // dbDictType 中指定了哈希函数 server.db[j].dict = dictCreate(&dbDictType,NULL); ... } 这个 dbDictType struct 指定了具体的哈希函数，跟代码进去能看到，使用了 SipHash 算法，具体实现逻辑在 siphash.c。 （SipHash 哈希算法是在 Redis 4.0 才开始使用的，3.0-4.0 使用的是 MurmurHash2 哈希算法，3.0 之前是 DJBX33A 哈希算法）

首先回答老师的提问：Redis使用的hash函数算法是siphash，其代码位于siphash.c的siphash函数中，上层函数是dictGenHashFunction 【注意】：在查找dictGenHashFunction的时候如果发现算法是time33，其实你找到的是C的redis客户端框架hiredis实现的hash函数，并不是redis本身的hash函数 此外阅读完文章我产生了三个问题并且自己给出自己的理解： 问题一： redis的dict结构核心就是链式hash，其原理其实和JDK的HashMap类似（JDK1.7之前的版本，1.8开始是红黑树或链表），这里就有一个问题为什么Redis要使用链式而不引入红黑树呢，或者直接使用红黑树？ 答： 1、hash冲突不使用红黑树：redis需要高性能，如果hash冲突使用红黑树，红黑树和链表的转换会引起不必要的开销（hash冲突不大的情况下红黑树其实比链表沉重，还会浪多余的空间） 2、dict不采用红黑树：在负载因子较低，hash冲突较低的情况下，hash表的效率O(1)远远高于红黑树 3、当采用渐进式rehash的时候，以上问题都可以解决 问题二： 何为渐进式rehash？本质原理是什么？当内存使用变小会缩容吗？ 答： 1、渐进式rehash的本质是分治思想，通过把大任务划分成一个个小任务，每个小任务只执行一小部分数据，最终完成整个大任务的过程 2、渐进式rehash可以在不影响运行中的redis使用来完成整改hash表的扩容（每次可以控制只执行1ms） 3、初步判定会，因为dictResize中用于计算hash表大小的minimal就是来源于实际使用的大小，并且htNeedsResize方法中（used*100/size < HASHTABLE_MIN_FILL）来判断是否触发缩容来节约内存，而缩容也是渐进式rehash 问题三： 渐进式rehash怎么去执行？ 答： 在了解渐进式rehash之前，我们需要了解一个事情，就是正在运行执行任务的redis，其实本身就是一个单线程的死循环（不考虑异步以及其他fork的场景），其循环的方法为aeMain(),位于ae.c文件中，在这个循环中每次执行都会去尝试执行已经触发的时间事件和文件事件，而渐进式rehash的每个小任务就是位于redis，serverCron时间事件中，redis每次循环的时候其实都会经过如下所示的调用流程： 1、serverCron -> updateDictResizePolicy (先判断是否能执行rehash，当AOF重写等高压力操作时候不执行) 2、serverCron -> databasesCron -> incrementallyRehash -> dictRehashMilliseconds -> dictRehash (dictRehashMilliseconds默认要求每次rehash最多只能执行1ms) 通过这种方式最终完成整改hash表的扩容

咨询个问题，当部分bucket 执行 rehash，部分bucket还没有执行rehash，这时增删查请求操作是对ht[1]操作，还是ht[0]，谢谢

为啥说dictht里的**table是一个二维数组啊，不是一个二级指针的一位数组吗？

需要注意的是在渐进式rehash的过程，如果有增删改查操作时，如果index大于rehashindex，访问ht[0]，否则访问ht[1]

Hash 表使用的是哪一种 Hash 函数? 各个类型的 dictType 在 server.c 中被初始化，常用的包括 setDictType、zsetDictType 以及 16 个 database 所使用的 dbDictType。 此时就可以找到 hashFunction 的实现为 dictSdsHash()，最终的底层实现为 siphash()。 dict 对象的使用除了理解最基本的拉链法处理哈希冲突、使用渐进式 rehash 的方式进行扩容以外，我认为还需要从全局的角度来考虑。也就是 Redis Server 在运行时 使用了哪些功能的 dict。这部分内容可以在 server.c/initServer() 方法中找到答案: ``` for (j = 0; j < server.dbnum; j++) { // 创建基础 hashmap，也就是 set key value 所使用的 hashmap server.db[j].dict = dictCreate(&dbDictType,NULL); // 创建 expires hashmap，用于实现 TTL，调用可见 dbAsyncDelete() server.db[j].expires = dictCreate(&dbExpiresDictType,NULL); // 创建 blocking_keys hashmap，用于记录阻塞信息，调用可见 serveClientsBlockedOnListKey() server.db[j].blocking_keys = dictCreate(&keylistDictType,NULL); // 创建 ready_keys hashmap，调用可见 handleClientsBlockedOnKeys() server.db[j].ready_keys = dictCreate(&objectKeyPointerValueDictType,NULL); // 创建 watched_keys hashmap，调用可见 watchForKey() server.db[j].watched_keys = dictCreate(&keylistDictType,NULL); ...... } ``` 也就是说，Redis 在启动时将会创建 16 * 5 个功能性的 dict，这些 dcit 是实现 TTL、BLPOP/BRPOP 等功能的关键组件。

老师你好，有几个问题想请教下： 1、判断是否扩容并rehash的条件是d->ht[0].used >= d->ht[0].size &&(dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)，这句逻辑好像不对？应该写成d->ht[0].used >= d->ht[0].size && dict_can_resize || d->ht[0].used/d->ht[0].size > dict_force_resize_ratio？ 2、在函数dictRehash中有一段代码是 assert(d->ht[0].size > (unsigned long)d->rehashidx)，这是断言rehashidx是否越界，rehashidx为什么会有越界的情况？ 3、另外问个代码上的问题（有可能钻牛角尖了），作为性能抠的很细的redis来说，在计算新哈希表大小的时候需要从初始大小4频繁*2得到最终size，这里为什么不直接用移位操作提升效率？