Redis dict详解

Redis dict 详解

dict，又称字典（dictionary）或映射（map），是集合的一种形式，其中每个元素都是 KV（Key-Value）键值对。字典在各编程语言中都有体现，面向对象的编程语言如 C++、Java 中通常称其为 Map。

Redis 的 KV 存储结构

Redis 内存数据库的最底层是一个 redisDb 结构。

redisDb 整体使用 dict 字典 来存储键值对（KV）。字典中的每一项使用 dictEntry 表示，代表一个 KV 键值对，类似于 Java HashMap 中的 Entry。

为什么选择 dict/map？

dict 是一种用于维护 key 和 value 映射关系的数据结构，与很多编程语言中的 Map 类似。

为什么 dict/map 这么受欢迎？

因为 dict/map 实现了 key 和 value 的映射，通过 key 查询 value 是效率非常高的操作。在没有冲突/碰撞的情况下，时间复杂度可以达到 O(1)。

dict 本质上是为了解决算法中的查找问题（Searching）。一般查找问题的解法分为两个大类：

• 基于平衡树：如二叉搜索树、红黑树，使用的是“二分思想”。如果需要实现排序，可使用平衡树（例如用大顶堆实现 TreeMap）。
• 基于哈希表：如 Java 中的 Map、Python 中的字典 dict，使用的是“映射思想”。

我们平常使用的各种 Map 或 dict，大都是基于哈希表实现的。在不要求数据有序存储，且能保持较低的哈希值冲突概率的前提下，基于哈希表的查找性能非常高效，接近 O(1)，而且容易实现。

Redis 中 dict 的应用

字典 dict 在 Redis 中的应用广泛，使用频率可以说和 SDS 以及双端链表不相上下，基本上各个功能模块都有用到字典的地方。

其中，dict 的主要用途有以下两个：

• 实现数据库键空间（key space）；
• 用作 hash 键的底层实现之一。

以下两个小节分别介绍这两种用途。

Redis 数据库键空间（key space）

Redis 是一个键值对数据库服务器，服务器中每个数据库都由 redisDB 结构表示（默认 16 个库）。其中，redisDB 结构的 dict 字典保存了数据库中所有的键值对，这个字典被称为键空间（key space）。

可以认为，Redis 默认 16 个库，这 16 个库在各自的键空间（key space）中，其实就通过键空间实现了隔离。而键空间（key space）底层是 dict 实现的。

键空间（key space）除了实现了 16 个库的隔离，还能基于键空间通知 (Keyspace Notifications) 实现某些事件的订阅通知，如某个 key 过期的时间、某个 key 的 value 变更事件。

键空间通知 (Keyspace Notifications) 是因为键空间（key space）实现了 16 个库的隔离，而我们执行 Redis 命令最终都是落在其中一个库上。当有事件发生在某个库上时，该库对应的键空间（key space）就能基于 pub/sub 发布订阅，实现事件“广播”。

键空间（key space）的详细分析，可参见：Redis 键空间通知 (Keyspace Notifications)

dict 用作 hash 键的底层实现

Redis 的 hash 键使用以下两种数据结构作为底层实现：

• 压缩列表 ziplist；
• 字典 dict。

因为压缩列表比字典更节省内存，所以程序在创建新 Hash 键时，默认使用压缩列表作为底层实现。当有需要时，才会将底层实现从压缩列表转换到字典。

ziplist 是为 Redis 节约内存而开发的、非常节省内存的双向链表，深入学习可移步 Redis 的 list

压缩列表转成字典 (ziplist->dict) 的条件

同时满足以下两个条件，hash 键才会使用 ziplist：

1. key 和 value 长度都小于 64 字节；
2. 键值对数小于 512。

该配置在 redis.conf 中：

hash-max-ziplist-entries 512
hash-max-ziplist-value 64

字典 dict/映射的实现原理

dict，又称字典 (dictionary) 或映射 (map)，是集合的一种；这种集合中每个元素都是 KV 键值对。它是根据关键字值（key）而直接进行访问 KV 键值对的数据结构。也就是说，它通过把关键字值映射到一个位置来访问记录，以加快查找的速度。这个映射函数称为哈希函数（也称为散列函数）。因此通常我们称字典 dict，也叫哈希表。

映射过程通常使用 hash 算法实现，因此也称映射过程为哈希化，存放记录的数组叫做散列表、或 hash 表。

哈希化之后难免会产生一个问题，那就是对不同的关键字，可能得到同一个散列地址，即不同的 key 散列到同一个数组下标，这种现象称为冲突。那么我们该如何去处理冲突呢？

最常用的就是链地址法，也常被称为拉链法。就是在冲突的下标处，维护一个链表，所有映射到该下标的记录，都添加到该链表上。

Redis 字典 dict 如何实现的？

Redis 字典 dict 也是采用哈希表，本质就是数组 + 链表。这也是众多编程语言实现 Map 的首选方式，如 Java 中的 HashMap。

Redis 字典 dict 的底层实现，其实和 Java 中的 ConcurrentHashMap 思想非常相似。就是用数组 + 链表实现了分布式哈希表。当不同的关键字散列到数组相同的位置，就拉链，用链表维护冲突的记录。当冲突记录越来越多、链表越来越长，遍历列表的效率就会降低，此时需要考虑将链表的长度变短。

将链表的长度变短，一个最直接有效的方式就是扩容数组。将数组 + 链表结构中的数组扩容，数组变长、对应数组下标就增多了；将原数组中所有非空的索引下标、搬运到扩容后的新数组，经过重新散列，自然就把冲突的链表变短了。

如果你对 Java 的 HashMap 或 ConcurrentHashMap 底层实现原理比较了解，那么对 Redis 字典 dict 的底层实现，也能很快上手。

dict.h 给出了这个字典 dict 的定义：

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);
    void *(*keyDup)(void *privdata, const void *key);
    void *(*valDup)(void *privdata, const void *obj);
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    void (*keyDestructor)(void *privdata, void *key);
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

结合上面的代码，可以很清楚地看出 dict 的结构。一个 dict 由如下若干项组成：

• dictType *type;：一个指向 dictType 结构的指针。它通过自定义的方式使得 dict 的 key 和 value 能够存储任何类型的数据。
• void *privdata;：一个私有数据指针。由调用者在创建 dict 的时候传进来。
• dictht ht[2];：两个哈希表。只有在 rehash 的过程中，ht[0] 和 ht[1] 才都有效。而在平常情况下，只有 ht[0] 有效，ht[1] 里面没有任何数据。
• int rehashidx;：当前 rehash 索引。如果 rehashidx = -1，表示当前没有在 rehash 过程中；否则，表示当前正在进行 rehash，且它的值记录了当前 rehash 进行到哪一步了。
• int iterators;：当前正在进行遍历的 iterator 的个数。

dictType 结构包含若干函数指针，用于 dict 的调用者对涉及 key 和 value 的各种操作进行自定义。这些操作包含：

• hashFunction：对 key 进行哈希值计算的哈希算法。
• keyDup 和 valDup：分别定义 key 和 value 的拷贝函数，用于在需要的时候对 key 和 value 进行深拷贝，而不仅仅是传递对象指针。
• keyCompare：定义两个 key 的比较操作，在根据 key 进行查找时会用到。
• keyDestructor 和 valDestructor：分别定义对 key 和 value 的析构函数。

私有数据指针（privdata）就是在 dictType 的某些操作被调用时会传回给调用者。

dictht (dict hash table) 哈希表

dictht 是字典 dict 哈希表的缩写，即 dict hash table。
dict.h/dictht 类型定义：

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;


/*
 * 哈希表节点
 */
typedef struct dictEntry {
    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 链往后继节点
    struct dictEntry *next;
} dictEntry;

dictht 定义一个哈希表的结构，包括以下部分：

• 一个 dictEntry 指针数组（table）。key 的哈希值最终映射到这个数组的某个位置上（对应一个 bucket）。如果多个 key 映射到同一个位置，就发生了冲突，那么就拉出一个 dictEntry 链表。
• size：标识 dictEntry 指针数组的长度。它总是 2 的指数次幂。
• sizemask：用于将哈希值映射到 table 的位置索引。它的值等于 (size-1)，比如 7, 15, 31, 63 等等，也就是用二进制表示的各个 bit 全 1 的数字。每个 key 先经过 hashFunction 计算得到一个哈希值，然后计算 (哈希值 & sizemask) 得到在 table 上的位置。相当于计算取余 (哈希值 % size)。
• used：记录 dict 中现有的数据个数。它与 size 的比值就是装载因子。这个比值越大，哈希值冲突概率越高。

Redis dictht 的负载因子

我们知道当 HashMap 中由于 Hash 冲突（负载因子）超过某个阈值时，出于链表性能的考虑、会进行扩容，Redis dict 也是一样。

一个 dictht 哈希表里，核心就是一个 dictEntry 数组，同时用 size 记录了数组大小，用 used 记录了所有记录数。

dictht 的负载因子，就是 used 与 size 的比值，也称装载因子（load factor）。这个比值越大，哈希值冲突概率越高。当比值 [默认] 超过 5，会强制进行 rehash。

dictEntry 结构中包含 k, v 和指向链表下一项的 next 指针。k 是 void 指针，这意味着它可以指向任何类型。v 是个 union，当它的值是 uint64_t、int64_t 或 double 类型时，就不再需要额外的存储，这有利于减少内存碎片。当然，v 也可以是 void 指针，以便能存储任何类型的数据。

next 指向另一个 dictEntry 结构，多个 dictEntry 可以通过 next 指针串连成链表。从这里可以看出，dictht 使用链地址法来处理键碰撞：当多个不同的键拥有相同的哈希值时，哈希表用一个链表将这些键连接起来。

下图展示了一个由 dictht 和数个 dictEntry 组成的哈希表例子：

如果再加上之前列出的 dict 类型，那么整个字典结构可以表示如下：

在上图给出的示例中，只使用了 0 号哈希表 ht[0]，且 rehashidx=-1 表明字典未进行 rehash。什么是 rehash，下文会详细展开。

Redis dict 使用的哈希算法

前面提到，一个 kv 键值对，添加到哈希表时，需要用一个映射函数将 key 散列到一个具体的数组下标。

Redis 目前使用两种不同的哈希算法：

1. MurmurHash2
   是种 32 bit 算法：这种算法的分布率和速度都非常好；Murmur 哈希算法最大的特点是碰撞率低，计算速度快。Google 的 Guava 库包含最新的 Murmur3。
   具体信息请参考 MurmurHash 的主页：http://code.google.com/p/smhasher/ 。
2. 基于 djb 算法实现的一个大小写无关散列算法
   具体信息请参考 http://www.cse.yorku.ca/~oz/hash.html 。

使用哪种算法取决于具体应用所处理的数据：

• 命令表以及 Lua 脚本缓存都用到了算法 2。
• 算法 1 的应用则更加广泛：数据库、集群、哈希键、阻塞操作等功能都用到了这个算法。

Redis dict 各种操作

以下是用于处理 dict 的各种 API，它们的作用及相应的算法复杂度：

下面，会对一些关键步骤进行详细讲解。

dict 的创建（dictCreate）

创建 dict：
dict *d = dictCreate(&hash_type, NULL);

dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

dictCreate 为 dict 的数据结构分配空间并为各个变量赋初值。其中两个哈希表 ht[0] 和 ht[1] 起始都没有分配空间，table 指针都赋为 NULL。这意味着要等第一个数据插入时才会真正分配空间。

• ht[0]->table 的空间分配将在第一次往字典添加键值对时进行；
• ht[1]->table 的空间分配将在 rehash 开始时进行。

添加新键值对到字典 (dictAdd)

根据字典所处的状态，将给定的键值对添加到字典可能会引起一系列复杂的操作：

• 如果字典为未初始化（即字典的 0 号哈希表的 table 属性为空），则程序需要对 0 号哈希表进行初始化；
• 如果在插入时发生了键碰撞，则程序需要处理碰撞；
• 如果插入新元素，使得字典满足了 rehash 条件，则需要启动相应的 rehash 程序。

当程序处理完以上三种情况之后，新的键值对才会被真正地添加到字典上。

dictAdd 函数是调用 dictAddRaw 实现的：

/* 将 Key 插入哈希表 */
dictEntry *dictAddRaw(dict *d, void *key) 
{ 
    int index; 
    dictEntry *entry; 
    dictht *ht; 
 
    if (dictIsRehashing(d)) _dictRehashStep(d);  // 如果哈希表在 rehashing，则执行单步 rehash
 
    /* 调用_dictKeyIndex() 检查键是否存在，如果存在则返回 NULL */ 
    if ((index = _dictKeyIndex(d, key)) == -1) 
        return NULL; 
 

    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; 
    entry = zmalloc(sizeof(*entry));   // 为新增的节点分配内存
    entry->next = ht->table[index];  //  将节点插入链表表头
    ht->table[index] = entry;   // 更新节点和桶信息
    ht->used++;    //  更新 ht
 
    /* 设置新节点的键 */ 
    dictSetKey(d, entry, key); 
    return entry; 
}

整个添加流程可以用下图表示：

在接下来的三节中，我们将分别看到，添加操作如何在以下三种情况中执行：

1. 字典为空；
2. 添加新键值对时发生碰撞处理；
3. 添加新键值对时触发了 rehash 操作。

添加新元素时 table 为空

当第一次往空字典里添加键值对时，程序会根据 dict.h/DICT_HT_INITIAL_SIZE 里指定的大小为 d->ht[0]->table 分配空间（在目前的版本中，DICT_HT_INITIAL_SIZE 的值为 4）。

以下是字典空白时的样子：

以下是往空白字典添加了第一个键值对之后的样子：

添加新键值对时发生碰撞

在哈希表实现中，当两个不同的键拥有相同的哈希值时，称这两个键发生碰撞（collision），而哈希表实现必须想办法对碰撞进行处理。

字典哈希表所使用的碰撞解决方法被称之为链地址法：这种方法使用链表将多个哈希值相同的节点串连在一起，从而解决冲突问题。

假设现在有一个带有三个节点的哈希表，如下图：

对于一个新的键值对 key4 和 value4，如果 key4 的哈希值和 key1 的哈希值相同，那么它们将在哈希表的 0 号索引上发生碰撞。

通过将 key4-value4 和 key1-value1 两个键值对用链表连接起来，就可以解决碰撞的问题：

添加新键值对时触发了 rehash

对于使用链地址法来解决碰撞问题的哈希表 dictht 来说，哈希表的性能取决于大小（size 属性）与保存节点数量（used 属性）之间的比率：

• 哈希表的大小与节点数量，比率在 1:1 时，哈希表的性能最好；
• 如果节点数量比哈希表的大小要大很多的话，那么哈希表就会退化成多个链表，哈希表本身的性能优势便不复存在。

举个例子，下面这个哈希表，平均每次失败查找只需要访问 1 个节点（非空节点访问 2 次，空节点访问 1 次）：

而下面这个哈希表，平均每次失败查找需要访问 5 个节点：

为了在字典的键值对不断增多的情况下保持良好的性能，字典需要对所使用的哈希表（ht[0]）进行 rehash 操作：在不修改任何键值对的情况下，对哈希表进行扩容，尽量将比率维持在 1:1 左右。

dictAdd 在每次向字典添加新键值对之前，都会对哈希表 ht[0] 进行检查。对于 ht[0] 的 size 和 used 属性，如果它们之间的比率 ratio = used / size 满足以下任何一个条件的话，rehash 过程就会被触发：

• 自然 rehash：ratio >= 1，且变量 dict_can_resize 为 true。
• 强制 rehash：ratio 大于变量 dict_force_resize_ratio（目前版本中，dict_force_resize_ratio 的值为 5）。

什么时候 dict_can_resize 会为 false？

在前面介绍字典的应用时也说到过，数据库就是字典，数据库里的哈希类型键也是字典。当 Redis 使用子进程对数据库执行后台持久化任务时（比如执行 BGSAVE 或 BGREWRITEAOF 时），为了最大化地利用系统的 copy on write 机制，程序会暂时将 dict_can_resize 设为 false，避免执行自然 rehash，从而减少程序对内存的触碰（touch）。

当持久化任务完成之后，dict_can_resize 会重新被设为 true。

另一方面，当字典满足了强制 rehash 的条件时，即使 dict_can_resize 不为 true（有 BGSAVE 或 BGREWRITEAOF 正在执行），这个字典一样会被 rehash。

Rehash 执行过程

字典的 rehash 操作实际上就是执行以下任务：

1. 创建一个比 ht[0]->table 更大的 ht[1]->table；
2. 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table；
3. 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0]。

经过以上步骤之后，程序就在不改变原有键值对数据的基础上，增大了哈希表的大小。

dict 的 rehash 本质就是扩容，就是将数组 + 链表结构中的数组扩容。这个过程，需要开辟一个更大空间的数组，将老数组中每个非空索引的 bucket，搬运到新数组；搬运完成后再释放老数组的空间。

作为例子，以下四个小节展示了一次对哈希表进行 rehash 的完整过程。

1. 开始 rehash
这个阶段有两个事情要做：

• 设置字典的 rehashidx 为 0，标识着 rehash 的开始；
• 为 ht[1]->table 分配空间，大小至少为 ht[0]->used 的两倍。

这时的字典是这个样子：

2. Rehash 进行中
在这个阶段，ht[0]->table 的节点会被逐渐迁移到 ht[1]->table。因为 rehash 是分多次进行的（细节在下一节解释），字典的 rehashidx 变量会记录 rehash 进行到 ht[0] 的哪个索引位置上。
注意除了节点的移动外，字典的 rehashidx、ht[0]->used 和 ht[1]->used 三个属性也产生了变化。

3. 节点迁移完毕
到了这个阶段，所有的节点都已经从 ht[0] 迁移到 ht[1] 了：

4. Rehash 完毕
在 rehash 的最后阶段，程序会执行以下工作：

• 释放 ht[0] 的空间；
• 用 ht[1] 来代替 ht[0]，使原来的 ht[1] 成为新的 ht[0]；
• 创建一个新的空哈希表，并将它设置为 ht[1]；
• 将字典的 rehashidx 属性设置为 -1，标识 rehash 已停止。

以下是字典 rehash 完毕之后的样子：

增量/渐进式 rehash（Incremental Rehashing）

在上一节，我们了解了字典的 rehash 过程。需要特别指出的是，rehash 并不是在触发之后，马上就执行直到完成；而是分多次、渐进式地完成的。

rehash 会产生的问题

1. rehash 的过程，会使用两个哈希表，创建了一个更大空间的 ht[1]，此时会造成内存陡增；
2. rehash 的过程，可能涉及大量 KV 键值对 dictEntry 的搬运，耗时较长。

如果这个 rehash 过程必须将所有键值对迁移完毕之后才将结果返回给用户，这样的处理方式将不满足 Redis 高效响应的特性。rehash 会产生的问题，主要层面就是内存占用陡增、和处理耗时长的问题，基于这两点，还会带来其他影响。

为了解决这些问题，Redis 使用了 incremental rehashing，是一种增量/渐进式的 rehash 方式：通过将 rehash 分散到多个步骤中进行，从而避免了集中式的计算/节点迁移。

dictAdd 添加键值对到 dict，检查到需要进行 rehash 时，会将 dict.rehashidx 设置为 0，标识着 rehash 的开始。
后续请求，在执行 add、delete、find 操作时，都会判断 dict 是否正在 rehash。如果是，就执行 _dictRehashStep() 函数，进行增量 rehash。

每次执行 _dictRehashStep，会将 ht[0]->table 哈希表第一个不为空的索引上的所有节点就会全部迁移到 ht[1]->table。

也就是在某次 dictAdd 添加键值对时，触发了 rehash；后续 add、delete、find 命令在执行前都会检查，如果 dict 正在 rehash，就先不急去执行自己的命令，先去帮忙搬运一个 bucket。搬运完一个 bucket，再执行 add、delete、find 命令原有处理逻辑。

ps: 实际上 incremental rehashing 增量/渐进式 rehash，只解决了第二个：耗时长的问题，将集中式的节点迁移分摊到多步进行，ht[1] 占用的双倍多内存，还一直占用。

下面我们通过 dict 的查找（dictFind）来看渐进式 rehash 过程。

dict 的查找（dictFind）

dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);// 如果哈希表在 rehashing，则执行单步 rehash
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

上述 dictFind 的源码，根据 dict 当前是否正在 rehash，依次做了这么几件事：

• 如果当前正在进行 rehash，那么将 rehash 过程向前推进一步（即调用 _dictRehashStep）。实际上，除了查找，插入和删除也都会触发这一动作。这就将 rehash 过程分散到各个查找、插入和删除操作中去了，而不是集中在某一个操作中一次性做完。
• 计算 key 的哈希值（调用 dictHashKey，里面的实现会调用前面提到的 hashFunction）。
• 先在第一个哈希表 ht[0] 上进行查找。在 table 数组上定位到哈希值对应的位置（如前所述，通过哈希值与 sizemask 进行按位与），然后在对应的 dictEntry 链表上进行查找。查找的时候需要对 key 进行比较，这时候调用 dictCompareKeys，它里面的实现会调用到前面提到的 keyCompare。如果找到就返回该项。否则，进行下一步。
• 判断当前是否在 rehash，如果没有，那么在 ht[0] 上的查找结果就是最终结果（没找到，返回 NULL）。否则，在 ht[1] 上进行查找（过程与上一步相同）。

下面我们有必要看一下增量式 rehash 的 _dictRehashStep 的实现。

static void _dictRehashStep(dict *d) {
    if (d->iterators == 0) dictRehash(d,1);
}

/* 
 * Note that a rehashing step consists in moving a bucket (that may have more
 * than one key as we use chaining) from the old to the new hash table, however
 * since part of the hash table may be composed of empty spaces, it is not
 * guaranteed that this function will rehash even a single bucket, since it
 * will visit at max N*10 empty buckets in total, otherwise the amount of
 * work it does would be unbound and the function may block for a long time. 
 */
int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    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;
    }

    /* More to rehash... */
    return 1;
}

根据 dictRehash 函数的注释，rehash 的单位是 bucket，也就是从老哈希表 dictht 中找到第一个非空的下标，要把该下标整个链表搬运到新数组。

如果遍历老数组，访问的前 N*10 个都是空 bucket，则不再继续往下寻找。

dictAdd、dictDelete、dictFind 在 rehash 过程中的特殊性

在哈希表进行 rehash 时，字典还会采取一些特别的措施，确保 rehash 顺利、正确地进行：

• 因为在 rehash 时，字典会同时使用两个哈希表，所以在这期间的所有查找 dictFind、删除 dictDelete 等操作，除了在 ht[0] 上进行，还需要在 ht[1] 上进行。
• 在执行添加操作 dictAdd 时，新的节点会直接添加到 ht[1] 而不是 ht[0]，这样保证 ht[0] 的节点数量在整个 rehash 过程中都只减不增。

dict 的缩容

上面关于 rehash 的章节描述了通过 rehash 对字典进行扩展（expand）的情况。如果哈希表的可用节点数比已用节点数大很多的话，那么也可以通过对哈希表进行 rehash 来收缩（shrink）字典。

收缩 rehash 和上面展示的扩展 rehash 的操作几乎一样，执行以下步骤：

• 创建一个比 ht[0]->table 小的 ht[1]->table；
• 将 ht[0]->table 中的所有键值对迁移到 ht[1]->table；
• 将原有 ht[0] 的数据清空，并将 ht[1] 替换为新的 ht[0]。

小结

Redis 的 dict 最显著的一个特点，就在于它的 rehash。它采用了一种称为增量式（incremental rehashing）的 rehash 方法，在需要扩容时避免一次性对所有 key 进行 rehash，而是将 rehash 操作分散到对于 dict 的各个增删改查的操作中去。

这种方法能做到每次只对一小部分 key 进行 rehash，而每次 rehash 之间不影响 dict 的操作。dict 之所以这样设计，是为了避免 rehash 期间单个请求的响应时间剧烈增加，这与前面提到的“快速响应时间”的设计原则是相符的。

• Redis 的 dict 也是使用数组 + 链表实现；
• 当冲突增加、链表增长，也是采用 rehash(数组扩容) 来将链表变短；
• dict 数组扩容，也是按 2 的指数次幂，使用位运算，替代求余操作，计算更快；
• 渐进式 rehash，其实是辅助式的；不是让触发 rehash 的一个人搬运完所有 dictEntry，而是让后来者一起参与搬运。

说明：本文基于 Redis 早期版本（如 Redis 3.x/4.x/5.x）的 dict 实现原理编写。在 Redis 6.0 及以后版本中，Hash 对象的底层编码已由 ziplist 升级为 listpack，但 dict 字典的核心结构与渐进式 rehash 机制保持不变。