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 就会使用字典作为哈希键的底层实现。

举个例子， website 是一个包含 10086 个键值对的哈希键， 这个哈希键的键都是一些数据库的名字， 而键的值就是数据库的主页网址：

redis> HLEN website
(integer) 10086
​
redis> HGETALL website
1) "Redis"
2) "Redis.io"
3) "MariaDB"
4) "MariaDB.org"
5) "MongoDB"
6) "MongoDB.org"
# ...

website 键的底层实现就是一个字典， 字典中包含了 10086 个键值对：

• 其中一个键值对的键为 "Redis" ， 值为 "Redis.io" 。

• 另一个键值对的键为 "MariaDB" ， 值为 "MariaDB.org" ；

• 还有一个键值对的键为 "MongoDB" ， 值为 "MongoDB.org" ；

诸如此类。

除了用来实现数据库和哈希键之外， Redis 的不少功能也用到了字典， 在后续的章节中会不断地看到字典在 Redis 中的各种不同应用。

本章接下来的内容将对 Redis 的字典实现进行详细的介绍， 并列出字典的操作 API 。

本章不会对字典的基本定义和基础算法进行介绍， 如果有需要的话， 可以参考以下这些资料：

• 维基百科的 Associative Array 词条（http://en.wikipedia.org/wiki/Associative_array）和 Hash Table 词条（http://en.wikipedia.org/wiki/Hash_table）。

• 《算法：C 语言实现（第 1 ～ 4 部分）》一书的第 14 章。

• 《算法导论（第三版）》 一书的第 11 章。

字典的实现

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 ， 这