上一篇文章详细介绍了Redis的五种常用数据类型，每种数据类型在内存中的数据结构都会因情况而异。接下来，我会用几篇文章来详细解析这一系列数据结构，这篇文章我们先来解析一下Redis中用得最多的dict（字典）结构。

1. 字典在Redis中的应用

字典，是一种保存键值对的数据结构，相比采用其他数据结构来保存key-value，在字典中查找键值对的平均时间复杂度为O(1)。

经过上一篇文章的学习，我们可以知道：Redis中的hash、set、zset底层实现都包含字典，具体是怎么通过字典来实现这几种数据类型的，大家可以翻看上一章。除此之外，其实整个Redis数据库都是用字典来保存数据的，众所周知，Redis是一个key-value型的内存存储组件，这一点与字典的特性不谋而合。具体Redis如何在数据库层面使用字典，接下来我会写一篇文章带大家俯瞰Redis数据库，在这里就先不引申太多（卖个关子 😋 ）。

2. Redis中字典的实现

Redis中的字典是使用dict结构来实现的，每个dict包含两个哈希表dictht，dictht[0]用于日常保存数据，dictht[1]只有在rehash时才会用到（哈希表在扩容或者缩容时需要rehash，将哈希表中的数据重新hash到不同的槽位上，使得元素分配更均匀）。每个哈希表都是由dictEntry节点组成的二维结构，一维是dictEntry数组，每个数组元素都由dictEntry链表构成，这就形成了二维结构。

Redis字典.png

接下来，我们对照着上图详细解析下字典中各个模块的属性。

dict

dict即Redis的字典，里面的每个属性都是在字典层面的。

• type和privdata属性都是为了实现多态字典而设置的，只有实现了多态字典才能通过dict结构来保存string、hash、set等不同类型的数据。type指针指向dictType结构，每个dictType结构定义了一系列操作不同类型键值对的函数。而privdata则保存了需要传给特定类型函数的可选参数。
• dictht数组保存了两个哈希表，第一个哈希表用于日常保存数据，另一个则在rehash时保存新哈希表使用。
• rehashidx属性标记着当前字典是否正在rehash，如果没有在rehash则为-1。

dictht

dictht是哈希表，它直接连接着装载着dictEntry链表的数组。

• table是哈希表数组，数组中的每个元素都是一个链表，因此形成了一个二维结构，字典中的数据都存储在这个二维结构里面。
• size是哈希表数组的大小，不是直接指元素的个数。
• sizemask是哈希表数组大小的掩码，取值为size-1。扩容后可通过hash(key) & sizemask算出数组下标。
  sizemask.png
• used表示哈希表已有节点的数量，即dictEntry的总数。

dictEntry

dictEntry是哈希表的节点，每个key-value数据都保存在dictEntry里面。

• key指针指向哈希表中的键。
• v用于保存字典的值，它是一个union（联合体），联合体中的u64和s64可直接保存64位的整数值。如果值不是整数，则通过指针val来指向数据所在内存。
• next指向下一个dictEntry节点，一系列dictEntry可通过next指针串成一个链表。

2. 字典中的插入与查询

要往字典里插入数据，必须先找到要插入的下标，计算下标常用的方法是对key的hash值取模，即hash(key) % size。

当数组对应下标存在元素时，则产生了键冲突。Redis中解决键冲突的方法是链地址法，将插入数据的next指针指向数组中对应下标的元素，再将插入数据存入该下标。出于速度考虑Redis不是将新元素插入链尾，而是插入链头，这样做可省去遍历链表找到链尾节点的开销。

链地址法.png

查找key时，先通过key的hash值找到对应的下标，遍历该下标存储的链表，直到找到对应的key。理想情况下每个数组下标只有一个节点，只需定位数组的开销，时间复杂度为O(1)。

3. 哈希表的扩容与缩容

当哈希表中的元素太多或太少时，会进行扩容或者缩容。扩容是出于哈希表的查找效率考虑，当哈希表中的元素达到一定数量时，表中链的长度会随着哈希表元素的增长而增长，链表越长意味着查询效率也会越慢。缩容是为了节省内存空间，避免数组中太多空元素造成空间浪费。

Redis中的哈希表通过load_factor（负载因子）来决定是否扩容或者缩容，负载可由公式ht[0].used/ht[0].size算得，即为哈希表中元素个数与数组大小之比。哈希表中的元素越多，数组中的元素就越倾向于形成链表；反之则数组中空置的“坑位”也就越多。因此负载因子可作为哈希表扩缩容的指标。

扩容

扩容时需考虑服务器当前是否正在执行bgsave或者bgrewriteaof，若服务器当前正在bgsave或bgrewriteaof，应该尽量避免扩容，此时触发扩容的条件是load_factor为5；否则当load_factor为1时就开始扩容。之所以要这样做，是因为bgsave或bgrewriteaof命令会fork子进程来遍历内存，若内存无变更则与父进程共享内存页，修改内存数据时需将内存页拷贝一份出来进行修改（这就是传说中的写时复制），修改内存数据不但在拷贝内存页时会消耗CPU资源，而且会消耗更多的内存空间。而扩容时需要将旧哈希表元素rehash到新哈希表，从而造成内存数据变更，因此要尽量避免扩容。

为了方便rehash，扩容时数组容量会扩展到（第一个大于2倍哈希表元素个数）的2^n。这句话有点绕，举个例子：假如哈希表中有3个元素，扩容时先算出2倍元素个数为6，但是6不满足2^n， 因此要扩为8，因为2^2<6<2^3。通过这种扩容策略，新数组的大小为旧数组大小的2^n 倍，rehash时可以直接通过公式hash(key) & sizemask来算出下标。

扩容.png

缩容

缩容则不需要考虑bgsave或者bgrewriteaof，当负载因子为0.1时会触发缩容。缩容时也需要进行rehash操作，数组长度会缩减为（第一个大于哈希表元素个数）的2^n，新下标也可通过公式hash(key) & sizemask算出来。

缩容.png

4. 渐进式rehash

上面说到，哈希表在扩容和缩容时都需要rehash，由于Redis是单线程处理的，如果字典中的元素太多，一次性执行rehash操作会造成卡顿，因此Redis采用渐进式rehash的策略，在某个key被访问时对其进行迁移，如果某个key一直没有被访问，Redis会在定时任务中对其执行rehash。

渐进式rehash.png

上图简略展示了渐进式rehash的过程，除了两个哈希表ht[0]和ht[1]之间会发生节点转移外，还需要注意rehashidx的变化，该参数记录了rehash的进度，接下来我们详细讲述一下渐进式rehash的过程：

1. 为ht[1]分配数组空间，大小为扩/缩容之后的空间。上图哈希表数组长度由2扩到4，因此ht[1]中节点数组的大小为4。
2. 将rehashidx由-1置为0，标记着渐进式rehash的开始，同时也用来保存下次rehash的数组下标。
3. 每次对key进行访问的时候，都将该节点从ht[0] rehash到ht[1]，同时将下标为rehashidx的链表中的所有节点rehash到ht[1]，然后将rehashidx加1。因此rehashidx既可以看出当前的rehash进度，又指代着下次rehash的下标。
4. 最终ht[0]中的所有元素都rehash到了ht[1]，此时将ht[0]指向ht[1]中的哈希表，再清空ht[1]，然后将rehashidx置为-1，代表着rehash结束。

渐进式rehash对增、删、改、查的影响

在rehash的过程中，字典中同时存在两个哈希表，因此删、改、查操作可能需要对两个哈希表进行操作，当ht[0]中不存在元素时就访问ht[1]，不过无论ht[0]中是否存在元素，最终元素都需要被rehash到ht[1]。往字典中插入元素时，rehash的过程中总会把新元素插入ht[1]，这样做可以避免对新元素进行多余的rehash操作。

5. rehash与字典遍历

在Redis中，很多操作都需要遍历字典，如bgsave与bgrewriteaof操作、keys和scan指令。bgsave与bgrewriteaof是在子进程中执行的操作，在指令执行过程中如果Redis需要进行rehash，rehash操作会以页为单位将内存数据拷贝一份出来修改，因此并不会改变bgsave与bgrewriteaof需遍历的内存。keys指令在执行时与rehash操作共享同一份内存数据，但是由于keys指令用的是安全的迭代器，在指令执行过程中不允许rehash操作，所以执行keys指令并不会重复遍历数据。

安全的迭代器：在遍历哈希表时允许对哈希表中的数据进行修改，但是不允许rehhash操作。bgsave、bgrewriteaof和keys都是用安全的迭代器。
不安全的迭代器：在遍历的过程中哈希表只读，允许执行rehash操作。

scan指令与rehash

scan指令与keys指令的功能相似，都是用于查找字典中的key，支持模式匹配。但是keys指令一次性遍历返回所有符合条件的key，在数量大的情况下可能会造成卡顿，因此不建议使用。而scan指令则支持批次遍历，可以指定游标值（遍历的起始槽位）和单次遍历的槽位数量来执行，执行结果为游标值和符合条件的key，下次遍历时可指定上次返回的游标值继续遍历，遍历结束时游标值返回0。由于scan指令支持分批遍历，键小且少的情况下不会造成内存卡顿，因此要尽量避免大key的产生。

# 添加数据
127.0.0.1:6379> mset a a b b c c d d e e f f
OK

# 第一次遍历
127.0.0.1:6379> scan 0 match * count 2
1) "2"
2) 1) "a"
   2) "c"

# 第二次遍历
127.0.0.1:6379> scan 2 match * count 3
1) "5"
2) 1) "d"
   2) "b"
   3) "e"

# 第三次遍历
127.0.0.1:6379> scan 5 match * count 2
1) "0"
2) 1) "f"

由于使用scan指令遍历字典需分多次执行，即使使用安全的迭代器也无法保证在多次执行的过程中不会执行rehash操作，因此需要一种方法来尽量避免重复遍历，这种方法就是高位加法，高位加法每次执行加法运算时都是在高位相加。

高位加法.png
扩缩容下标关系.png
上图展示了哈希表扩容和缩容之后，元素迁移下标的对应关系。从左往右看，恰恰是采用高位加法的下标变化关系。总结来说就是：原来下标为 xxx的元素，扩容后会被rehash到槽位0xxx或者1xxx中；原来下标为 0xx的元素和下标为1xx的元素，缩容后会被rehash槽位xx中。

扩容时，如果当前遍历的下标为001，则可以保证不再遍历0001之前的槽位。如果使用普通的加法，则后续还会对槽位1000、0100、1100进行重复遍历。但是对于同一个槽位的元素而言，还是有可能造成重复遍历的：在rehash的过程中，能之直接被用户访问的还是原来的哈希表，scan遍历的时候会先遍历001，再遍历0001和1001，重复遍历的元素可在客户端去重。如果一次scan遍历完后，rehash过程也刚好完成，那么接下来的scan还是会再遍历1001槽位的。所以高位加法并不能完全避免元素重复遍历，而是尽可能地减少元素重复遍历。

对于缩容而言，如果在遍历旧哈希表槽位010时会同时遍历新哈希表的10槽位，在接下来遍历槽位110时如果当前还在rehash，也会遍历10槽位，因此可能对槽位10进行重复遍历；如果当前rehash过程已经完成了，ht[0]就会替换成ht[1]被客户端访问，槽位110也就不复存在了，所以如果当前scan遍历到槽位010，下次scan时可能就访问不到110槽位了，因此有可能漏遍历。

6、总结
最近工作太忙了，这篇文章断断续续写了一个星期，也许有一些瑕疵的地方，欢迎大家批评指正，接下来我来总结一下全文的知识点：

1. Redis字典采用三个结构体实现：dict（字典）、dictht（哈希表）、dictEntry（哈希表节点），其中dictht有两个，只有ht[0]能被直接访问，ht[1]在rehash时被用来存储过度态的新哈希表。
2. 在元素过多或者过少时，Redis都会执行rehash，过多或过少用负载因子load_factor来衡量，rehash采用渐进式rehash的方式。
3. 由于字典会rehash，因此在遍历时有可能会重复遍历元素，因此bgsave、bgrewriteaof、keys指令采用安全的迭代器，在遍历过程中禁止rehash，由于scan是分批执行的，即使采用安全的迭代器也无法避免重复遍历，因此采用高位加法计算遍历槽位来避免尽量重复遍历。

读者如果有什么疑问或者建议可以在下方留言，我将会在看到的第一时间给予解答或者完善文章，提升自己也惠及他人