由于 Redis 的 dict 数据结构通过链表地址法来解决哈希冲突的问题，久而久之，当一个字典中出现冲突的键值对过多的时候，就会造成字典“负载过重”的问题：平均每个哈希节点上挂载的键值对过多。

由于链表的查询复杂度是O(N)，当单个hash节点挂载的键值对过多时候，就可能造成整个字典查询读写性能降低，这时候，就需要重新对每个字典节点上负载的键值对重新计算哈希，再重新均匀地排列到新的哈希表上，这个过程就是字典的rehash过程。

同样的，如果哈希表中单个空置的哈希节点如果过多，说明字典结构浪费了太多内存空间，这时候就同样需要通过对字典进行 rehash 来缩短哈希表的长度，从而达到高效利用内存的目的。

rehash 扩展的条件

当需要像哈希表中插入新的节点时候，就需要扩展字典的空间，查看 redis 源码中的对字典进行插入操作时候的逻辑 https://github.com/redis/redis/blob/7.2.4/src/dict.c#L1442：

void *dictFindPositionForInsert(dict *d, const void *key, dictEntry **existing) {
    ...
    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return NULL;
    ...
}

在对字典结构增加新节点之前，首先调用了_dictExpandIfNeeded，这个函数用来判断当前字典是否需要 rehash ：

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{
    ···
    /* If we reached the 1:1 ratio, and we are allowed to resize the hash
     * table (global setting) or we should avoid it but the ratio between
     * elements/buckets is over the "safe" threshold, we resize doubling
     * the number of buckets. */
    if ((dict_can_resize == DICT_RESIZE_ENABLE &&
         d->ht_used[0] >= DICTHT_SIZE(d->ht_size_exp[0])) ||
        (dict_can_resize != DICT_RESIZE_FORBID &&
         d->ht_used[0] / DICTHT_SIZE(d->ht_size_exp[0]) > dict_force_resize_ratio))
    {
        ...
        return dictExpand(d, d->ht_used[0] + 1);
    }
    ···
}

这里涉及到两个全局定义的值：

static dictResizeEnable dict_can_resize = DICT_RESIZE_ENABLE;
static unsigned int dict_force_resize_ratio = 5;

dictResizeEnable 是个枚举类型：

typedef enum {
    DICT_RESIZE_ENABLE,
    DICT_RESIZE_AVOID,
    DICT_RESIZE_FORBID,
} dictResizeEnable;

分别代表三种对字典扩容的配置：开启扩容、尽量避免扩容和禁止扩容，其中DICT_RESIZE_AVOID可以被其他比较耗时的命令（如 SAVE 和 BGSAVE）设置未启用状态，意思是尽量避免字典扩容，除非负载达到了一个较高的阈值（即dict_force_resize_ratio）。

综上来看，redis 触发 rehash 扩容的条件有两个：

• 全局配置允许正常扩容时，哈希表 used >= size （即负载因子： used / size >= 1）;
• 全局配置为尽量避免扩容时候，负载因子 used / size >= dict_force_resize_ratio （默认阈值配置为5）

以上两个条件只要满足其一，就会触发字典的 rehash 扩充哈希表的过程。

rehash 收缩的条件

redis 对 hash 键执行 hdel 命令时候，底层会执行到代码：

/* Delete an element from a hash.
 * Return 1 on deleted and 0 on not found. */
int hashTypeDelete(robj *o, sds field) {
    ...
    if (htNeedsResize(o->ptr)) dictResize(o->ptr);
    ...
}

这里htNeedsResize就是用来判断删除元素后字典是否需要收缩的函数：

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

dictSlots() 和 dictSize() 定义：

#define dictSlots(d) (DICTHT_SIZE((d)->ht_size_exp[0])+DICTHT_SIZE((d)->ht_size_exp[1]))
#define dictSize(d) ((d)->ht_used[0]+(d)->ht_used[1])

说明dictSlots()获取了字典持有的两张哈希表的 size 之和，dictSize() 得到了字典中两张哈希表的 used 部分之和。

再看看两个常量的定义：

/* This is the initial size of every hash table */
#define DICT_HT_INITIAL_EXP      2
#define DICT_HT_INITIAL_SIZE     (1<<(DICT_HT_INITIAL_EXP))
···
/* Hash table parameters */
#define HASHTABLE_MIN_FILL        10      /* Minimal hash table fill 10% */

根据注释了解到 DICT_HT_INITIAL_SIZE 是每个哈希表的最小尺寸，即哈希表及时收缩到最小也不能低于这个值。HASHTABLE_MIN_FILL 代表理想中每个哈希表的“填充度”不能低于10%。

填充度的计算原理：

(ht[0]->used + ht[1]->used)) / (ht[0]->size + ht[1]->size) 

可以看出这里的填充度其实和字典扩充时候的"负载因子"有一定相似性。

综合上面分析的结果，可以得出字典哈希表收缩时候必须同时满足两个条件：

• 当前使用的哈希表的长度不低于哈希表最小长度；
• 当前字典持有的两张哈希表的“总负载因子”（total_used / total_size）小于10%；

渐进式 rehash

字典哈希表扩展或者收缩时候的rehash过程并不是一次性完成的，由于rehash会涉及到大量的键值对重新计算hash，这个过程会占用大量的CPU，因此redis通过记录每次执行rehash的索引点（字典结构中的dict->rehashidx）,将rehash的过程分散到每次执行不同的hash键的命令上。

继续来查看代码，当对字典进行扩充时候，一单满足了前述的rehash条件，代码就会执行函数_dictExpand()来开启 rehash 过程：

/* Expand or create the hash table,
 * when malloc_failed is non-NULL, it'll avoid panic if malloc fails (in which case it'll be set to 1).
 * Returns DICT_OK if expand was performed, and DICT_ERR if skipped. */
int _dictExpand(dict *d, unsigned long size, int* malloc_failed){
    ···
    /* Prepare a second hash table for incremental rehashing */
    d->ht_size_exp[1] = new_ht_size_exp;
    d->ht_used[1] = new_ht_used;
    d->ht_table[1] = new_ht_table;
    d->rehashidx = 0;
    return DICT_OK;
}

可以看到这个函数只是对字典做了一堆分配内存和其他判断的逻辑，最后只是设置了d->rehashidx = 0就认为当前字典的扩容任务已经“开启”。

真正逐步执行rehash的逻辑分布在其他hash键相关的命令中，以hget命令为例，执行这个命令时候，代码最终会执行dictFind()函数来查找需要的键值对：

dictEntry *dictFind(dict *d, const void *key)
{
    ...
    if (dictIsRehashing(d)) _dictRehashStep(d);
    ...
}

可见程序在真正查找字典数据之前，首先判断了当前字典是否开启了rehash过程(dict->rehashidx != -1)，进入条件就通过_dictRehashStep() 来执行一部分rehash的任务：

static void _dictRehashStep(dict *d) {
    if (d->pauserehash == 0) dictRehash(d,1);
}

...

int dictRehash(dict *d, int n) {
        int empty_visits = n*10; /* Max number of empty buckets to visit. */
    unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);
    unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);
    if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;
    if (dict_can_resize == DICT_RESIZE_AVOID && 
        ((s1 > s0 && s1 / s0 < dict_force_resize_ratio) ||
         (s1 < s0 && s0 / s1 < dict_force_resize_ratio)))
    {
        return 0;
    }

    while(n-- && d->ht_used[0] != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);
        while(d->ht_table[0][d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        de = d->ht_table[0][d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {
            uint64_t h;

            nextde = dictGetNext(de);
            void *key = dictGetKey(de);
            /* Get the index in the new hash table */
            if (d->ht_size_exp[1] > d->ht_size_exp[0]) {
                h = dictHashKey(d, key) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            } else {
                /* We're shrinking the table. The tables sizes are powers of
                 * two, so we simply mask the bucket index in the larger table
                 * to get the bucket index in the smaller table. */
                h = d->rehashidx & DICTHT_SIZE_MASK(d->ht_size_exp[1]);
            }
            if (d->type->no_value) {
                if (d->type->keys_are_odd && !d->ht_table[1][h]) {
                    /* Destination bucket is empty and we can store the key
                     * directly without an allocated entry. Free the old entry
                     * if it's an allocated entry.
                     *
                     * TODO: Add a flag 'keys_are_even' and if set, we can use
                     * this optimization for these dicts too. We can set the LSB
                     * bit when stored as a dict entry and clear it again when
                     * we need the key back. */
                    assert(entryIsKey(key));
                    if (!entryIsKey(de)) zfree(decodeMaskedPtr(de));
                    de = key;
                } else if (entryIsKey(de)) {
                    /* We don't have an allocated entry but we need one. */
                    de = createEntryNoValue(key, d->ht_table[1][h]);
                } else {
                    /* Just move the existing entry to the destination table and
                     * update the 'next' field. */
                    assert(entryIsNoValue(de));
                    dictSetNext(de, d->ht_table[1][h]);
                }
            } else {
                dictSetNext(de, d->ht_table[1][h]);
            }
            d->ht_table[1][h] = de;
            d->ht_used[0]--;
            d->ht_used[1]++;
            de = nextde;
        }
        d->ht_table[0][d->rehashidx] = NULL;
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht_used[0] == 0) {
        zfree(d->ht_table[0]);
        /* Copy the new ht onto the old one */
        d->ht_table[0] = d->ht_table[1];
        d->ht_used[0] = d->ht_used[1];
        d->ht_size_exp[0] = d->ht_size_exp[1];
        _dictReset(d, 1);
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    return 1;
}

代码逻辑大致可以分为一下步骤分析：

• 首先对 rehash 条件做了安全判断，防止不该触发 rehash 的情况下调用了这个执行 rehash 的函数；

• 通过 int empty_visits = n*10 跳过了一些空节点；

• 每次对旧哈希表（ht[0]）上 rehashidx 指向的哈希节点上的所有键值根据新的哈希表（ht[1]）长度对重新计算新的索引值，并填入新哈希表的对应节点。每次重复执行n个旧哈希节点后停止，进入下一步判断；

• 如果上述步骤执行完成后发现旧表已经没有被使用的哈希节点了，则认为整个字典的 rehash 过程完成了，则会把新哈希表设置未ht[0],旧表设为ht[1]，重置 rehashidx 为 -1 (表示不需要再执行 rehash 任务了)；

• 如果没有完成 rehash 的任务，同样会直接返回，等到后续其他命令继续重新执行 rehash 的过程，直至整个 rehash 任务完毕。