「Redis设计与实现」字典篇

字典简介

字典， 又称符号表（symbol table）、关联数组（associative array）或者映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构。
在字典中， 一个键（key）可以和一个值（value）进行关联（或者说将键映射为值）， 这些关联的键和值就被称为键值对。

字典中的每个键都是独一无二的， 程序可以在字典中根据键查找与之关联的值， 或者通过键来更新值， 又或者根据键来删除整个键值对， 等等。

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

字典在 Redis 中的应用相当广泛， 比如 Redis 的数据库就是使用字典来作为底层实现的， 对数据库的增、删、查、改操作也是构建在对字典的操作之上的。
如，当我们执行命令：

redis> SET msg "hello world"
OK

在数据库中创建一个键为 "msg" ， 值为 "hello world" 的键值对时， 这个键值对就是保存在代表数据库的字典里面的。

字典的实现

Redis 的字典使用哈希表作为底层实现， 一个哈希表里面可以有多个哈希表节点， 而每个哈希表节点就保存了字典中的一个键值对。接下来的三个小节将分别介绍 Redis 的哈希表、哈希表节点、以及字典的实现。

• 哈希表

typedef struct dictht {
    dictEntry **table; /* 哈希表数组 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /*哈希表大小掩码，用于计算索引值 总是等于 size - 1*/
    unsigned long used; /* 该哈希表已有节点的数量 */
} dictht;

1. table 属性是一个数组， 数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针， 每个 dictEntry 结构保存着一个键值对。
2. size 属性记录了哈希表的大小， 也即是 table 数组的大小， 而 used 属性则记录了哈希表目前已有节点（键值对）的数量。
3. sizemask 属性的值总是等于 size - 1 ， 这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面。

• 哈希表节点

typedef struct dictEntry {
    void *key; /* 键 */
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; /* 指向下个哈希表节点，形成链表，hash键冲突时才被用到 */
} dictEntry;

1. 哈希表节点使用dictEntry结构表示， 每个dictEntry结构都保存着一个键值对
2. key属性保存着键值对中的键， 而v属性则保存着键值对中的值， 其中键值对的值可以是一个指针， 或者是一个uint64_t整数， 又或者是一个int64_t整数。
3. next属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一次， 以此来解决键冲突（collision）的问题。

• 字典
  字典结构用dict表示，此结构能很方便的支持rehash

typedef struct dict {
    dictType *type; /* 类型特定函数 */
    void *privdata; /* 私有数据 */
    dictht ht[2]; /* 哈希表 */
    int rehashidx; /* rehash 索引 当 rehash 不在进行时，值为 -1 */
    int iterators; /* 目前正在运行的安全迭代器的数量 */
} dict;

1. type属性和privdata属性是针对不同类型的键值对， 为创建多态字典而设置的
2. ht属性是一个包含两个项的数组， 数组中的每个项都是一个dictht哈希表， 一般情况下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用
3. 除了 ht[1] 之外， 另一个和 rehash 有关的属性就是rehashidx： 它记录了 rehash 目前的进度， 如果目前没有在进行 rehash ， 那么它的值为 -1 。

下图展示了一个普通状态下（没有进行 rehash）的字典：

普通字典结构.png

哈希算法

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

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

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

可以看出，redis对进入的字符串首先做一层hashFunction操作，将其转换成unsigned int型, 再将其和hash表的sizemask做与操作，得到index。

图4-4.png
举个例子， 对于图 4-4 所示的字典来说， 如果我们要将一个键值对 k0 和 v0 添加到字典里面， 那么程序会先使用语句：
hash = dict->type->hashFunction(k0);
计算键 k0 的哈希值。
假设计算得出的哈希值为 8 ， 那么程序会继续使用语句：
index = hash & dict->ht[0].sizemask = 8 & 3 = 0;
计算出键 k0 的索引值 0 ， 这表示包含键值对 k0 和 v0 的节点应该被放置到哈希表数组的索引 0 位置上， 如图 4-5 所示。
图4-5.png
当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
可参考：http://code.google.com/p/smhasher/ 。

解决冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时， 我们称这些键发生了冲突（collision）。

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

此处简单，不再摘出书中例子。

rehash

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

扩展和收缩哈希表的工作可以通过执行 rehash （重新散列）操作来完成， Redis 对字典的哈希表执行 rehash 的步骤如下：

1. 为字典的 ht[1] 哈希表分配空间， 这个哈希表的空间大小取决于要执行的操作， 以及 ht[0] 当前包含的键值对数量 （也即是 ht[0].used 属性的值）：
   • 如果执行的是扩展操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used * 2 的 2^n （2 的 n 次方幂）；
   • 如果执行的是收缩操作， 那么 ht[1] 的大小为第一个大于等于 ht[0].used 的 2^n 。
2. 将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上面： rehash 指的是重新计算键的哈希值和索引值， 然后将键值对放置到 ht[1] 哈希表的指定位置上。
3. 当 ht[0] 包含的所有键值对都迁移到了 ht[1] 之后 （ht[0] 变为空表）， 释放 ht[0] ， 将 ht[1] 设置为 ht[0] ， 并在 ht[1] 新创建一个空白哈希表， 为下一次 rehash 做准备。

举个例子， 假设程序要对图 4-8 所示字典的 ht[0] 进行扩展操作， 那么程序将执行以下步骤：

1. ht[0].used 当前的值为 4 ， 4 * 2 = 8 ， 而 8 （2^3）恰好是第一个大于等于 4 的 2 的 n 次方， 所以程序会将 ht[1] 哈希表的大小设置为 8 。 图 4-9 展示了 ht[1] 在分配空间之后， 字典的样子。
2. 将 ht[0] 包含的四个键值对都 rehash 到 ht[1] ， 如图 4-10 所示。
3. 释放 ht[0] ，并将 ht[1] 设置为 ht[0] ，然后为 ht[1] 分配一个空白哈希表，如图 4-11 所示。

至此， 对哈希表的扩展操作执行完毕， 程序成功将哈希表的大小从原来的 4 改为了现在的 8 。
图 4-12 至图 4-17 展示了一次完整的渐进式 rehash 过程， 注意观察在整个 rehash 过程中， 字典的 rehashidx 属性是如何变化的。

4-12.png
4-13.png
4-14.png
4-15.png
4-16.png
4-17.png

字典API

函数	作用	时间复杂度
dictCreate	创建一个新的字典。	O(1)
dictAdd	将给定的键值对添加到字典里面。	O(1)
dictReplace	将给定的键值对添加到字典里面， 如果键已经存在于字典，那么用新值取代原有的值。	O(1)
dictFetchValue	返回给定键的值。	O(1)
dictGetRandomKey	从字典中随机返回一个键值对。	O(1)
dictDelete	从字典中删除给定键所对应的键值对。	O(1)
dictRelease	释放给定字典，以及字典中包含的所有键值对。	O(N) ， N 为字典包含的键值对数量。