5分钟搞定，Redis的哈希表何时扩容？

这道题已经超出了一般面试中只问到数据类型的层次，要求面试者阅读过 Redis 源码，并且深入探究过 Hash 编码的扩容过程。

哈希表

在 Redis 中，哈希数据类型的底层实现是hash表、压缩列表，在未来 6.2以后 listpack 也会作为其底层实现，在这里我们只对 hash 表做探究。

Hash 表应用如此广泛的一个重要原因，就是从理论上来说它能以 O(1) 的复杂度快速查询数据。Hash 表通过 Hash 函数的计算，就能定位数据在表中的位置，这就产生一个问题，hash 函数计算的结果冲突怎么办？

Redis 为我们提供了一个经典的 Hash 表实现方案。针对哈希冲突，Redis 采用了链式哈希，在不扩容哈希表的前提下，将具有相同哈希值的数据链接起来，以便这些数据在表中仍然可以被查询到。

但是这样又有一个问题。Hash 表冲突过多导致查询效率变低怎么办？这就需要扩容来减少冲突，对于旧数据的迁移就需要 rehash。对于 rehash 开销，Redis 实现了渐进式 rehash 设计，进而缓解了 rehash 操作带来的额外开销对系统的性能影响。

关于渐进式 rehash 以后有机会再讲，这次只说什么节点会去 rehash。

扩容时机

话不多说，直接怼源码。

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2]; //两个Hash表，交替使用，用于rehash操作
    long rehashidx; /* //Hash表是否在进行rehash的标识，-1表示没有进行rehash 。rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;
_______________________
//如果Hash表为空，将Hash表扩为初始大小
if (d->ht[0].size == 0) 
   return dictExpand(d, DICT_HT_INITIAL_SIZE);
 
//如果Hash表承载的元素个数超过其当前大小，并且可以进行扩容，或者Hash表承载的元素个数已是当前大小的5倍
if (d->ht[0].used >= d->ht[0].size &&(dict_can_resize ||
              d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
    return dictExpand(d, d->ht[0].used*2);
}

情况一：在 Redis 中，hash表底层结构是一个大小为2的数组，渐进rehash的时候，是ht[0] 中的数据不断往 ht[1] 迁移。从上面源码可以看出，dictExpand()是扩容函数，在添加或者修改元素的过程中，如果发现此时hash表大小为0，会进行第一次扩容。

情况二：如果数组大小大于0，当发现数据的元素个数已经超过hash表容量，并且当前状态可以扩容，会进行rehash。

情况三：如果数组大小大于0，并且发现数据的元素个数已经超过hash表容量，但是当前状态不可以扩容，则不进行rehash。如果此时hash表承载的元素个数，是其大小的 5 倍（dict_force_resize_ratio默认等于5），则强制进行扩容。

这里介绍一下，dict_can_resize= true，表示当前没有 RDB 子进程，并且也没有 AOF 子进程。简言之，redis当前没有进行持久化操作。

一旦判断要扩容，Redis 在执行 rehash 操作时，对 Hash 表扩容的思路也很简单，就是如果当前表的已用空间大小为 size，那么就将表扩容到 size*2 的大小。