字典，又称为符号表、关联数组或映射，是一种用于保存键值对的抽象数据结构。

Redis构建了自己的字典实现，并应用在自己的数据库中，对数据库的增删改查操作都是构建在对字典的操作之上。

1.字典的实现

Redis的字典使用哈希表作为底层实现，一个哈希表里面可以有多个哈希节点，而每个哈希节点就保存了字典中的一个键值对。

1.1 哈希表

Redis字典所使用的哈希表由dict.h/dictht结构定义：

/*
 * 哈希表
 *
 * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
 */
typedef struct dictht {
    
    // 哈希表数组,数组中的每个元素都是一个指向dict.h/dictEntry结构的指针
    dictEntry **table;

    // 哈希表大小,即table数组的大小
    unsigned long size;
    
    // 哈希表大小掩码，用于计算索引值
    // 总是等于 size - 1
    unsigned long sizemask;

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

} dictht;

下图展示了一个大小为4的空哈希表

image

1.2 哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构都保存着一个键值对:

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

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

    // 指向下个哈希表节点，形成链表，解决冲突问题
    struct dictEntry *next;

} dictEntry;

下图展示了如何通过next指针，将两个索引值相同的键k1和k0连接在一起

image

1.3 字典

Redis中的字典由dict.h/dict结构来表示:

/*
 * 字典
 */
typedef struct dict {

    // 类型特定函数,Redis为用途不同的字典设置不同的值
    dictType *type;

    // 私有数据
    void *privdata;

    // 哈希表,一般情况下只使用ht[0]哈希表，ht[1]只会在rehash的时候使用
    dictht ht[2];

    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */

} 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;

下图展示了一个普通状态下的字典

image

2. 哈希算法

当要将一个键值对添加到字典里面时，需要先计算出哈希索引值，然后再根据哈希索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
具体步骤如下：

1. 如果要将一个键值对k0和v0添加到字典里面，会先使用语句，hash=dict->type->hashFunction(k0);
2. 如果计算出哈希值为8，那么程序会继续使用语句:index = hash&dict->ht[0].sizemask = 8 & 3 = 0;
3. 计算出索引值为0后，就把包含键值对的k0和v0节点放置到哈希表数组的索引0位置上

3. 解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，就称为哈希冲突。

Redis的哈希表使用链地址法来解决冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以通过next指针构成一个单向链表，被分配到同一个索引上的多个节点，可以通过这个单向链表连接起来，解决了冲突。

4. rehash

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表的负载因子（load fctor）维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。

具体步骤如下：

1. 为字典的ht[1]哈希表分配空间，空间大小跟操作类型有关，以及ht[0].used属性的值
   • 如果执行的是扩展操作：那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n
   • 如果执行的是收缩操作：那么ht[1]的大小为第一个大于等于ht[0].used的2^n
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面：即重新计算哈希值
3. 当ht[0]包含的所有键值对都迁移到ht[1]上，就会释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空哈希表，为下一次rehash做准备

4.1 哈希表的扩展与收缩

扩展条件为以下二选一：

1. 服务器目前没有在执行BGS4VE命令或者 BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
2. 服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

收缩条件：
当哈希表的负载因子小于0.1时，程序自动开始对哈希表进行收缩。

负载因子公式：load_factor = ht[0].used / ht[0].size

5. 渐进式rehash

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

原因是如果哈希表保存的键值对数量是几百万、几千万甚至上亿时，一次性将这些键值对全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

具体步骤为：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
2. 在字典中维持一个索引计数器rehashidx变量，并将它的值设为0，表示rehash工作正式开始
3. 在rehash进行期间，每次对字典进行增删改查操作时，程序除了执行指定操作外，还会顺带将ht[0]哈希表rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成后，将rehashidx属性的值增一
4. 随着字典操作的不断执行，最终ht[0]的所有键值对都会被rehash到ht[1]，这时程序将rehashidx的属性值设为-1，表示rehash操作已完成。

5.1 渐进式rehash执行期间的哈希表操作

因为在进行渐进式rehash的过程中，字典会同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行。例如，要在字典里面查找一个键的话，程序会先在ht[0]里面进行查找，如果没找到的话，就会继续到ht[1] 里面进行查找，诸如此类。

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

6. 相关源码

6.1 dictCreate 创建一个新的字典

/*
 * 创建一个新的字典
 *
 * T = O(1)
 */
dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));
    // 初始化哈希表
    _dictInit(d,type,privDataPtr);

    return d;
}

/*
 * 初始化哈希表
 *
 * T = O(1)
 */
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;
}

6.2 dictAdd 将给定的键值对添加到字典里面

/*
 * 尝试将给定键值对添加到字典中
 *
 * 只有给定键 key 不存在于字典时，添加操作才会成功
 *
 * 添加成功返回 DICT_OK ，失败返回 DICT_ERR
 *
 * 最坏 T = O(N) ，平滩 O(1) 
 */
int dictAdd(dict *d, void *key, void *val)
{
    // 尝试添加键到字典，并返回包含了这个键的新哈希节点
    // T = O(N)
    dictEntry *entry = dictAddRaw(d,key);

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

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

    // 添加成功
    return DICT_OK;
}

/*
 * 尝试将键插入到字典中
 *
 * 如果键已经在字典存在，那么返回 NULL
 *
 * 如果键不存在，那么程序创建新的哈希节点，
 * 将节点和键关联，并插入到字典，然后返回节点本身。
 *
 * T = O(N)
 */
dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;

    // 如果条件允许的话(看是否正在进行rehash)，进行单步 rehash
    // T = O(1)
    if (dictIsRehashing(d)) _dictRehashStep(d);

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    // 计算键在哈希表中的索引值
    // 如果值为 -1 ，那么表示键已经存在
    // T = O(N)
    if ((index = _dictKeyIndex(d, key)) == -1)
        return NULL;

    // T = O(1)
    /* Allocate the memory and store the new entry */
    // 如果字典正在 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. */
    // 设置新节点的键
    // T = O(1)
    dictSetKey(d, entry, key);

    return entry;
}

/* Returns the index of a free slot that can be populated with
 * a hash entry for the given 'key'.
 * If the key already exists, -1 is returned.
 *
 * 返回可以将 key 插入到哈希表的索引位置
 * 如果 key 已经存在于哈希表，那么返回 -1
 *
 * Note that if we are in the process of rehashing the hash table, the
 * index is always returned in the context of the second (new) hash table. 
 *
 * 注意，如果字典正在进行 rehash ，那么总是返回 1 号哈希表的索引。
 * 因为在字典进行 rehash 时，新节点总是插入到 1 号哈希表。
 *
 * T = O(N)
 */
static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    // 单步 rehash
    // T = O(N)
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;

    /* Compute the key hash value */
    // 计算 key 的哈希值
    h = dictHashKey(d, key);
    // T = O(1)
    for (table = 0; table <= 1; table++) {

        // 计算索引值
        idx = h & d->ht[table].sizemask;

        /* Search if this slot does not already contain the given key */
        // 查找 key 是否存在
        // T = O(1)
        he = d->ht[table].table[idx];
        while(he) {
            if (dictCompareKeys(d, key, he->key))
                return -1;
            he = he->next;
        }

        // 如果运行到这里时，说明 0 号哈希表中所有节点都不包含 key
        // 如果这时 rehahs 正在进行，那么继续对 1 号哈希表进行 rehash
        if (!dictIsRehashing(d)) break;
    }

    // 返回索引值
    return idx;
}

6.3 dictReplace 将给定的键值对添加到字典里面，如果键已经存在于字典，那么用新值取代原有的值

/* Add an element, discarding the old if the key already exists.
 *
 * 将给定的键值对添加到字典中，如果键已经存在，那么删除旧有的键值对。
 *
 * Return 1 if the key was added from scratch, 0 if there was already an
 * element with such key and dictReplace() just performed a value update
 * operation. 
 *
 * 如果键值对为全新添加，那么返回 1 。
 * 如果键值对是通过对原有的键值对更新得来的，那么返回 0 。
 *
 * T = O(N)
 */
int dictReplace(dict *d, void *key, void *val)
{
    dictEntry *entry, auxentry;

    /* Try to add the element. If the key
     * does not exists dictAdd will suceed. */
    // 尝试直接将键值对添加到字典
    // 如果键 key 不存在的话，添加会成功
    // T = O(N)
    if (dictAdd(d, key, val) == DICT_OK)
        return 1;

    /* It already exists, get the entry */
    // 运行到这里，说明键 key 已经存在，那么找出包含这个 key 的节点
    // T = O(1)
    entry = dictFind(d, key);
    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    // 先保存原有的值的指针
    auxentry = *entry;
    // 然后设置新的值
    // T = O(1)
    dictSetVal(d, entry, val);
    // 然后释放旧值
    // T = O(1)
    dictFreeVal(d, &auxentry);

    return 0;
}

6.4 dictFetchValue 返回给定键的值

/*
 * 获取包含给定键的节点的值
 *
 * 如果节点不为空，返回节点的值
 * 否则返回 NULL
 *
 * T = O(1)
 */
void *dictFetchValue(dict *d, const void *key) {
    dictEntry *he;

    // T = O(1)
    he = dictFind(d,key);

    return he ? dictGetVal(he) : NULL;
}

6.5 dictGetRandomKey 从字典中随机返回一个键值对

/* Return a random entry from the hash table. Useful to
 * implement randomized algorithms */
/*
 * 随机返回字典中任意一个节点。
 *
 * 可用于实现随机化算法。
 *
 * 如果字典为空，返回 NULL 。
 *
 * T = O(N)
*/
dictEntry *dictGetRandomKey(dict *d)
{
    dictEntry *he, *orighe;
    unsigned int h;
    int listlen, listele;

    // 字典为空
    if (dictSize(d) == 0) return NULL;

    // 进行单步 rehash
    if (dictIsRehashing(d)) _dictRehashStep(d);

    // 如果正在 rehash ，那么将 1 号哈希表也作为随机查找的目标
    if (dictIsRehashing(d)) {
        // T = O(N)
        do {
            h = random() % (d->ht[0].size+d->ht[1].size);
            he = (h >= d->ht[0].size) ? d->ht[1].table[h - d->ht[0].size] :
                                      d->ht[0].table[h];
        } while(he == NULL);
    // 否则，只从 0 号哈希表中查找节点
    } else {
        // T = O(N)
        do {
            h = random() & d->ht[0].sizemask;
            he = d->ht[0].table[h];
        } while(he == NULL);
    }

    /* Now we found a non empty bucket, but it is a linked
     * list and we need to get a random element from the list.
     * The only sane way to do so is counting the elements and
     * select a random index. */
    // 目前 he 已经指向一个非空的节点链表
    // 程序将从这个链表随机返回一个节点
    listlen = 0;
    orighe = he;
    // 计算节点数量, T = O(1)
    while(he) {
        he = he->next;
        listlen++;
    }
    // 取模，得出随机节点的索引
    listele = random() % listlen;
    he = orighe;
    // 按索引查找节点
    // T = O(1)
    while(listele--) he = he->next;

    // 返回随机节点
    return he;
}