Redis数据结构之字典 (2)

回到正题，现在当一个键值对添加到字典中，会先计算出当前键值对需要存储在 table 中的 index，计算分两步，先根据键计算hash值，再根据hash值和掩码计算index

hash = dict->type->hashFunction(key); //根据键计算其hash值 //根据hash值和掩码计算索引，ht[x]可能会是h[0]，也可能是h[1]，根据rehash来定 index = hash & dict->ht[x].sizemask;

首先，对于不同的key，这里计算的hash值可能相同，其次，不同的hash值经过和掩码取&，会出现相同的index，这也是使用链表的原因，在 Redis 中称之为键发生了冲突（collision）

我们前面说到，sizemask 总是 size - 1，即数组的最大索引，hash & sizemask 就保证得出的 index一定是一个小于等于 sizemask 的值，即一定在数组内

计算错 index 之后，就把该键值对保存到 table 对应的位置，table 的元素都是链表，新插入的键值对，会保存在链表的最前端，这样效率最高，时间复杂度为 O(1)，如果保存在最后端，那么时间复杂度为O(N)。反正放在最前端和最后端都一样，就取一个插入最快的吧。

这样存储完成之后，我们取数据也就是要在数组和链表中取，时间复杂度也就是 O(1) + O(N)，这里的N越小越好，即链表越小越好，最好没有键冲突，那么时间复杂度就是O(1)

3.3、rehash

rehash 即对hash表进行扩展和收缩。

这个操作是非常又必要的，可以想象一下，假设一开始创建的 dictEntry 数组的大小只有100个，结果随着时间的推移，保存的键值对慢慢变多，变成五六百个，那么，键冲突的概率就会成倍地增加，最后就会导致个别数组内的链表元素有多个，这样就大大地增加了读取的效率，此时就很有必要对原先只有100个元素的数组进行拓展，比如扩展成五六百个，尽量保证，链表节点的数量最小。同理，当保存的键值对删减之后，缩小数组可以节约内存，反正空着也是空着，不如释放了。

提到hash，就不得不提负载因子（load factor）的概念，它是保存的键值对和数组大小的一个比值，使用扩展和收缩的手段，把它控制在一个合理的范围之内，可以避免内存的浪费和读取的低效

负载因子的计算公式如下：

load_factor = ht[0].used / ht[0].size

used 是保存的的键值对的数目，size 是数组的大小

可见，如果负载因子太大，表示数组中的元素的链表元素会多，即键冲突的概率会变大；

而如果负载因子太小，表示数组中可能有些元素没有使用，即有些内存浪费了；

哈希表的收缩和扩展：

Redis 中，当满足下面两个条件之一时，会自动进行扩展操作：

当服务器没有执行 BGSAVE 和 BGREWRITEAOF 命令，并且负载因子大于等于1的时候；

当服务器正在执行 BGSAVE 和 BGREWRITEAOF 命令，并且负载因子大于等于5的时候；

这是因为这两个命令在执行过程中，Redis 需要创建子进程，而大多数的操作系统都采用写时复制的技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高触发扩展所需的负载因子，尽可能避免在子进程存在期间进行扩展操作，最大限度地节约内存。

当 Redis 进行 rehash 这种操作的时候，客户端还在使用，要兼顾 rehash 和 客户端，就要保证原数据和新数据同时存储和查询。这就是 dict 结构中 ht 大小为2的原因。

在没有进行 rehash 的时候，只使用 ht[0]，rehash 会将新旧数据都重新散列，存入 ht[1] 中。rehash 完成之后，将 ht[1] 变成 ht[0]，原来的 ht[0] 释放掉，再新建一个 ht[1]

3.4、渐进式rehash

当数据量很大的时候，rehash 操作如果一次性将h[0]数据转到ht[1]，会导致服务宕机，这是不能接受的。因此，Redis 的 rehash 操作并不是一次性、集中式地完成，而是分多次、渐进式地完成的。

大致步骤如下：

为 ht[1] 分配空间，，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；

将 rehashindex 值设置为0，表示开始 rehash；

在 rehash 期间，每次对字典执行增删查改的操作时，程序还会顺带将 ht[0] 中哈希表在 rehashindex 上的所有键值对 rehash 到 ht[1] 上，完成只有，rehashindex 递增；

随着字典的操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被rehash至 ht[1]，这时候，rehash 全部完成，将 rehashindex 设置为-1；

渐进式 rehash 的好处在于，其采用分治的方式，将 rehash 键值对的工作量均摊到每次对字典的增删查改上，避免了集中式 rehash 带来的庞大的计算量

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