Redis字典dict要定义两个哈希表的原因

Redis 字典 dict 要定义两个哈希表的原因

Redis 字典 dict 定义两个哈希表是为了给哈希表进行扩展或者收缩准备的

为什么 Redis 字典 dict 中的哈希表要扩展或者收缩

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

Redis 字典 dict 如何实现哈希表的扩展和收缩

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

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

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

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

到此，对哈希表的扩张操作执行完毕，程序成功将哈希表的大小从原来的 4 扩展为 8

哈希表扩展和收缩的触发条件

哈希表扩展

当以下条件中的任意一个被满足时，程序和自动开始对哈希表执行扩展

服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1；
服务器目前正在执行 BGSAVE 或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5；

哈希表的收缩

当哈希表的负载因子小于 0.1 时，程序会自动开始对哈希表进行收缩

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

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

根据 BGSAVE 命令或者 BGREWRITEAOF 命令是否正在执行，服务器执行执行操作所需的负载因子并不相同，这是因为正在执行 BGSAVE 或者 BGREWRITEAOF 命令的过程中，Redis 需要创建当前服务进程的子进程，而大多数操作系统都采用写时复制技术来优化进程的使用效率，所以子进程存在的期间，服务器会提高执行扩展操作所需要的负载因子，从而尽量地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存