面试题：Redis字典中哈希表的扩容机制是怎样在代码中体现的

Question

在Redis字典相关代码实现里，描述一下哈希表的扩容条件以及具体在代码层面是如何执行扩容操作的，例如涉及到哪些数据结构调整和函数调用。

Answer 1

哈希表扩容条件

1. 负载因子过高：负载因子 = 哈希表已保存节点数量 / 哈希表大小。当负载因子大于等于1，并且Redis没有在执行BGSAVE命令或者BGREWRITEAOF命令（也就是没有后台I/O操作在进行）时，会触发扩容。
2. 当执行BGREWRITEAOF命令或者BGSAVE命令时：如果负载因子大于等于5，也会触发扩容。

代码层面扩容操作

1. 数据结构调整：
   • 分配新的哈希表空间。新哈希表的大小是原哈希表大小的2倍，并且是大于等于原大小2倍的第一个2的幂次方数。例如原哈希表大小为4，新哈希表大小为8。
   • 原哈希表ht[0] 不变，新哈希表ht[1] 被分配空间。
   • 在扩容过程中，字典的rehashidx字段会从 -1变为0，表示开始进行rehash操作。
2. 函数调用：
   • dictExpand函数负责分配新的哈希表空间，并初始化相关参数。它会根据当前哈希表已保存节点数量，计算出合适的新哈希表大小并分配内存。
   • dictRehash函数负责逐步将原哈希表中的键值对迁移到新哈希表。在进行实际迁移时，每次迁移一个桶（bucket）中的所有节点。该函数会循环从ht[0] 中取出一个桶，将桶中的所有节点重新计算哈希值并插入到ht[1] 中合适的位置，然后将rehashidx加1，指向下一个要迁移的桶。迁移完成后，将ht[0] 释放，ht[1] 成为新的ht[0]，并将rehashidx重新设为 -1，表示rehash操作完成。