字典也被称为映射(map)，经常作为一种数据结构内置在很多高级编程语言里面。但是Redis所使用的C语言并没有内置这种数据结构，因此Redis构建了自己的字典实现。
字典在Redis中的应用相当广泛，比如Redis的数据库就是使用字典来作为底层实现的，对数据库的增删改查也是构建在对字典的操作之上的。字典还是哈希键的底层实现之一。当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字典作为哈希键的底层实现。
字典的实现
Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。
接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现。
哈希表
Redis 字典所使用的哈希表由 dict.h/dictht 结构定义：
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。
下图是一个大小为4的空哈希表：
哈希表节点
哈希表节点使用 dictEntry 结构表示， 每个 dictEntry 结构都保存着一个键值对：
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;key 属性保存着键值对中的键， 而 v 属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个 uint64_t 整数， 又或者是一个 int64_t 整数。
next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。
下图展示了Redis中如何用拉链法解决键冲突：
字典
Redis 中的字典由 dict.h/dict 结构表示：
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;type 属性和 privdata 属性是针对不同类型的键值对， 为创建多态字典而设置的：
type属性是一个指向dictType结构的指针， 每个dictType结构保存了一簇用于操作特定类型键值对的函数， Redis 会为用途不同的字典设置不同的类型特定函数。- 而
privdata属性则保存了需要传给那些类型特定函数的可选参数。
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;ht 属性是一个包含两个项的数组， 数组中的每个项都是一个 dictht 哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用。
除了 ht[1] 之外， 另一个和 rehash 有关的属性就是 rehashidx ： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。
下图展示了一个没有进行rehash的字典：
哈希算法
当要将一个新的键值对添加到字典里面时， 程序需要先根据键值对的键计算出哈希值和索引值， 然后再根据索引值， 将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。
Redis 计算哈希值和索引值的方法如下：
# 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值，计算出索引值
# 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
解决键冲突
如在字典的实现一节中所述，在Redis中是用拉链法来解决键冲突问题的。
rehash
随着操作的不断执行， 哈希表保存的键值对会逐渐地增多或者减少， 为了让哈希表的负载因子（load factor）维持在一个合理的范围之内， 当哈希表保存的键值对数量太多或者太少时， 程序需要对哈希表的大小进行相应的扩展或者收缩。
扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成， Redis 对字典的哈希表执行 rehash 的步骤如下：
-
为字典的
ht[1]哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及ht[0]当前包含的键值对数量 （也即是ht[0].used属性的值）：- 如果执行的是扩展操作， 那么
ht[1]的大小为第一个大于等于ht[0].used * 2的 $2^n$（2的n次方幂）； - 如果执行的是收缩操作， 那么
ht[1]的大小为第一个大于等于ht[0].used的 $2^n$ 。
- 如果执行的是扩展操作， 那么
-
将保存在
ht[0]中的所有键值对 rehash 到ht[1]上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到ht[1]哈希表的指定位置上。 -
当
ht[0]包含的所有键值对都迁移到了ht[1]之后 （ht[0]变为空表）， 释放ht[0]， 将ht[1]设置为ht[0]， 并在ht[1]新创建一个空白哈希表， 为下一次 rehash 做准备。
哈希表扩展与收缩的条件：
- 当以下条件中的任意一个被满足时， 程序会自动开始对哈希表执行扩展操作：
- 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于
1；
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令， 并且哈希表的负载因子大于等于
5；其中哈希表的负载因子可以通过公式：
# 负载因子 = 哈希表已保存节点数量 / 哈希表大小 load_factor = ht[0].used / ht[0].size
- 当哈希表的负载因子小于
0.1时， 程序自动开始对哈希表执行收缩操作。
渐进式 rehash
当哈希表里面保存有大量的键值对的时候，如果rehash是一次性、集中式地完成，那么庞大的计算量可能会导致服务器在一段时间内停止服务。因此，Redis中的rehash动作是分多次、渐进式地完成的，称之为渐进式rehash。
以下是哈希表渐进式 rehash 的详细步骤：
- 为
ht[1]分配空间， 让字典同时持有ht[0]和ht[1]两个哈希表。 - 在字典中维持一个索引计数器变量
rehashidx， 并将它的值设置为0， 表示 rehash 工作正式开始。 - 在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将
ht[0]哈希表在rehashidx索引上的所有键值对 rehash 到ht[1]， 当 rehash 工作完成之后， 程序将rehashidx属性的值增一。 - 随着字典操作的不断执行， 最终在某个时间点上，
ht[0]的所有键值对都会被 rehash 至ht[1]， 这时程序将rehashidx属性的值设为-1， 表示 rehash 操作已完成。
渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。
渐进式 rehash 执行期间的哈希表操作:
因为在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。
另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 ht[1] 里面， 而 ht[0] 则不再进行任何添加操作： 这一措施保证了 ht[0] 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。
文章评论