Redis源码解读之Dict(字典)详解

1. 简介

字典又称为符号表、关联数组或映射，是一种保存键值对的抽象数据结构。
在字典中，一个键（key）可以和一个值（value）进行关联，这些关联的键和值就称为键值对。
字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对，等等。
字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典作为底层实现的，对数据库的增，删，查，改操作也是构建在对字典的操作之上的。
举个例子，当我们执行命令：
redis > set msg 'hello world'
OK
在数据库中创建一个键为msg,值为'hello world' 的键值对时，这个键值对就保存在代表数据库的字典里面的。
除了用来表示数据库之外，字典还是哈希键底层实现之一，当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。
举个例子，website是一个包含10086个键值对的哈希键，这些哈希键的值都是一些数据库的名字，而键的值就是数据库的主页地址。
redis > hlen website
(integer) 10086

redis > hgetall website
"redis"
"redis.io"
"MariaDB"
"MariaDB.org"
"MongoDB"
"MongoDB.org"
...
website 键底层实现就是一个字段，字典中包含了10086个键值对,例如：
键值对的键为"redis",值为"redis.io".
键值对的键为"Maria",值为"Maria.io".
键值对的键为"MongoDB",值为"MongoDB.io".
当然除了实现数据库和哈希键之外，Redis的不少功能也用到了字典。接下来介绍下字典的实现

2. 字典的实现

1. 我们先来看下哈希表的定义:

/* 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;
    unsigned long sizemask;
    unsigned long used;
} dictht;

这个就是我们的哈希表结构，每个字典包含有两个这种结构，一般只使用其中一个，另外一个是来做rehash的。下面具体来看看哈希表中每个字段的含义:
table;// 是dictEntry 这种类型的一个二级指针。
size;//哈希表大小
sizemark;// 哈希表大小掩码，用于计算索引值
used;// 哈希表已使用的节点
简单来理解，上面展示的这个dictht 结构是hash table 的头部结构，table 指向的地方才是真正的hash table结构，实际上table指向的是一个数组，数组的每个元素都是dictEntry指针，这个指针指向的地方才是我们保存的数据。（注：table是一个二级指针），下面我用一张图来展示下：

dict_srtuct.png

这张图没有展示数据是怎么样的，接下来我们再看看哈希节点的结构。

2. 哈希节点结构:

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

这个就是哈希节点的结构，下面来具体看看:
key；// 这个是键，类型是void
v; //这个是一个联合体，里面可以保持指针，无符号64位，有符号64位数据，浮点数。
next;// dictEntry指针，指向下一个dictEntry节点，形成链表。下面来构建一个完整的hash table.

dict_struct.png

接下来再看看字典的结构.

3. 字典结构

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

上面这个结构就是字典结构，下面具体来看看每个字段的含义：
type;// 类型特定函数
privdata;//私有数据,保存了需要传给那些类型特定函数的可选参数。
ht[2];// 哈希表数组
rehashidx;// rehash标志，当值为-1时表示没有在rehash
下面来看下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;

上面有提到ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只会对ht[0]哈希表进行rehash时使用。
除了ht[1]之外，另一个和rehash有关的属性就是rehasgidx,它记录了rehash目前的进度，如果目前没有在进行rehash,那么它的值为-1.

3. 哈希算法

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

1. 使用字典设置的哈希函数，计算键key的哈希值
   hash = dict->type->hashFunction(key);
2. 使用哈希表的sizemark属性和哈希值，计算出索引值，根据情况不同，ht[x]可以是ht[0]或者ht[1]
   index = hash & dict->ht[x].sizemark;
   当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

4. 解决键冲突

当两个或者更多的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突。
还记得dictEntry结构的next指针吗? Redis 就是利用next指针把有冲突的键链接起来形成一个单项链表，这种方法叫做链地址法，利用这种方法有效的解决键冲突的问题。
多个冲突的键在链表中是怎么排列的呢？由于dictEntry节点组成的链表没有指向链表表尾的指针，所以为了考虑速度，程序总是将新节点添加到链表的表头位置，排在其他已有节点的前面。

5. rehash

1）. 什么时候进行rehash？
随着操作的不断进行，哈希表保存的键值对会逐渐地增多或者减少，为了让哈希表负载因子维持在一个合理的范围之内，当哈希表的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
2）. reshah 的步骤
a. 为字典ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0] 当前包含的键值对数量：
1）如果是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n(2的n次方幂).
2）如果执行的是收缩操作，那么ht[1] 的大小为第一个大于等于ht[0].used的2^n.
b. 将保存在ht[0]中的所有键值对重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
c. 当ht[0]的所有键值对都迁移到ht[1]之后（ht[0] 变为空表），释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白的哈希表，为下一次做准备。

3）. 什么时候程序开始对哈希表执行扩展操作？
a. 服务器目前没有执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于1.
b. 服务器目前正在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于5.
负载因子 = 哈希表已保存节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size
根据bgsave命令或者bgrewriteaof命令是否正在执行，服务器执行的扩展操作所需的负载因子并不相同，简单来说就是redis避免bgsave数据写入磁盘操作和rehash同时发生，最大限度地节约内存的使用。
另一方面,当哈希表的负载因子小于0.1时，程序自动开始对哈希表执行收缩操作。

4）. 渐进式rehash
上面提到过，扩展或者收缩哈希表需要将ht[0]里面的所有键值对rehash 到ht[1]里面，但是，这个rehash操作不是集中式的操作完的，而是分多次，渐进式地完成的。

5）. 为啥不是集中式的操作完的？
原因在于如果一个hash表里面包含有很多对键值对的话，如果是一次性rehash到ht[1]中的话，庞大的计算量可能会导致服务器在一段时间内停止服务。

6）. 渐进式rehash操作的详细步骤
1） 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2） 在字典中维持一个索引计数器变量rehashidx,并将它的值设置为0,表示rehash工作正式开始。
3） 在rehash进行期间，每次对字典执行添加，删除，查找或者更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1].

4. 随着字典操作的不断执行，最终在某个时间点上，ht[0]的所有键值对都会被rehash到ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。
   渐进式rehash执行期间的哈希表操作
   因为在渐进式rehash的过程中,字典同时使用ht[0]和ht[1]两个哈希表，所以在渐进式rehash进行期间，字典的删除,查找,更新等操作会在两个哈希表上进行。
   另外,新添加到字典的键值对一律会被保存到ht[1]里面。而ht[0]则不再进行任何操作。

6. 字典API

1. dictCreate ；// 创建一个新的字典
2. dictReplace； // 将给定的键值对添加到字典里面
3. dictReplace; // 将给定的键值对添加到字典里面，如果键已经存在于字典，那么用新值取代原有的值
4. dictFetchValue;// 返回给定键的值
5. dictGetRandomKey;// 从字典中随机返回一个键值对
6. dictDelete;// 从字典中删除给定键所对应的键值对
7. dictRelease;// 释放给定的字典，以及字典中包含的所有键值对