Redis ReHash 原理

在 Redis 的数据结构(一)，有提到 Redis 的 dict 结构中，有两个 dictEntry 的数组

之前只是提到，它是作为 rehash 时使用的，那为什么需要 rehash 呢？

Redis 是作为一个字典表存在的，它是基于 hash 表进行查找数据的

那它的查找方式基于以下的步骤

1. 通过 hash 算法，获取在当前 hash 表中的位置，时间复杂度 O(1)

2. 如果有 hash 冲突，则遍历当前的位置的各个 dictEntry，比对相应的值,时间复杂度为 O(N)

为什么会有 O(N)的出现呢，因为 hash 算法会存在 hash 碰撞，当出现 hash 碰撞时，redis 通过使用链表的方式来存储对应的键值，如果熟悉 Java 中的 HashMap 的算法，其中的原理是类似的。

那要解决的问题，主要是尽量使 hash 碰撞的概率减小，解决方案便是进行 hash 表的扩容。而上面提到的两个 ht_table 表就是为了在扩容或是缩容时使用的。来看下具体的源码

1. rehash 的过程是从 ht_table[0]中，按索引的位置，将该 bucket 中的列表逐个迁移到 ht_table[1]中，这也是为了防止在迁移过程中长时间的阻塞导致 redis 不可用，并不是一次性进行迁移的，而是渐进式的

2. 更新 ht_table[0] 的 rehashidx 的值

3. 在 ht_table[0]迁移完成后，会释放 ht_table[0]，同时重新将 ht_table[1] 设置为 ht_table[0]

既然在 rehash 的过程，会将数据分散在两个表中，那在查找、新增、删除时是如何处理呢？来看下获取对应 key 的过程

这里会分别在两个 ht_table 中进行查找。

而新增呢？

从以上逻辑可以知道，当在插入时，只会插入到 ht_table[1]中。

既然 rehash 是为了解决 hash 冲突的问题，那什么时候会触发呢？

在上面的流程里，有调用 _dictExpandIfNeeded 方法

这里可以总结下扩容的时机点：

1. 未初始化，会进行初始化第一个 ht_table

2. 当 key 的总数大于 hashtable 的大小，接近 1:1 时，并且 dict_can_resize 为 1 或是 负载因子大于 5 时

3. 扩容规则是找到大于当前 key 的总数的最小 2 的指数倍

4. 扩容以后，会将 dict 中的 rehashidx 的值会被置为 0

扩容以后，后台线程(1 秒钟执行 10 次)检查是否在扩容后，需要 rehash，如果需要，则会调用以下的方法

或是新增、删除 key 时判断是需要 rehash,之后会调用 _dictRehashStep 进行迁移一个 bucket

总结

Redis 的 rehash 是为了解决 hash 冲突带来的性能问题，将原来紧凑的数据分布，进行松散分布，可以使 key 的查找尽可能达到 O(1)