哈希表 Dict

一、数据结构

1.1 Hash 表

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;  // 指针数组，用于存储键值对
    unsigned long size;  // table 数组的大小
    unsigned long sizemask;  // 掩码：size - 1
    unsigned long used;  // table 中已存元素个数（含 next 单链表）
} dictht;

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

sizemask 字段用来计算键的索引值，sizemask 的值恒等于 size – 1。我们知道，索引值是键 Hash 值与数组总容量取余之后的值，而 Redis 为提高性能对这个计算进行了优化，具体计算步骤如下：

1. 人为设定 Hash 表的数组容量初始值为 4，每次扩容时，新扩容的容量大小为当前容量大小的一半，即哈希表的容量始终为 $2^n$；
2. 索引值 = 哈希值 & 掩码值，源码中为 h & d->ht[table].sizemask，使用位运算要比取余运算快很多，

说明

设 $Y=2^n$，则 $X \bmod Y = X \& (2^n - 1) = X \& (\sim Y)$。

原理：对 $2^n$ 求余，就意味着数字将向右移 n 位（右移一次相当于一次被 2 整除的运算）；这被右移的 n 位就是余数，只要我们用 & 运算将这 n 位保存下来即可！

1.2 Hash 表节点

Hash 表中的元素是用 dictEntry 结构体来封装的，主要作用是存储键值对，具体结构体如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

Hash 表节点整体占用 24 字节，key 字段存储的是键值对中的键；v 字段是一个联合体，存储的是键值对中的值，在不同场景下使用不同字段；当出现 Hash 冲突时，next 字段用来指向冲突的元素，通过头插法，形成单链表。

1.3 字典

Redis 字典对 Hash 表进行了一层封装，当需要一些特殊操作时要用到里面的辅助字段，具体结构如下：

typedef struct dict {
    dictType *type;  // 该字典对应的特定操作函数
    void *privdata;  // 该字典依赖的数据
    dictht ht[2];    // Hash 表，键值对存储在此
    long rehashidx;  // rehash 标识，默认值 -1，代表未进行 rehash 操作
    unsigned long iterators;  // 当前运行的安全迭代器数量
} dict;

其中 type 字段，指向 dictType 结构体，里面包含了对该字典操作的函数指针，具体如下：

typedef struct dictType {
    // 计算哈希值的函数
    uint64_t (*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;

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

• privdata：私有数据，配合 type 指向的函数一起使用；
• ht：一个大小为 2 的数组，存储的元素为 dictht，虽然有两个元素，但一般情况下只会使用 ht[0]，只有当扩容、缩容需要 rehash 时，才会用到 ht[1]；
• rehashidx：用来标记该字典是否在进行 rehash，没进行 rehash 时，值为 -1，否则，该值用来表示 Hash 表 ht[0] 执行 rehash 到了哪个元素，并记录该元素的数组下标值；
• iterators：用来记录当前运行的安全迭代器数，当有安全迭代器绑定到该字典时，会暂停 rehash 操作。

下图展示了一个普通状态下（没有进行 rehash）的字典：

二、基本操作

2.1 字典初始化

在 redis-server 启动时，会初始化一个空的字典用于存储整个数据库的键值对，对应源码为：

/* Create a new hash table */
dict *dictCreate(dictType *type, void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

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

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type, void *privDataPtr)
{
    // 初始化两个哈希表的各项属性值
    // 但暂时还不分配内存给哈希表数组
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);

    // 设置类型特定函数
    d->type = type;

    // 设置私有数据
    d->privdata = privDataPtr;

    // 设置哈希表 rehash 状态
    d->rehashidx = -1;

    // 设置字典的安全迭代器数量
    d->iterators = 0;

    return DICT_OK;
}

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

2.2 添加元素

添加元素的步骤如下：

1. 调用 dictAddRaw 函数，若键已存在则返回 NULL，否则添加键至 Hash 表，并返回新添加的 Hash 表节点；
2. 给返回的新节点设置值，即更新其 val 字段。

点击查看代码

/* Add an element to the target hash table */
int dictAdd(dict *d, void *key, void *val)
{
    // 尝试添加键到字典，并返回包含了这个键的新 Hash 节点
    dictEntry *entry = dictAddRaw(d,key,NULL);

    // 若键已存在，添加失败
    if (!entry) return DICT_ERR;

    // 键不存在，设置节点的值
    dictSetVal(d, entry, val);

    // 添加成功
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;

    // 如果条件允许的话，进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 计算键在哈希表中的索引值，若值为 -1 ，那么表示键已经存在，将老节点存入 existing
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    // 如果字典正在 rehash ，那么将新键添加到 1 号哈希表，否则添加到 0 号哈希表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];

    // 为新节点分配空间
    entry = zmalloc(sizeof(*entry));

    // 将新节点插入到链表表头
    entry->next = ht->table[index];
    ht->table[index] = entry;

    // 更新哈希表已使用节点数量
    ht->used++;

    /* Set the hash entry fields. */
    // 设置新节点的键
    dictSetKey(d, entry, key);

    return entry;
}

字典扩容

随着 Redis 数据库添加操作逐步进行，存储键值对的字典会出现容量不足，达到上限，此时就需要对字典的 Hash 表进行扩容，扩容的主要流程为：

1. 申请一块新内存，初始申请时默认容量大小为 4，非初次申请时，申请内存的大小则为当前 Hash 表容量的 2 倍；
2. 把新申请的内存地址赋值给 ht[1]；
3. 将字典的 rehashidx 标识由 -1 改为 0，表示之后要进行 rehash 操作。

点击查看代码

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{
    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */

    // 计算扩容后容量大小
    unsigned long realsize = _dictNextPower(size);

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].size) return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    // 扩容后新内存放入 ht[1] 中
    d->ht[1] = n;
    // 标识需进行 rehash
    d->rehashidx = 0;
    
    return DICT_OK;
}

渐进式 rehash

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

1. 给 Hash 表 ht[1] 申请足够的空间，并将字典的 rehashidx 标识置为 0。
   • 扩容时，空间大小为当前容量的 2 倍，即：d->ht[0].used * 2；
   • 缩容时（使用量不到总空间的 10%），空间大小为能恰好包含 d->ht[0].used 个节点的 $2^n$ 整数。
2. 进行 rehash 操作调用的是 dictRehash 函数，重新计算 ht[0] 中每个键的 Hash 值与索引值（重新计算就叫 rehash），依次添加到新的 Hash 表 ht[1]，并把老 Hash 表中该键值对删除。把字典中字段 rehashidx 字段修改为 Hash 表 ht[0] 中正在进行 rehash 操作节点的索引值。
3. rehash 操作后，清空 ht[0]，然后对调一下 ht[1] 与 ht[0] 的值，并把字典中 rehashidx 字段标识为-1。

由于 Redis 是单进程模式，当数据量过大时，整个 rehash 过程将非常缓慢，如果不优化 rehash 过程，可能造成很严重的服务不可用现象。Redis 优化的思想很巧妙，利用 分而治之 的思想进行 rehash 操作，大致的步骤如下。

• 执行插入、删除、查找、修改等操作前，都先判断当前字典 rehash 操作是否在进行中，进行中则调用 dictRehashStep 函数进行 rehash 操作（每次只对 1 个节点进行 rehash 操作，共执行 1 次）；
• 当服务空闲时，如果当前字典也需要进行 rehash 操作， 则会调用 incrementallyRehash 函数进行批量 rehash 操作（每次对 100 个节点进行 rehash 操作，共执行 1 毫秒）。

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

2.3 查找元素

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

1. 根据键调用 Hash 函数取得其 Hash 值；
2. 根据 Hash 值取到索引值；
3. 遍历字典的两个 Hash 表，读取索引对应的元素；
4. 遍历该元素单链表，如找到了与自身键匹配的键，则返回该元素；
5. 找不到则返回 NULL。

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

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    
    // 如果需要 rehash，则进行一步 rehash 操作
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 获取键的 Hash 值
    h = dictHashKey(d, key);
    
    // 遍历查找 Hash 表：ht[0] 与 ht[1]
    for (table = 0; table <= 1; table++) {
        // 根据 Hash 值获取对应索引值
        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;
}

2.4 修改元素

修改元素的过程主要分为以下几个步骤：

1. 调用 dictFind 查找键是否存在；
2. 不存在则中断执行；
3. 修改节点键值对中的值为新值；
4. 释放旧值内存。

void dbOverwrite(redisDb *db, robj *key, robj *val) {
    // 查找键存在与否，返回存在的节点
    dictEntry *de = dictFind(db->dict,key->ptr);

    // 不存在则中断执行
    serverAssertWithInfo(NULL,key,de != NULL);
    dictEntry auxentry = *de;

    // 获取老节点的 val 字段值
    robj *old = dictGetVal(de);
    if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {
        val->lru = old->lru;
    }
    // 给节点设置新的值
    dictSetVal(db->dict, de, val);

    if (server.lazyfree_lazy_server_del) {
        freeObjAsync(old);
        dictSetVal(db->dict, &auxentry, NULL);
    }

    // 释放节点中旧 val 内存
    dictFreeVal(db->dict, &auxentry);
}

2.5 删除元素

删除元素的主要执行过程为：

1. 查找该键是否存在于该字典中；
2. 存在则把该节点从单链表中剔除；
3. 释放该节点对应的键占用的内存、值占用的内存，以及本身占用的内存；
4. 给对应的 Hash 表的 used 字段减 1 操作。

当字典中数据经过一系列操作后，使用量不到总空间小于 10% 时， 就会进行缩容操作，将 Redis 数据库占用内存保持在合理的范围内，不浪费内存。

字典缩容的核心函数有两个：

void tryResizeHashTables(int dbid) {
    // 判断是否需要缩容
    if (htNeedsResize(server.db[dbid].dict))
        // 执行缩容操作
        dictResize(server.db[dbid].dict);
    
    if (htNeedsResize(server.db[dbid].expires))
        dictResize(server.db[dbid].expires);
}

int dictResize(dict *d) {
    int minimal;

    if (!dict_can_resize || dictIsRehashing(d)) return DICT_ERR;
    minimal = d->ht[0].used;

    // 容量最小值为 4
    if (minimal < DICT_HT_INITIAL_SIZE)
        minimal = DICT_HT_INITIAL_SIZE;

    // 调用扩容函数，实质进行的是缩容
    return dictExpand(d, minimal);
}

三、字典的遍历

本节将讲解字典的遍历操作，遍历数据库的原则为：

1. 不重复出现数据；
2. 不遗漏任何数据。

遍历 Redis 整个数据库主要有两种方式：全遍历 （keys 命令）、间断遍历（hscan 命令），这两种方式将在下面进行详细讲解。

• 全遍历：一次命令执行就遍历完整个数据库。
• 间断遍历：每次命令执行只取部分数据，分多次遍历。

3.1 迭代器遍历

字典迭代器主要用于迭代字典这个数据结构中的数据。

既然是迭代字典中的数据，必然会出现一个问题，迭代过程中，如果发生了数据增删，则可能导致字典触发 rehash 操作，或迭代开始时字典正在进行 rehash 操作，从而导致一条数据可能多次遍历到。那Redis如何解决这个问题呢？

Redis 源码中迭代器实现的基本数据结构如下：

typedef struct dictIterator {
    dict *d;  // 迭代的字典
    long index;  // 当前迭代到 Hash 表中哪个索引值

    // table 表示当前正在迭代的 Hash 表编号：0 或 1
    // safe 标识这个迭代器是否安全
    int table, safe;

    dictEntry *entry, *nextEntry;  // 当前节点，下一个节点

    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;  // 字典的指纹
} dictIterator;

为了让迭代过程变得简单，Redis 也提供了迭代相关的 API 函数，主要为：

// 初始化迭代器
dictIterator *dictGetIterator(dict *d);

// 初始化安全的迭代器
dictIterator *dictGetSafeIterator(dict *d);

// 通过迭代器获取下一个节点
dictEntry *dictNext(dictIterator *iter);

// 释放迭代器
void dictReleaseIterator(dictIterator *iter);

简单介绍完迭代器的基本结构、字段含义及 API，我们来看下 Redis 如何解决增删数据的同时不出现读取数据重复的问题。

Redis 为单进程单线程模式，不存在两个命令同时执行的情况，因此只有当执行的命令在遍历的同时删除了数据，才会触发前面的问题。我们把迭代器遍历数据分为两类：

• 普通迭代器，只遍历数据；
• 安全迭代器，遍历的同时删除数据。

1. 普通迭代器

普通迭代器迭代字典中数据时，会对迭代器中 fingerprint 字段的值做严格的校验，来保证迭代过程中字典结构不发生任何变化，确保读取出的数据不出现重复。

普通迭代器迭代数据的过程比较简单，主要分为如下几个步骤：

1. 调用 dictGetIterator 函数初始化一个普通迭代器，此时会把 iter->safe 的值置为 0，表示初始化的迭代器为普通迭代器；
2. 循环调用 dictNext 函数依次遍历字典中 Hash 表的节点，首次遍历时会通过 dictFingerprint 函数拿到当前字典的指纹值；
3. 当调用 dictNext 函数遍历完字典 Hash 表中节点数据后，释放迭代器时会继续调用 dictFingerprint 函数计算字典的指纹值，并与首次拿到的指纹值比较，不相等则返回异常结束。

注意

• entry 与 nextEntry 两个指针分别指向 Hash 冲突后的两个父子节点。如果在安全模式下，删除了 entry 节点，nextEntry 字段可以保证后续迭代数据不丢失。
• 对字典进行修改、添加、删除、查找操作都会调用 dictRehashStep 函数，进行渐进式 rehash 操作，从而导致 fingerprint 值发生改变。

2. 安全迭代器

安全迭代器和普通迭代器迭代数据原理类似，也是通过循环调用 dictNext 函数依次遍历字典中 Hash 表的节点。

安全迭代器确保读取数据的准确性，不是通过限制字典的部分操作来实现的，而是通过限制 rehash 的进行来确保数据的准确性，因此迭代过程中可以对字典进行增删改查等操作。

由于对字典的增删改查操作会调用 dictRehashStep 函数进行渐进式 rehash 操作，那么首先来看下 dictRehashStep 函数的源码实现：

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

原理上很简单，如果当前字典有安全迭代器运行，则不进行渐进式 rehash 操作，rehash 操作暂停，字典中数据就不会被重复遍历，由此确保了读取数据的准确性。

Redis 在执行部分命令时会使用安全迭代器来迭代字典数据，例如 keys 命令（遇到过期的键则会进行删除操作）。

安全迭代器整个迭代过程也较为简单，主要分为如下几个步骤。

1. 调用 dictGetSafeIterator 函数初始化一个安全迭代器，此时会把 iter->safe 的值置为 1；
2. 循环调用 dictNext 函数依次遍历字典中 Hash 表的节点，首次遍历时会把字典中 iterators 字段进行加 1 操作，确保迭代过程中渐进式 rehash 操作会被中断执行；
3. 当调用 dictNext 函数遍历完字典 Hash 表中节点数据后，释放迭代器时会把字典中 iterators 字段进行减 1 操作，确保迭代后渐进式 rehash 操作能正常进行。

3.2 间断遍历

前文讲解了“全遍历”字典的实现，但有一个问题凸显出来，当数据库中有海量数据时，执行 keys 命令进行一次数据库全遍历，耗时肯定不短，会造成短暂的 Redis 不可用。所以在 Redis 2.8.0 版本后新增了 scan 操作，也就是“间断遍历”。

dictScan 是“间断遍历”中的一种实现，主要在迭代字典中数据时使用。dictScan 遍历字典的过程中是可以进行 rehash 操作的，通过算法来保证所有的数据能被遍历到。

我们看下 dictScan 函数参数介绍：

unsigned long dictScan(dict *d,
                       unsigned long v,
                       dictScanFunction *fn,
                       dictScanBucketFunction* bucketfn,
                       void *privdata)

• d：表示当前迭代的字典；
• v：标识迭代开始的游标，即 Hash 表中数组索引；
• fn：表示回调函数，每遍历一个节点则调用该函数处理；
• bucketfn：在整理碎片时调用该函数；
• privdata：回调函数 fn 所需的参数。

dictScan 函数间断遍历字典过程中会遇到如下 3 种情况。

1. 从迭代开始到结束，散列表没有进行 rehash 操作。
2. 从迭代开始到结束，散列表进行了扩容或缩容操作，且恰好都为两次迭代间隔期间完成了 rehash 操作。
3. 从迭代开始到结束，某次或某几次迭代时散列表正在进行 rehash 操作。

下面对这几种情况分别考虑。

1. 遍历过程中始终未遇到 rehash 操作

每次迭代都没有遇到 rehash 操作，也就是遍历字典只遇到第 1 或第 2 种情况。

• 第 1 种情况：只要依次按照顺序遍历 Hash 表 ht[0] 中节点即可；
• 第 2 种情况：如果依然按照顺序遍历，则可能会出现数据重复或缺失读取的现象。

Redis 为了做到不漏数据且尽量不重复数据，统一采用了反向二进制迭代（Reverse Binary Iteration）算法的方法来进行间断数据迭代，见下图。

该算法的成立的条件是字典的 rehash 长度都是翻倍增加或半数减少的，可以看出，这样在字典 rehash 时可以避免重复遍历，又能完整返回原始的所有 Key。同理，字典缩容时也一样，字典缩容可以看出是反向扩容。

2. 遍历过程中遇到了 rehash 操作

rehash 操作中会同时并存两个 Hash 表：一张为扩容或缩容后的表 ht[1]，一张为老表 ht[0]，ht[0] 的数据通过渐进式 rehash 会逐步迁移到 ht[1] 中，最终完成整个迁移过程。

因为大小两表并存，所以需要从 ht[0] 和 ht[1] 中都取出数据，整个遍历过程为：先找到两个散列表中更小的表，先对小的 Hash 表遍历，然后对大的 Hash 表遍历，表内遍历顺序依旧使用反向二进制迭代（Reverse Binary Iteration）算法，从而做到不重不漏的遍历。

四、总结

• 字典被广泛用于实现 Redis 的各种功能，其中包括数据库和 Hash 键。
• Redis 中的字典使用 Hash 表作为底层实现，每个字典带有两个 Hash 表，一个用于平时使用，另一个仅在进行 rehash 时使用。
• Hash 表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对 Hash 表进行扩展或者收缩操作时，程序需要将现有 Hash 表包含的所有键值对 rehash 到新的 Hash 表里面，并且这个 rehash 过程并不是一次性地完成的，而是渐进式地完成的。

五、参考资料

• 《Redis 5 设计与源码分析》– 陈雷
• 《Redis 设计与实现》– 黄健宏
• 二进制按位与 & 及求余数 (opens new window)
• 美团针对 Redis Rehash 机制的探索和实践 (opens new window)