Dict简介

字典（dict）是Redis一个重要的基础数据结构，它是一个用于维护key和value映射关系的数据结构，与很多语言中的Map或dictionary类似。不过，这只是它在Redis中的一个用途而已，它在Redis中被使用的地方还有很多。比如Redis的数据库就是使用字典来作为底层实现的，对数据的增删查改操作都是构建在对字典的操作之上，又比如，一个Redis hash结构，当它的field较多时，便会采用dict来存储。再比如，Redis配合使用dict和skiplist来共同维护一个sorted set。


字典经常作为一种数据结构内置在很多高级的编程语言里，但Redis的实现所使用的C语言中并没有内置这种数据结构，因此Redis构建了自己的字典实现。

Dict的双数组哈希表

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privatedata;

    // 哈希表
    dictht ht[2];

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

其中ht属性是一个包含两个项的数组，数组中的每个项都是一个dictht哈希表，一般情况下，字典只使用ht[0]哈希表，ht[1]哈希表只用于对ht[0]哈希表进行rehash时。

除了ht[1]之外，另一个和rehash有关的属性就是rehashidx，它记录了rehash目前的进度，如果目前没有在进行rehash，那么它的值为-1。

哈希算法

Redis计算哈希值和索引值的方法：

1
2
3
4
5
6

# 使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希值的 sizemark 属性和和哈希值，计算出索引值
# 根据情况不同，ht[x]可以是ht[0]或者ht[1]
index = hash & dict->ht[x].sizemark;

当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。

键冲突

键冲突解决方法是链地址法（拉链法），与Java里的hashmap一样使用单向链表把同一个索引上的多个节点连接起来。
因为dictEntry节点组成的链表没有指向链表表尾的指针，所以为了速度考虑，程序总是把新节点添加到链表的表头位置（复杂度为O(1)），排在其它已有节点的前面。

Rehash

哈希表的扩展与收缩是通过执行rehash（重新散列）操作来完成，操作步骤如下：

1. 空间分配：
   为字典的ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（也即是ht[0].used属性的值）:

• 如果是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2ⁿ（2的n次幂）。
• 如果是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2ⁿ。

2. rehash：
   将保存在ht[0]中的所有键值对rehash到ht[1]上面：rehash指的是重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表的指定位置上。
3. 替换：
   当ht[0]包含的所有键值对都迁移到ht[1]之后（ht[0]变为空表），释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash做准备。

哈希表的扩展与收缩

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：

1. 没在执行BGSAVE命令或者BGREWRITEAOF命令，而哈希表的负载因子≥1。

2. 有在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子≥0.5。

   负载因子计算为：
   load_factor = ht[0].used / ht[0].size;

负载因子＜0.1时，进行收缩操作。

渐进式rehash

Redis的扩展或收缩需要把ht[0]所有键值对rehash到ht[1]里，这个动作并不是一次性、集中式完成的，而是分多次、渐进式完成的。
这么做的原因是，当哈希表数据量庞大到一定量级时，一次性rehash操作会带来庞大的计算量，这样可能会导致服务器在一段时间内停止服务。
以下是渐进式rehash的详细步骤：

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