redis 字典（dict）深入分析（抓住两个核心要点）

本文已参与「新人创作礼」活动，一起开启掘金创作之路。

本文参考源码版本为 redis6.2

字典又称散列表，是用来存储键值（key-value）对的一种数据结构，在很多高级语言中都有实现，如 PHP 的数组。但是 C 语言没有这种数据结构，Redis 是 K-V 型数据库，整个数据库是用字典来存储的，对 Redis 数据库进行任何增、删、改、查操作，实际就是对字典中的数据进行增、删、改、查操作。

根据 Redis 数据库的特点，便可知字典有如下特征。

字典又称散列表，英文叫 “Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”，

散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。 简单来说，为了将我们的 key 映射到 hash table 上，中间通过散列计算，尽可能均匀的映射到 hash table 上。

散列函数：

散列函数，顾名思义，它是一个函数。我们可以把它定义成 hash(key)，其中 key 表示元素的键值，hash(key) 的值表示经过散列函数计算得到的散列值。

上图中，将 key001 映射为散列表的下标 0 的 hash(key)，便是我们的散列函数。

散列冲突：

虽然散列函数会尽可能的使数据均匀分布在 hash 表中，但仍然存在将多个不同的 key 映射到同一个 hash 表的下标上。这就是散列冲突，主要有以下几种解决方式：

1）开放寻址法：

核心思想：如果出现散列冲突，就重新探测一个空闲位置，将其插入。

经典的探测算法有线性探测法、二次探测、双重散列三种；这里，我们以 线性探测 为例，简单讲讲其原理。

线性探测的原理是，当我们往散列表中插入数据时，如果某个数据经过散列函数散列之后，存储位置已经被占用了，我们就从当前位置开始，依次往后查找，看是否有空闲位置，直到找到为止。 可以看到， key001、key002 经过 hash 计算都映射到了 hash[3]，即同一个索引下标 3 上，产生了 hash 冲突。 最终，处理 hash 冲突之后，数据映射在下标 3、4。当然，这是在理想的情况下，经过一步操作就能找到合适位置，当 hash 表元素很多并且装载较满时，可能经过很多步都无法找到合适位置的时候，这时，性能将急剧下降。

开放寻执法适用场景：当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

2）链表法：

相较于开放寻址法的顺位寻找可用 hash 槽的做法，链表法直接摒弃了这一做法，而是在映射的 hash 槽位上处理；这样一来，同一个 hash 槽位上可能出现多个元素，这个时候，采用链表将其串联起来。

适用场景：基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

如何设计散列函数？

在极端情况下，所有的数据经过散列函数之后，都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法，那这个时候，散列表就会退化为链表，查询的时间复杂度就从 O(1) 急剧退化为 O(n)。

如果散列表中有 10 万个数据，退化后的散列表查询的效率就下降了 10 万倍。更直接点说，如果之前运行 100 次查询只需要 0.1 秒，那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。

散列函数的设计上要考虑两个原则：

首先，散列函数的设计不能太复杂。过于复杂的散列函数，势必会消耗很多计算时间，也就间接地影响到散列表的性能。

其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。

装载因子过大了怎么办？

装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。

针对数组的扩容，数据搬移操作比较简单。但是，针对散列表的扩容，数据搬移操作要复杂很多。因为散列表的大小变了，数据的存储位置也变了，所以我们需要通过散列函数重新计算每个数据的存储位置。

插入一个数据，最好情况下，不需要扩容，最好时间复杂度是 O(1)。最坏情况下，散列表装载因子过高，启动扩容，我们需要重新申请内存空间，重新计算哈希位置，并且搬移数据，所以时间复杂度是 O(n)。用摊还分析法，均摊情况下，时间复杂度接近最好情况，就是 O(1)。

装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。

装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。

如何避免低效扩容？

大部分情况下，动态扩容的散列表插入一个数据都很快，但是在特殊情况下，当装载因子已经到达阈值，需要先进行扩容，再插入数据。这个时候，插入数据就会变得很慢，甚至会无法接受。

如果我们的业务代码直接服务于用户，尽管大部分情况下，插入一个数据的操作都很快，但是，极个别非常慢的插入操作，也会让用户崩溃。这个时候，“一次性”扩容的机制就不合适了。

为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。

当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。

这期间的查询操作怎么来做呢？对于查询操作，为了兼容了新、老散列表中的数据，我们先从新散列表中查找，如果没有找到，再去老的散列表中查找。

通过这样均摊的方法，将一次性扩容的代价，均摊到多次插入操作中，就避免了一次性扩容耗时过多的情况。这种实现方式，任何情况下，插入一个数据的时间复杂度都是 O(1)。

在第一部分，我们已经介绍了字典的基本原理，以及在解决实际问题中需要去处理的几大关键问题。因此，我们接下来看看，redis 如何结合自身场景去解决这几大问题。

还是这张图，redis 的字典实现本质上就是这种模式，即，链表法。

相信你也已经明白，这里的哈希算法对应我们上面的 hash(key)，需要解决与 hash 表的映射关系。同时，hash 算法的优劣程度基本决定了 hash 表的性能关键。

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis 使用 MurmurHash2 算法来计算键的哈希值。

MurmurHash 算法最初由 Austin Appleby 于 2008 年发明，这种算法的优点在于，即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，并且算法的计算速度也非常快。

MurmurHash 算法目前的最新版本为 MurmurHash3，而 Redis 使用的是 MurmurHash2，关于 MurmurHash 算法的更多信息可以参考该算法的主页：code.google.com/p/smhasher/…

在上面我们已经介绍过散列冲突，以及两大类解决方案及其应用场景。相信你也很清楚，针对 redis 这种大量数据的场景，可以使用我们说到的 链表法 解决冲突。

没错，redis 正是使用 链地址法 解决冲突。

redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题。

通俗的说，hash 表在使用的过程中，数据越来越密集，这个时候会考虑进行扩容以维持 hash 表的高效性；反之为缩容。

其中，习惯性将控制 hash 表元素疏密程度的，叫做 负载因子，需要考虑将其维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行 rehash（重新散列）操作来完成，Redis对字典的哈希表执行 rehash 的步骤如下：

1）为字典的 ht[1] 哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及 ht[0]当前包含的键值对数量（也即是 ht[0].used 属性的值）：

直接看源码，更清晰。

2）将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。

3）当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后（ht[0] 变为空表），释放 ht[0]，将 ht[1]设置为 ht[0]，并在 ht[1] 新创建一个空白哈希表，为下一次 rehash 做准备。

哈希表的扩展与收缩

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行，服务器执行扩展操作所需的负载因子并不相同，这是因为在执行 BGSAVE 命令或 BGREWRITEAO F命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）技术来优化子进程的使用效率。

所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。

另一方面，当哈希表的负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作。

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1] 里面，但是，这个 rehash 动作并不是一次性、集中式地完成的，而是分多次、渐进式地完成的。

这样做的原因在于，如果 ht[0] 里只保存着四个键值对，那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht[1]；但是，如果哈希表里保存的键值对数量不是四个，而是四百万、四千万甚至四亿个键值对，那么要一次性将这些键值对全部 rehash 到 ht[1] 的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

因此，为了避免 rehash 对服务器性能造成影响，服务器不是一次性将 ht[0] 里面的所有键值对全部 rehash 到 ht[1]，而是分多次、渐进式地将 ht[0] 里面的键值对慢慢地 rehash 到ht[1]。

以下是哈希表渐进式 rehash 的详细步骤：

渐进式 rehash 的好处在于它采取分而治之的方式，将 rehash 键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免了集中式 rehash 而带来的庞大计算量。

渐进式 rehash 执行期间的哈希表操作因为在进行渐进式 rehash 的过程中，字典会同时使用ht[0] 和 ht[1] 两个哈希表，所以在渐进式 rehash 进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。

例如，要在字典里面查找一个键的话，程序会先在 ht[0] 里面进行查找，如果没找到的话，就会继续到 ht[1] 里面进行查找，诸如此类。

另外，在渐进式 rehash 执行期间，新添加到字典的键值对一律会被保存到 ht[1] 里面，而ht[0] 则不再进行任何添加操作，这一措施保证了 ht[0] 包含的键值对数量会只减不增，并随着 rehash 操作的执行而最终变成空表。

字典结构在 redis 中使用比较广泛，比如我们常说 redis 是 K-V 存储结构，其中，这个主数据库就是用字典来存储 K-V 结构。

除此之外，还有很多其他地方会用到。例如，Redis 的哨兵模式，就用字典存储管理所有的Master 节点及 Slave 节点；

再如，数据库中键值对的值为 Hash 类型时，存储这个 Hash 类型的值也是用的字典。在不同的应用中，字典中的键值对形态都可能不同，而 dictType 结构体，则是为了实现各种形态的字典而抽象出来的一组操作函数。

redis 字典实现依赖的数据结构主要包含了三部分：字典、hash表、hash表节点。字典中嵌入了两个 hash 表，hash 表中的 table 字段存放着 hash 表节点，hash 表节点对应存储的是键值对。整体结构如下：

1）字典

其主要作用是对散列表再进行一层封装，当字典需要进行一些特殊操作时要用到里面的辅助字段。

在不同的应用中，字典中的键值对形态都可能不同，而 dictType 结构体，则是为了实现各种形态的字典而抽象出来的一组操作函数。

2）hash 表：

hash 表的结构体整体占用 32 字节，其中 table 字段是数组，作用是存储键值对，该数组中的元素指向的是 dictEntry 的结构体，每个 dictEntry 里面存有键值对。size 表示 table 数组的总大小。used 字段记录着 table 数组已存键值对个数。

sizemask 字段用来计算键的索引值，sizemask 的值恒等于 size-1。

3）hash 表节点：

hash 表中元素结构体和我们前面自定义的元素结构体类似，整体占用 24 字节，key 字段存储的是键值对中的键。v 字段是个联合体，存储的是键值对中的值，在不同场景下使用不同字段。

例如，用字典存储整个 redis 数据库所有的键值对时，用的是 *val字段，可以指向不同类型的值；再比如，字典被用作记录键的过期时间时，用的是s64字段存储；

当出现了 hash 冲突时，next 字段用来指向冲突的元素，通过头插法，形成单链表。

在 redis-server 启动中，整个数据库会先初始化一个空的字典用于存储整个数据库的键值对。初始化一个空字典，调用的是dict.h文件中的 dictCreate 函数，对应源码为：

dictCreate 函数初始化一个空字典的主要步骤为：申请空间、调用_dictInit 函数，给字典的各个字段赋予初始值。

1）dictAdd：

dictAdd函数主要作用是，添加键值对，执行步骤如下。

1）调用 dictAddRaw 函数，添加键，字典中键已存在则返回 NULL，否则添加键至 hash 表中，并返回新加的 hash 节点。

2）给返回的新节点设置值，即更新其 val 字段。

2）dictAddRaw：

dictAddRaw 函数主要作用是添加或查找键，添加成功返回新节点，查找成功返回 NULL 并把旧节点存入 existing 字段。

该函数中比较核心的是调用 _dictKeyIndex 函数，作用是得到键的索引值，有这么两步:

1．字典扩容

随着 redis 数据库添加操作逐步进行，存储键值对的字典会出现容量不足，达到上限，此时就需要对字典的 hash 表进行扩容，扩容对应的源码是 dict.h 文件中的 dictExpand 函数。

扩容主要流程为：

当然，这里不仅可以将空间扩大，也可以缩小。

2．渐进式rehash

rehash 除了扩容时会触发，缩容时也会触发。redis 整个 rehash 的实现，主要分为如下几步完成。

redis 优化的思想很巧妙，利用分而治之的思想了进行 rehash 操作，大致的步骤如下。

执行插入、删除、查找、修改等操作前，都先判断当前字典 rehash 操作是否在进行中，进行中则调用 dictRehashStep 函数进行 rehash 操作（每次只对1个节点进行rehash操作，共执行1次）。

除这些操作之外，当服务空闲时，如果当前字典也需要进行 rehsh 操作，则会调用incrementallyRehash 函数进行批量r ehash 操作（每次对100个节点进行rehash操作，共执行1毫秒）。

在经历 N 次 rehash 操作后，整个 ht[0] 的数据都会迁移到 ht[1] 中，这样做的好处就把是本应集中处理的时间分散到了上百万、千万、亿次操作中，所以其耗时可忽略不计。

查找键的源码，整个过程比较简单，主要分如下几个步骤。

dict.h 文件中的 dictDelete 函数，其主要的执行过程为：

主要流程：

当字典中数据经过一系列操作后，使用量不到总空间ht[0].used; if (minimal < DICT_HT_INITIAL_SIZE) // 容量最小值为4 minimal = DICT_HT_INITIAL_SIZE; return dictExpand(d, minimal); // 将容量调整到指定大小 }

整个缩容的步骤大致为：判断当前的容量是否达到最低阈值，即 used/size < 10%，达到了则调用 dictResize 函数进行缩容，缩容后的函数容量实质为 used 的最小 2^N 整数。缩容操作和扩容操作实质差不多，最终调用的都是 dictExpand 函数，之后的操作与扩容一致。

从 redis 的源码中我们可以看到，有多个地方通过调用 _dictRehashStep 函数，进而调用 dictRehash 函数，来执行 rehash，它们分别是：dictAddRaw，dictGenericDelete，dictFind，dictGetRandomKey，dictGetSomeKeys。

不管是增删查哪种操作，这 5 个函数调用的 _dictRehashStep 函数，给 dictRehash 传入的循环次数变量 n 的值都为 1:

这样一来，每次迁移完一个 hash 槽，hash 表就会执行正常的增删查请求操作，这就是在代码层面实现渐进式 rehash 的方法。

在实现 rehash 时，都需要解决哪些问题？主要有以下三点：什么时候触发 rehash？rehash 扩容扩多大？rehash 如何执行？ 结合文章，你可以自己思考总结下。

实现一个高性能的 hash 表不仅是 redis 的需求，也是很多计算机系统开发过程中的重要目标。而要想实现一个性能优异的 hash 表，就需要重点解决哈希冲突和 rehash 开销这两个问题。

好，至此，你已经理解了本文两大核心：哈希冲突 和 rehash 开销，你以为就结束了吗？

答案是否定的，均摊法思维引入的渐进式 rehash 解决了高效扩容问题的同时，也给字典的遍历带来了一定困难；关于字典的遍历问题，咱们下篇接着聊～