聊聊 Redis 中的字典设计与实现

发布时间：2025-11-04 06:49:07 来源：技术快报 作者：数据库

Redis作为非关系数据库，聊聊其底层采用了字典(也称为映射)保存键值对。字典设本文会基于源码分析的计实方式带你了解redis中这一常见数据结构的精巧设计，希望对你有帮助。聊聊

我们简单说明一下redis字典数据结构特征：

可能上文说的计实比较抽象，我们不妨举个例子，聊聊假设我们现在键入如下指令:

redis完成命令解析后，字典设定位到student这个key对应的计实字段空间的字典，找到当前正在使用的聊聊哈希表，按照如下步骤完成键值对存储：

我们可以在dict.h看到上文所提及的哈希表和字典中每一个元素的数据结构：

上文我们讲解了哈希结构，而哈希表在极端算法情况下会造成大量键值对冲突碰撞的情况，导致查询效率由原来的O(1)变为O(n)，所以为了保证针对冲突的数组进行优化，redis的字典采用的双数组的方式管理键值对，所以这一小节我们着重说明redis如何基于字典管理两个哈希表空间。

对应的我们也可以在dict.h看到dict 的定义，企商汇可以看到字典维护哈希表字段ht是一个空间为2的数组：

如下图所示，可以看到dict的数据结构定义了大小为2的哈希表数组，当某个哈希表碰撞激烈需要进行调整时，就会采用渐进式哈希算法将键值对存到dictht[1]，并通过rehashidx标志为-1表示当前处于渐进式哈希阶段：

进行键值对创建时，dictCreate会进行必要的内存分配，然后进入初始化工作：

对应的我们可以在dict.c中看到dictCreate函数的源代码：

字典的插入操作大体流程也很市面上常见的哈希表实现差不多，通过哈希算法(MurmurHash2)定位元素插入的位置再进行插入操作，唯一有所区别的是，redis版本字典的链地址法解决冲突的上的云南idc服务商优化，为了保证哈希定位的位置存在元素时能够快速插入，redis字典的插入采用的是头插法，即将最新的元素作为链表头元素插入:

与之对应的我们给出代码的入口，也就是dict.c下的dictAdd方法，可以看到其内部是通过完成键的添加，只有key插入成功后才会通过setVal方法维护插入的entry的值：

dictAddRaw逻辑也比较简单，先检查当前的字典表是否因为大量冲突而处理渐进式哈希(关于渐进式哈希后文会详细讲解，这里也补充一些简单的概念)，通过_dictKeyIndex定位到当前元素插入的索引位置，采用头插法将其插入到对应索引位置的链表首部：

随着我们不断的新增键值对，当前的哈希算法得到的索引位置很大概率会出现哈希冲突，即每次定位到的索引位置都很大概率存在元素，这也就是我们的常说的哈希冲突，这就是redis的字典默认会初始化两张哈希表的原因所在。

符合以下两个条件时，字典就会触发扩容机制:

触发扩容时，字典会将rehashidx设置为0意为当前因为大量冲突碰撞而从0索引开始渐进式再哈希，ht[1]就会基于ht[0]数组长度创建一个其2倍的数组空间，后续的新插入的元素也都会根据哈希算法将元素插入到ht[1]中。

对于旧有存在的元素，考虑到整个哈希表可能存在不可预估数量的键值对，redis的字典会通过渐进式哈希的方式在元素每次进行增删改查操作时将旧有元素逐批次迁移到ht[1]中，一旦所有元素全部迁移到ht[1]后，哈希表就会将ht[1]指向的哈希表指针赋值给ht[0]，并将ht[0]原有哈希表释放。

了解整体的设计之后，我们就可以从源码角度印证这个问题了，可以看到字典在每次进行哈希索引定位时都会调用_dictKeyIndex方法，而该方法内部则有一个_dictExpandIfNeeded操作，其内部就会根据我们上文所说的阈值判断当前哈希表是否需要进行扩容:

我们继续步入_dictExpandIfNeeded即可看到扩容判断的逻辑，也就是我们上文所说的符合两个扩容条件：

只要符合上述的条件，该函数就会调用dictExpand触发扩容，并将rehashidx设置为0即代表从数组0的索引0位置尝试渐进式驱逐：

此时我们再回看之前的键值对插入操作，它会根据dictIsRehashing判断rehashidx是否为0以确定是否处于渐进式再哈希，从而调用_dictRehashStep进入渐进式哈希操作在键值对维护：

我们直接查看_dictRehashStep内部的实现就可以看到一个dictRehash的函数，它就是渐进式哈希的核心实现，该方法会从0开始每次驱逐10个元素到ht[1]中：

有了上述的基础后，我们查看查询操作就比较简单了，其步骤比较固定：

同理我们最后给出删除操作的源码，也查询操作一样，定位到元素后，将其从索引位置中解除该元素和前驱节点关系即可：

相关文章