Redis 数据结构之字典

2019-02-04 本文已影响5人杰哥长得帅

Redis 的数据库就是使用字典来作为底层实现的，对数据库的 curd 操作都时构建在对字典的操作之上。除了用来表示数据库外，字典还是哈希键的底层实现之一，当一个哈希键包含的键值对较多，又或者键值对中的元素都是比较长的字符串时，Redis 就会使用字典作为哈希键的底层实现

字典的实现

Redis 的字典使用哈希表作为底层实现，一个哈希表内可以又多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对

哈希表

一个空的哈希表

哈希表节点

其中 key 保存键，v 保存值，值可以时一个指针或者一个 uint64_t 或 int64_t 的整数。next 属性指向另一个哈希表节点，这个指针可将多个哈希值系统的键值对连接在一起，用来解决键冲突问题

关于 union：

union 中可以定义多个成员，union 的大小由最大的成员的大小决定
union 成员共享同一块大小的内存，一次只能使用其中的一个成员
对某一个成员赋值，会覆盖其他成员的值
联合体 union 的存放顺序是所有成员都从低地址开始存放的

连接在一起的键 K1 和键 K0

字典

ht 时一个包含两个哈希表的数组，一般情况下只会使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希表进行 rehash 时使用

rehashidx 记录了 rehash 目前的角度，如果不是正在进行 rehash，值为 -1

普通状态下（没有进行 rehash）的字典

哈希算法

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

具体方法如下：

// 使用字典设置的哈希函数，计算键 key 的哈希值
hash = dict -> type -> hashFunction(key);
// 使用哈希表的 sizemask 属性和哈希值，计算出索引值
// x 可以是 0 或 1
index = hash & dict -> ht[x].sizemask;

解决键冲突

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

因为 dictEntry 节点组成的链表没有指向表尾的指针，所以为了速度考虑，程序总是将新节点添加到链表的表头位置

rehash

为了让哈希表的负载因子维持在一个合理的范围内，当哈希表保存的键值对数量太多或者太少时，需要调整哈希表的大小

扩展和收缩哈希表的工作可以通过执行 rehash 来完成，步骤如下：

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

如果执行扩展，那么 ht[1] 的大小为第一个不小于 ht[0].used * 2 的 2^n
如果执行收缩，那么 ht[1] 的大小为第一个不小于 ht[0].used 的 2^n

将保存在 ht[0] 中的所有键值对 rehash 到 ht[1] 上
rehash 完成后，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

扩展或收缩哈希表需要将 ht[0] 里面的所有键值对 rehash 到 ht[1]，但并不是一次性、集中式地完成地，而是分多次、渐进式地完成

渐进式 rehash 详细步骤：

为 ht[1] 分配空间
将 rehashidx 设为 0，表示 rehash 开始
在 rehash 期间，每次对字典 curd 时，程序除了执行指定操作外，还会顺带将 ht[0] 在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成后，rehashidx + 1
随着字典操作不断执行，最终在某个时间点上，ht[0] 所有键值对都会被 rehash 至 ht[1]，这时把 rehashidx 值设为 -1，表示 rehash 完成

渐进式 rehash 地好处在于分而治之，将 rehash 键值所需的计算工作均摊到对字典的每个 curd 操作上，从而避免集中式 rehash 带来的庞大计算量

渐进式 rehash 执行期间的哈希表操作

在进行渐进式 rehash 的过程中，字典会同时使用 ht[0] 和 ht[1] 两个哈希表，所以在 rehash 进行期间，字典的 curd 操作会在两个哈希表上进行。例如，要在字典内查找一个键的话，程序会现在 ht[0] 查找，如果没找到，就会继续到 ht[1] 查找

另外，新添加到字典的键值对一律会被保存到 ht[1] 中，而 ht[0] 不再进行任何添加操作，这保证了 ht[0] 包含的键值对数量只减不增，最终变成空表