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 做准备