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

今天讲一道面试中区分度比较高的题：请你详细讲讲 Redis 中 hash 结构何时扩容（何时rehash）？

点击上方“后端开发技术”，选择“设为星标” ，优质资源及时送达

这道题已经超出了一般面试中只问到数据类型的层次，要求面试者阅读过 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);
}