redis 系列6 数据结构之字典(下)

一.概述

接着上篇继续，这篇把数据结构之字典学习完， 这篇知识点包括：哈希算法，解决键冲突， rehash , 渐进式rehash,字典API。

1.1 哈希算法

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

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

例1： 将一个“键值对”K0和V0 添加到字典里面，那么程序会使用如下语句，假设hash变量的哈希值为8, sizemask为3, &是指"按位与"运算符。公式如下：

hash = dict -> type->hashFunction(K0);
index= hash $ dict ->ht[0]. sizemask=8 &3 = 0;

通过公式计算出健K0的索引值为0，这个新的“键值对”节点应该放置到哈希表数组的索引0位置，对于哈希算法的底层实现，redis使用MurmurHash2算法来计算键的哈希值。Murmur哈希是一种非加密散列函数，目前有三个版本(MurmurHash1、MurmurHash2、MurmurHash3),这里不在深入，例1如下图所示：

1.2 解决键冲突

当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，称为键冲突。Redis 的哈希表使用“链地址”来解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，被分配到哈希表数组同一个索引上，用单向链表把多个节点连接一起，解决了键冲突问题。

例2： 程序要将新"键值对"k2和v2 添加到哈希表中，计算的k2 索引值为2, 但该哈希表数组索引值2上已有"键值对"k1和v1。 解决键索引冲突的办法就是使用next指针将键k2和键k1的节点连接起来，如下图所示：

1.3 rehash 重新散列

随着对哈希表数组的不断操作， 哈希表数组保存的"键值对"节点会增多或减少，为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的“键值对”数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或收缩。扩展或收缩哈希表的工作是通过执行rehash 操作来完成的，Redis字典的哈希表执行reash的步骤如下：

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

(2) 将保存在ht[0]中的所有“键值对”rehash到ht[1]上面， rehash指的是重新计算键的哈希值和索引值，然后“键值对”放置到ht[1]哈希表的指定位置上。

(3) 当ht[0]包含的所有“键值对”都迁移到了ht[1]之后,释放ht[0], 将ht[1]设置为ht[0],并在ht[1]新创建一个空白的哈希表，为下一次rehash准备。

例3： 下面是对ht[0]进行扩展操作，在没有rehash之前，字典如下所示

ht[0].used当前的值为4(扩展公式为ht[0].used *2,  2^3次方), 程序会将ht[1]哈希表的大小设置为8,ht[1]在分配空间之后，字典如下所示：

将ht[0]包含的四个“键值对”都rehash到ht[1]，此时释放了ht[0]的哈希表，如下图所示：

最后将ht[1] 设置为ht[0], 然后为ht[1]分配一个空白哈希表，至此，对哈希表的扩展操作执行完毕，程序成功将哈希表的大小从原来的4改为了现在的8，如下图所示：

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

(1) 服务器目前没有在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于1。

(2) 服务器目前正在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于5。

#负载因子= 哈希表已保存节点数量 / 哈希表大小
load_factor=ht[0].used /ht[0].size

例如：对于一个大小为4,包含4个“键值对”的哈希表来说，这个哈希表的负载因子为: load_factor= 4/4=1。 又例如，对于一个大小为512，包含256个“键值对“的哈希表来说，这个哈希表的负载因子为: load_factor=256/512=0.5(这个要不需要扩展)。另外当哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作。

1.4 渐进式 rehash

上面rehash扩展或收缩哈希表需要将ht[0] 里面的所有”键值对“ rehash到ht[1]里面， 这个rehash动作并不是一次性，集中式完成的，而是分多次，渐进式完成的。这样做原因在于考虑到有大量”键值对“，如果一次性将大量”键值对“全部rehash到ht[1]的话，庞大的计算量可能会导致服务器在一段时间内停止服务。因此是渐进式的将ht[0]里面的键值对慢慢地rehash到ht[1]。

例4 以下是哈希表渐进式rehash的详细步骤：

(1) 为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。此时rehashidx值为-1。

(2) 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0,表示rehash工作正式开始(rehash了一个键值对)。此时rehashidx值为0。

(3) 在每次rehash进行期间，除了对字典执行操作，程序还会将ht[0]的rehashidx索引值增一，下图是全部rehash完成，此时rehashidx值为3。

(4) 最后当ht[0]的所有键值对rehash到ht[1]，此时程序将rehashidx属性的值为-1, 表示rehash操作全部完成。将ht[1]设置为ht[0],并在ht[1]新创建一个空白的哈希表，为下一次rehash准备

总结： 在渐进式 rehash执行期间，新添加到字典的键值对 一律会被保存到ht[1]里面，而ht[0]则不再进行任何添加操作，这一措施保证了ht[0]包含的键值对数量只减不增，并随着rehash操作的执行最终变成空表。

1.5 字典API (主要操作API)

最后字典总结：

(1) 字典被广泛用于实现 Redis 的各种功能，其中包括数据库和哈希键。

(2) Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个在rehash时使用。

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

(4) 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个“键值对”会连接成一个单向链表。

(5) 在对哈希表扩展或收缩操作时，程序需要将现有哈希表包含的所有“键值对”rehash到新哈希表里面，并且这个rehash过程并不是一次性完成的，而是渐近式完成。