字典是Redis的重要数据结构，Redis的数据库就是使用字典作为底层实现的。代码位于dict.h和dict.c中。

1. 字典（Dict）

1.1 哈希表（Hash Table）

Redis使用哈希表实现字典。
哈希表存储键值对，将键的哈希值映射到存储位置（即索引值），加快访问速度。
Redis默认哈希算法为SipHash（待以后写文分析），使用数组+链表作为哈希表数据结构（即链地址法），哈希值模数组大小即为索引值。

1.2 Redis哈希表

哈希表结构

哈希表结构如上图所示，为行文方便定义几个名词指代上图中的组件结构：

1. ht（哈希表）：最左边的组件即为哈希表
2. table（桶数组）：ht中有字段指向数组，此数组称为table，数组长度即为哈希表大小
3. bucket（桶）：table的每一项称为bucket，bucket指向具有相同索引值的键值对链表
4. entry（节点）：链表里的节点称为entry，entry包装了键值对的key和value，同时包含next指针指向链表的下一节点

• 哈希表

typedef struct dictht {
    // 哈希桶数组
    dictEntry **table;
    // 哈希表大小，即数组长度
    unsigned long size;
    // 哈希表大小掩码常量，为数组长度-1，与哈希值与计算得出索引值
    unsigned long sizemask;
    // 哈希表已有键值对数量
    // 装载因子 = used / size
    unsigned long used;
} dictht;

• 哈希表节点

typedef struct dictEntry {
    // 键
    void *key;
    // 值，使用union以适应不同类型的值
    union {
        void *val; // 整数与浮点数直接存储，其它类型使用引用
        uint64_t u64; // 无符号整数
        int64_t s64;  // 有符号整数
        double d;  // 浮点数
    } v;
    // 指向下一个节点
    struct dictEntry *next;
} dictEntry;

1.3 字典

字典结构

字典结构为上图所示，左边组件即为字典（本文称为dict），每个字典包含两个哈希表（本文称之为ht[0]和ht[1]）。代码定义如下：

• 字典

typedef struct dict {
    // 指向字典类型结构
    dictType *type;
    // 私有数据
    void *privdata;
    // 2个哈希表
    dictht ht[2];
    // rehash索引，rehash未进行时其值为-1
    long rehashidx;
    // 当前的迭代器数量
    unsigned long iterators;
} dict;

• 字典类型

// 字典类型，保存一组操作特定类型键值对的函数
// Redis为不同的字典设置不同的类型特定函数
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;

1.4 rehash（重哈希）

在初期，字典只使用ht[0]哈希表，ht[1]为空。随着操作的不断进行，ht[0]中元素最终会偏多或偏少，为了使哈希表的装载因子维持在一个合理范围，Redis使用rehash对哈希表进行伸缩。

rehash的基本原理是新建ht[1]哈希表，将ht[0]中的元素重新计算哈希值和索引值，然后迁移到ht[1]。但是如果字典中的元素数量太多，一次性地迁移所有元素会耗费很长时间，因此Redis采用分步渐进式rehash。

分步rehash的基本原理是将一次rehash拆分成多步来完成，每步只将ht[0]中一个bucket的元素迁移到ht[1]，直到全部迁移。分步rehash详细步骤如下：

1. 每次添加元素时，判断是否需要rehash
   • 允许rehash，装载因子达到1时
   • 不允许rehash，但装载因子达到5时
2. 需要rehash，则
   • 新建ht[1]哈希表，其大小是：
     • 若是扩张，为大于等于现有节点数2倍的最小2次幂
     • 若是收缩，为大于等于现有节点的最小2次幂
   • 将字典的rehashidx字段置为0，表示开始rehash（未开始时为-1）
   • rehash对table中的bucket按顺序逐个迁移，rehashidx实际是下一步要迁移bucket的数组下标
3. 开始rehash后，每次对字典进行增删查改操作时，顺带进行一步rehash，将一个bucket的所有元素从ht[0]迁移到ht[1]
4. 最终，ht[0]中的所有元素迁移到ht[1]，然后释放ht[0]，将ht[1]置为ht[0]，rehashidx复位为-1，一次完整的rehash结束。

2. 创建字典

// 传入字典类型和私有数据，创建字典
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;
}

3. 添加元素

3.1 哈希值、键、值

• 计算键的哈希值

// 调用字典类型的hashFunction函数计算键的哈希值
#define dictHashKey(d, key) (d)->type->hashFunction(key)

• 比较键

// 若字典类型的keyCompare函数存在，则使用函数比较，否则比较是否是相同引用
#define dictCompareKeys(d, key1, key2) \
    (((d)->type->keyCompare) ? \
        (d)->type->keyCompare((d)->privdata, key1, key2) : \
        (key1) == (key2))

• 设置键

// 若字典类型的keyDup函数存在，则使用函数计算后赋值，否则直接赋值
#define dictSetKey(d, entry, _key_) do { \
    if ((d)->type->keyDup) \
        (entry)->key = (d)->type->keyDup((d)->privdata, _key_); \
    else \
        (entry)->key = (_key_); \
} while(0)

• 释放键

// 若字典类型的keyDestructor函数存在，则使用函数销毁键
#define dictFreeKey(d, entry) \
    if ((d)->type->keyDestructor) \
        (d)->type->keyDestructor((d)->privdata, (entry)->key)

• 设置值

// 若字典类型的valDup函数存在，则使用函数计算后赋值，否则直接赋值
#define dictSetVal(d, entry, _val_) do { \
    if ((d)->type->valDup) \
        (entry)->v.val = (d)->type->valDup((d)->privdata, _val_); \
    else \
        (entry)->v.val = (_val_); \
} while(0)

• 释放值

// 若字典类型的valDestructor函数存在，则使用函数销毁值
#define dictFreeVal(d, entry) \
    if ((d)->type->valDestructor) \
        (d)->type->valDestructor((d)->privdata, (entry)->v.val)

3.2 rehash

• 判断是否处于rehash中

#define dictIsRehashing(d) ((d)->rehashidx != -1)

• 完成一步rehash

static void _dictRehashStep(dict *d) {
    // 只有在无迭代器才进行rehash
    // 如果rehash时有迭代器，不能对哈希表中的元素迁移，否则可能导致迭代时元素错过或重复
    if (d->iterators == 0) dictRehash(d,1);
}

• 通用：完成n步rehash

// 进行n步rehash，如果还有键需要迁移则返回1，否则返回0
// 如果遇到空桶则继续，遇到N*10个空桶则返回，避免阻塞过久
int dictRehash(dict *d, int n) {
    // 允许遇到的最大空桶数
    int empty_visits = n*10;
    if (!dictIsRehashing(d)) return 0;
    
    // 如果ht[0]仍有元素，则进行下一步rehash
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;
        
        // rehashidx是下一个要迁移的桶的数组下标，自然要小于数组长度
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        
        // 如果遇到空桶，则顺延到下一个bucket，直到遇到最大空桶数，就返回
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        // 获取bucket链表的头节点
        de = d->ht[0].table[d->rehashidx];
        
        // 遍历链表的节点，全部迁移到ht[1]
        while(de) {
            unsigned int h;
            
            // 获取下一节点
            nextde = de->next;
            
            // 计算迁移元素在ht[1]的索引位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            // 迁移到ht[1]相应bucket链表头部
            // ht[0]中的链表，因为全部迁移，所以迁移单个节点时不进行处理
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            // 修改计数
            d->ht[0].used--;
            d->ht[1].used++;
            
            // 迭代下一节点
            de = nextde;
        }
        
        // ht[0]迁移的bucket置空
        d->ht[0].table[d->rehashidx] = NULL;
        // 设置下一步rehash要处理的bucket索引下标
        d->rehashidx++;
    }
    
    // 如果ht[0]中元素全部迁移完毕
    if (d->ht[0].used == 0) {
        // 释放ht[0]
        zfree(d->ht[0].table);
        // 将ht[1]哈希表设置为ht[0]
        d->ht[0] = d->ht[1];
        // ht[1]清空复位，以待下次rehash
        _dictReset(&d->ht[1]);
        // rehash状态设置为未开始
        d->rehashidx = -1;
        // 此次rehash完毕，返回0
        return 0;
    }
    
    // 未迁移完毕，还需下一步rehash，返回1
    return 1;
}

3.3 字典的扩张

• 如果需要则对字典进行扩张

static int _dictExpandIfNeeded(dict *d)
{
    // 如果正在rehash中，返回
    if (dictIsRehashing(d)) return DICT_OK;

    // 如果ht[0]为空哈希表，则对其进行初始化
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    // 如果允许resize，且装载因子达到1
    // 如果不允许resize，且装载因子达到5
    if (d->ht[0].used >= d->ht[0].size && (dict_can_resize ||
         d->ht[0].used/d->ht[0].size > dict_force_resize_ratio)) {
         // 按照当前节点数的2倍进行扩张（进行rehash）
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

• 相关参数

// 字典初始大小
#define DICT_HT_INITIAL_SIZE     4

// 默认允许resize
static int dict_can_resize = 1;

// 不允许resize时，强制进行resize要达到的负载因子
static unsigned int dict_force_resize_ratio = 5;

• 获取大于等于指定大小的最小2次幂，作为实际哈希表的大小

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;
    if (size >= LONG_MAX) return LONG_MAX;
    while(1) {
        if (i >= size) return i;
        i *= 2;
    }
}

• 将字典扩张到指定大小

int dictExpand(dict *d, unsigned long size)
{
    // 创建新哈希表ht[1]
    dictht n;
    
    // 将指定大小值进行规整：不小于size的最小2次幂值
    unsigned long realsize = _dictNextPower(size);
    
    // 判断扩张大小无效的情况
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;
    if (realsize == d->ht[0].size) return DICT_ERR;
    
    // 设置新哈希表属性
    n.size = realsize;
    n.sizemask = realsize-1;
    // 按新的哈希表大小创建table数组
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    
    // 若是初始化，则此次不是rehash，将新哈希表设置为ht[0]即可。
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }
    
    // 若ht[0]存在，则此次是rehash，将新哈希表设置为ht[1]
    // 并且设置为开始rehash状态，以便操作元素时进行rehash
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

3.4 添加元素

• 向字典添加键值对

int dictAdd(dict *d, void *key, void *val)
{
    // 将键构造成节点加入哈希表
    dictEntry *entry = dictAddRaw(d,key,NULL);
    if (!entry) return DICT_ERR;
    
    // 设置节点的值
    dictSetVal(d, entry, val);
    return DICT_OK;
}

• 添加或查找键，若查找到则existing指向节点返回null，若添加成功则返回节点

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    
    // 若处于rehash中，则完成一步rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 计算键的哈希值，判断键是否已存在
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    // 若正在rehash，则使用ht[1]哈希表，否则使用ht[0]哈希表
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    // 为哈希表节点申请内存
    entry = zmalloc(sizeof(*entry));
    // 根据键的索引值寻找bucket链表，插入到表头
    entry->next = ht->table[index];
    ht->table[index] = entry;
    // 增加节点计数
    ht->used++;
    
    // 设置节点的键
    dictSetKey(d, entry, key);
    return entry;
}

• 查找键是否已在哈希表中，若存在返回-1，若不存在则返回键的索引值

// 若existing非空，且键在哈希表中，则设置其指向键的节点
static int _dictKeyIndex(dict *d, const void *key, unsigned int hash, dictEntry **existing)
{
    unsigned int idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    // 检查字典装载因子，若需要则扩张字典
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    // 遍历哈希表
    for (table = 0; table <= 1; table++) {
        // 找到键的索引值对应的bucket
        idx = hash & d->ht[table].sizemask;
        // 遍历bucket中的节点
        he = d->ht[table].table[idx];
        while(he) {
            // 判断节点与键是否相同
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                // 如果找到键，返回-1
                return -1;
            }
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    
    return idx;
}

4. 查找元素

// 查找键对应的节点
dictEntry *dictFind(dict *d, const void *key)
{
    dictEntry *he;
    unsigned int h, idx, table;
    
    // 若字典为空返回NULL
    if (d->ht[0].used + d->ht[1].used == 0) return NULL;
    
    // 若正在rehash，进行一步rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 计算键的哈希值
    h = dictHashKey(d, key);
    
    // 遍历两个哈希表
    for (table = 0; table <= 1; table++) {
        // 计算键在哈希表的索引值
        idx = h & d->ht[table].sizemask;
        // 获取键所在bucket链表的头节点
        he = d->ht[table].table[idx];
        // 遍历链表节点
        while(he) {
            // 若键相同，则返回节点
            if (key==he->key || dictCompareKeys(d, key, he->key))
                return he;
            he = he->next;
        }
        // 若没有在rehash，则ht[1]为空，不需要遍历，直接返回
        if (!dictIsRehashing(d)) return NULL;
    }
    return NULL;
}

5. 替代元素

// 若键存在则替代值，若不存在则添加键值对
// 添加成功返回1，替代成功返回0
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, *existing, auxentry;

    // dictAddRaw：若键存在，则existing指向节点返回null，若键不存在，则添加并返回节点
    entry = dictAddRaw(d,key,&existing);
    if (entry) {
        // 添加成功，设置值，返回1
        dictSetVal(d, entry, val);
        return 1;
    }
    
    // 更新节点：设置新值、释放旧值、返回0
    auxentry = *existing;
    dictSetVal(d, existing, val);
    dictFreeVal(d, &auxentry);
    return 0;
}

6. 删除元素

// 删除键对应的元素，成功返回DICT_OK，找不到元素返回DICT_ERR
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0) ? DICT_OK : DICT_ERR;
}

// 删除键对应的元素，删除成功返回其节点，找不到元素返回NULL
static dictEntry *dictGenericDelete(dict *d, const void *key, int nofree) {
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;

    // 字典为空返回NULL
    if (d->ht[0].used == 0 && d->ht[1].used == 0) return NULL;
    
    // 正在rehash，进行一步rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);
    
    // 计算键的哈希值
    h = dictHashKey(d, key);
    
    // 遍历哈希表
    for (table = 0; table <= 1; table++) {
        // 计算键的索引值
        idx = h & d->ht[table].sizemask;
        // 键所在bucket链表的头节点
        he = d->ht[table].table[idx];
        prevHe = NULL;
        // 从头节点依次遍历整个链表
        while(he) {
            // 若找到相同键节点
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                // 将节点从链表中移除
                if (prevHe) // 若是中间节点
                    prevHe->next = he->next;
                else // 若是头节点
                    d->ht[table].table[idx] = he->next;
                
                if (!nofree) {
                    // 释放键
                    dictFreeKey(d, he);
                    // 释放值
                    dictFreeVal(d, he);
                    // 释放节点
                    zfree(he);
                }
                // 节点计数减1
                d->ht[table].used--;
                // 返回删除的节点
                return he;
            }
            // 当前节点不是，移动到下一节点
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;
    }
    return NULL;
}

7. 释放字典

// 清空并释放字典
void dictRelease(dict *d)
{
    // 清空两个哈希表
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    // 释放字典内存
    zfree(d);
}

// 清空哈希表
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {
    unsigned long i;

    // 遍历哈希表所有节点
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;

        if (callback && (i & 65535) == 0) callback(d->privdata);
        // 若遇到空桶，跳过
        if ((he = ht->table[i]) == NULL) continue;
        // 从桶的头节点开始遍历节点，释放节点的键、值和内存
        while(he) {
            nextHe = he->next;
            dictFreeKey(d, he);
            dictFreeVal(d, he);
            zfree(he);
            ht->used--;
            he = nextHe;
        }
    }
    // 释放table数组
    zfree(ht->table);
    // 重置字典
    _dictReset(ht);
    return DICT_OK;
}

8. 迭代器

8.1 迭代器定义

// 如果safe为1，则是安全迭代器，可在迭代时可调用dictAdd、dictFind以及其它函数
// 如果safe为0，则是非安全迭代器，在迭代时只可调用dictNext()
typedef struct dictIterator {
    // 字典引用
    dict *d;
    // 字典的哈希表下标
    int table;
    // 哈希表的bucket数组下标
    long index;
    // 指向bucket的链表中上一次返回的节点
    dictEntry *entry;
    // 指向bucket的链表中下一次返回的节点
    dictEntry *nextEntry;
    
    // 1，安全模式；0，非安全模式
    int safe;
    // 非安全模式下，在迭代器创建时，计算字典状态的指纹
    long long fingerprint;
} dictIterator;

8.2 获取迭代器

// 非安全迭代器
dictIterator *dictGetIterator(dict *d)
{
    dictIterator *iter = zmalloc(sizeof(*iter));
    // 设置字典引用
    iter->d = d;
    // 指向ht[0]哈希表
    iter->table = 0;
    iter->index = -1;
    // 非安全模式
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

// 安全迭代器
dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);
    i->safe = 1;
    return i;
}

8.3 获取下一元素

// 使用迭代器获取下一元素
// 按照哈希表数组、bucket数组、节点链表依次遍历节点
dictEntry *dictNext(dictIterator *iter)
{
    while (1) {
        // entry为null，表示已遍历完一个bucket的链表，或者是第一次使用迭代器
        if (iter->entry == NULL) {
            
            // 获取当前的哈希表
            dictht *ht = &iter->d->ht[iter->table];
            
            // 如果是初次使用迭代器，设置相关参数
            if (iter->index == -1 && iter->table == 0) {
                // 若为安全迭代器，则字典的迭代器计数加1
                if (iter->safe)
                    iter->d->iterators++;
                // 若为非安全迭代器，计算字典当前状态的指纹
                else 
                    iter->fingerprint = dictFingerprint(iter->d);
            }
            
            // 遍历完一个bucket，则顺延至下一bucket
            iter->index++;
            
            // 若当前哈希表已遍历完
            if (iter->index >= (long) ht->size) {
                // 若为遍历完ht[0]且正在rehash，则还需要遍历ht[1]；否则ht[1]为空，不需遍历
                if (dictIsRehashing(iter->d) && iter->table == 0) {
                    iter->table++;
                    iter->index = 0;
                    ht = &iter->d->ht[1];
                } else {
                    break;
                }
            }
            
            // 开始遍历新的bucket链表，此次返回链表的头节点
            iter->entry = ht->table[iter->index];
            
        } else { // 还在遍历一个bucket链表
            // 将下一节点设置为当前节点
            iter->entry = iter->nextEntry;
        }
        
        if (iter->entry) {
            // 设置下一节点
            iter->nextEntry = iter->entry->next;
            // 返回当前节点
            return iter->entry;
        }
    }
    return NULL;
}

8.4 释放迭代器

void dictReleaseIterator(dictIterator *iter)
{
    if (!(iter->index == -1 && iter->table == 0)) {  // 如果迭代器使用过
        if (iter->safe) // 若为安全模式，字典迭代器计数减1
            iter->d->iterators--;
        else // 若为非安全模式，检查迭代期间字典是否变更
            assert(iter->fingerprint == dictFingerprint(iter->d));
    }
    // 释放迭代器内存
    zfree(iter);
}