哈希表的优势

哈希表作为一种关键的数据结构应用非常普遍，比如在 Memcache 中，哈希表被用来作索引。而对于 Redis 来说，哈希表是键值对中的一种值类型，同时，Redis 也是用一个全局哈希表来保存所有的键值对，这样既能满足应用存取哈希型结构的数据需求，又能提供快速查询功能。

哈希表之所以应用这么广泛，主要原因是它以 O(1) 的时间复杂度快速查询数据，效率绝对是杠杠的。它的结构其实不难理解，但是有个问题，在实际应用的时候，随着数据量的不断增加，它的性能就容易受到哈希冲突和 rehash 开销这两个问题的影响。

针对哈希冲突，Redis 采用了链式hash。即以不扩容为前提，将具有相同哈希值的数据链接起来。而对于 rehash 开销，Redis 采用了渐进式 rehash 设计来缓解由于 rehash 操作带来的额外开销对操作性能的影响。
接下来，我们赶紧通过Redis源码讲解来聊一聊这两种方案是如何实现的把。

实现链式hash

首先得搞清楚一个问题，为何在数据量增加的时候会遭成哈希冲突？这对里面链式哈希非常重要。

一般来说哈希表就是一个数组，数组里的每个元素就是一个哈希桶（Bucket），第一个数组元素被编为哈希桶 0。所以，当一个键值对的键进行哈希计算后再对桶的数量取模就能得到该键值对在第几个哈希桶。

如下图，key1 经过哈希计算和哈希取模后对应桶 1，key3 对应桶 4。

上图中可以看到，需要写入哈希表的键空间一共有 16 个键，而哈希表的空间只有 8 个成员，这样就会导致有些键会对应到同一个桶中。

在实际应用，一般很难预估数量的大小，如果一开始就创建一个很大的哈希表，如果数据量较小时就容易遭成空间浪费。所以，我们通常会给哈希表设定一个初始大小，当数据量增大时，键空间的大小就会大于哈希表空间大小了。这就导致在用 hash 函数把键值映射到哈希表空间时，不可避免地会出现不同的键被映射到同一个位置上。而如果同一个位置只能保存一个键值对的就会遭成哈希冲突。

比如，key3 和 key100 都被映射到了哈希表的桶 3 中。当桶 3 只能保存一个 key 时，key3 和 key100 就会有一个无法保存到哈希表中。

那么，我们该如何解决哈希冲突呢？可以考虑使用以下两种解决方案：

• 链式哈希：解决了哈希冲突，但是链式哈希的链不能太长，否则会降低哈希表性能。
• 当链式哈希的链长达到一定长度时采用 rehash。不过 rehash 执行起来本身开销比较大，所以就需要渐进式 rehash 。

设计与实现链式 hash

所谓的链式哈希，就是用一个链表映射到哈希表的同一个桶中的键给链接起来。下面我们就来看看 Redis 是如何实现链式哈希的，以及为何链式hash能够帮助解决哈希冲突。Redis 中和实现hash相关的文件主要是在 dict.h 文件中定义，对哈希表的定义如下：

typedef struct dictht {
    //二维数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht

其中 dictEntry **table 是一个二维数组，这个数组的每个元素是一个指向哈希项（dictEntry）的指针。为了实现链式hash，在每个 dictEntry 结构中包含了另一个 dictEntry 结构体的指针*next，这里一看是不是觉得很熟悉，觉得和链表很像，它就是用来实现链式hash的。

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry

除此以外，这里还有一个值得注意的地方，就是在 dictEntry 结构体中，键值对的值是有一个联合体 v 。这个联合体 v 中包含了指向实际值的指针 *val，还包含了无符号 64 位整数、有符号的 64 位整数以及 double 类的值。

为什么这么实现，因为这么实现是一种节省内存的开发小技巧，因为当值为64位整数或双精度浮点数时，由于它们本身就是 64 位，就可以不用指针指向了。这样就可以避免了再用一个指针，从而节省了内存空间。

为什么链式hash可以解决冲突

刚才已经提到了 key5和 key100 都被映射到了桶 3 可以采用链式hash，桶 5就不会只保存 key5 或 key100，而是会用一个链表把 key5 和 key100 链接起来，当有更多的 key 被映射到桶 5时，这些 key 都可以被链表串联起来来应对哈希冲突。

这样，当要查询一个 key 时，可以先通过哈希函数计算，得到该 key 的哈希值被映射到的bucket中，然后再逐一比较 bucket 中串联的 key,直到查找到该键值。

但是，链式hash也有局限性。随着链表长度不断增加，哈希表在一个位置上查询哈希项的耗时也会增加，从而增加了哈希表整体查询时间，这样也导致了哈希表的性能下降。

那如何减少对哈希表性能的影响呢？不要着急，这就是接下来要介绍的 rehash。

实现 rehash

rehash 是什么？其实就是扩大哈希表空间。Redis 实现 rehash 的基本思路如下：
首先，Redis 准备了两个哈希表用来 rehash 时交替保存数据，Redis 在 dict.h 文件中使用 dictht 结构体定义了哈希表。在 dicht.h 文件中还定义了一个结构体 dict。代码如下：

 typedef struct dict {
    dictType *type;
    void *privdata;
    //两个哈希表，用来交替使用
    dictht ht[2]; 
    //哈希表是否在进行 rehash 的标识，-1 表示没有进行 rehash 
    long rehashidx;
    int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) */
} dict;

这个结构体中有一个结构体数组 ht[2]，它包含了两个哈希表 ht[0]、ht[1]：

• 正常服务阶段，所有的键值对都写入到 ht[0]中；
• 当进行 rehash 时，键值被迁移到扩容的 ht[1]中；
• 当迁移完成后，ht[0] 的空间将被释放，ht[1]赋给 ht[0]，ht[1] 表大小设置为 0。从而又回到了正常服务请求的阶段，ht[0]接收和服务请求，ht[1] 作为下一次 rehash 时的迁移表。如下图所示：

那么了解了 Redis 交替使用两个哈希表实现 rehash，下一步就需要解决以下几个问题了：

• 何时触发 rehash
• rehash 扩容扩多大
• rehash 如何执行

下面我们就通过代码来清晰地看下针对这三个问题 Redis 的设计思路。

什么时候触发 rehash

用来判断是否触发 rehash 的函数是 _dictExpandIfNeeded。下面我们先看看 _dictExpandIfNeeded 函数中进行扩容的触发条件，然后再看看它被哪些地方调用的。该函数的定义如下：

static int _dictExpandIfNeeded(dict *d)
{
    /* Incremental rehashing already in progress. Return. */
    if (dictIsRehashing(d)) return DICT_OK;

    /* If the hash table is empty expand it to the initial size. */
    //如果哈希表问空将其扩展为原始大小
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);

    /* 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. */
    //如果哈希表存取的元素个数超过其当前大小或者哈希表存取的元素已是当前大小的 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) &&
        dictTypeExpandAllowed(d))
    {
        return dictExpand(d, d->ht[0].used + 1);
    }
    return DICT_OK;
}

通过定义可以看到扩容条件满足下面三条：

• ht[0]的大小为 0；
• ht[0]的元素个数已经超过了 ht[0]的大小，而且哈希表是可以扩容的；
• ht[0]的元素个数是 ht[0]大小的 dict_force_resize_ratio 倍，其中 dict_force_resize_ratio 的定义如下：

static unsigned int dict_force_resize_ratio = 5

对于条件一来说，此时哈希表为空，所以 Redis 就需要将哈希表空间设置为初始大小，这其实并不属于 rehash 操作。

而条件二和三都对应了 rehash 的场景，都比较了哈希表当前存取的元素的元素个数（d->ht[0].used）和哈希表当前设定的大小（d->ht[0].size）。一般将这两个值的比值称为负载因子（loader factor）。Redis 判断是否需要进行 rehash 就是看负载因子是否大于 1 和是否大于 5。

实际上，当负载因子大于 5 时表明哈希表已经过载比较严重了，需要离开进行扩容。而当这个值大于 1 时，Redis 还会再判断 dict_can_size 这个变量。

咋又有个变量？那么这个值又是干啥的，其实，这个变量值是在 dictEnableResize 和 dictDisableResize 这两个函数中被调用，表示启用和禁用哈希表执行 rehash 功能，函数定义如下：

void dictEnableResize(void) {
    dict_can_resize = 1;
}

void dictDisableResize(void) {
    dict_can_resize = 0;
}

这两个函数又在 updateDictResizePolicy 函数中被调用，这个函数就是用来启动或禁用 rehash 扩容功能的，这个函数开启扩容功能的条件是当前没有 RDB 子进程或者 AOF 子进程，函数定义如下：

void updateDictResizePolicy(void) {
    if (!hasActiveChildProcess())
        dictEnableResize();
    else
        dictDisableResize();
}

接下来，我们接下来看下哪些函数调用 _dictExpandIfNeeded。可以发现 _dictExpandIfNeeded 是被 _dictKeyIndex 函数调用的，而 _dictKeyIndex 被 dictAddRaw 函数调用，而 dictAddRaw 函数被 dictReplace、dictAddorFind、dictAdd 这三个函数调用。

• dictAdd：往哈希表中添加一个键值对
• dictReplace：如果键值对存在，修改该键值对
• dictAddorFind：直接调用 dictAddRaw

所以，当我们向 Redis 中写入新的键值对或者修改键值对，Redis 都会判断是否需要进行 rehash。下图展示了 _dictExpandIfNeeded 的调用关系。

总结下来，Redis 触发 rehash 操作的关键就是 _dictExpandIfNeeded 函数和 updateDictResizePolicy 函数。_dictExpandIfNeeded 函数会根据哈希表的负载因子以及能否进行 rehash 的标识来判断是否进行 rehash，而 updateDictResizePolicy 函数会根据 RDB 和 AOF 的执行情况来启动或者禁用 rehash。

接下来，我们探讨第二个问题，rehash 扩容扩多大呢？

rehash 扩容

Redis 中，rehash 对哈希表空间的扩容是通过调用 dictExpand 函数来完成的。该函数有两个参数,一个是要扩容的哈希表的指针，另一个是要扩到的容量。下面是 dictExpand 函数的原型定义。

static int dictExpand(dict *ht, unsigned long size) {
    dict n; /* the new hashtable */
    unsigned long realsize = _dictNextPower(size), i;

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hashtable */
    if (ht->used > size)
        return DICT_ERR;

    _dictInit(&n, ht->type, ht->privdata);
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = hi_calloc(realsize,sizeof(dictEntry*));
    if (n.table == NULL)
        return DICT_ERR;

    /* Copy all the elements from the old to the new table:
     * note that if the old hash table is empty ht->size is zero,
     * so dictExpand just creates an hash table. */
    n.used = ht->used;
    for (i = 0; i < ht->size && ht->used > 0; i++) {
        dictEntry *he, *nextHe;

        if (ht->table[i] == NULL) continue;

        /* For each hash entry on this slot... */
        he = ht->table[i];
        while(he) {
            unsigned int h;

            nextHe = he->next;
            /* Get the new element index */
            h = dictHashKey(ht, he->key) & n.sizemask;
            he->next = n.table[h];
            n.table[h] = he;
            ht->used--;
            /* Pass to the next element */
            he = nextHe;
        }
    }
    assert(ht->used == 0);
    hi_free(ht->table);

    /* Remap the new hashtable in the old */
    *ht = n;
    return DICT_OK;
}

对于一个哈希表来说首先通过 _dictExpandIfNeeded 函数函数判断是否需要对其扩容，而一旦判断要扩容，Redis 在执行 rehash 操作时，对哈希表的扩容如果当前表的已经空间大小为 size，那么就将表扩容到 size*2 的大小。

在 dictExpand 函数中，主要由 _dictNextPower 函数完成，我们来看看这个函数的定义。

static unsigned long _dictNextPower(unsigned long size)
{
    unsigned long i = DICT_HT_INITIAL_SIZE;

    if (size >= LONG_MAX) return LONG_MAX + 1LU;
    while(1) {
        if (i >= size)
            return i;
        i *= 2;
    }
}

该函数定义了扩容操作，从哈希表的初始大小 DICT_HT_INITIAL_SIZE 不断乘 2 直到达到指定大小。

渐进式 rehash实现

首先，为什么要实现渐进式 rehash？因为哈希表在执行 rehash 的时候，由于哈希表空间扩大，原本映射到某一位置的键可能被映射到了一个新的位置，这样，很多键都需要从原来的位置拷贝到新的位置。而键拷贝会阻塞主线程，这样就会产生 rehash 开销。为了降低 rehash 的开销，Redis 提出了渐进式 rehash。

其实就是 Redis 并不会一次性把当前哈希表中的所有键都拷贝到新位置，而是采取分批拷贝。每次的键拷贝只拷贝哈希表中的一个 bucket 中的哈希项，这样可以减少对主线程的影响。渐进式 rehash 的代码又是如何实现的呢？先来看两个函数 dictRehash 和 _dictRehashStep。dictRehash 函数实际执行键拷贝。定义如下：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 0;

   //根据拷贝的 bucket 数量 n，循环 n 次后或者 ht[0]被移植完成后退出循环
    while(n-- && d->ht[0].used != 0) {
        dictEntry *de, *nextde;

        /* Note that rehashidx can't overflow as we are sure there are more
         * elements because ht[0].used != 0 */
        assert(d->ht[0].size > (unsigned long)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL) {
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        //获得 bucket 的哈希项指针
        de = d->ht[0].table[d->rehashidx];
        /* Move all the keys in this bucket from the old to the new hash HT */
       //如果 rehashidx 指向的 bucket 不为空
        while(de) {
            uint64_t h;
            //获得同一个 bucket 中的下一个哈希项
            nextde = de->next;
            /* Get the index in the new hash table */
            //根据扩容后的 ht[1]的大小计算当前哈希项在扩容后的哈希表中的 bucket 位置
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            d->ht[1].table[h] = de;
            //当前哈希表的哈希项个数减 1
            d->ht[0].used--;
            d->ht[1].used++;
            //指向下一个哈希项
            de = nextde;
        }
        //如果当前 bucket 已经没有哈希项了，将 bucket 设为 NULL
        d->ht[0].table[d->rehashidx] = NULL;
        //访问下一个 bucket
        d->rehashidx++;
    }

    /* Check if we already rehashed the whole table... */
    //判断 ht[0]是否迁移完成
    if (d->ht[0].used == 0) {
        释放 ht[0]的空间
        zfree(d->ht[0].table);
        //ht[1]赋值给 ht[0]
        d->ht[0] = d->ht[1];
        //ht[1]被重置
        _dictReset(&d->ht[1]);
        //rehashidx 被标识为-1 表示 rehash 结束
        d->rehashidx = -1;
        return 0;
    }

    /* More to rehash... */
    //ht[0]中仍然有元素没有迁移完成
    return 1;
}

它的输入参数有两个，第一个参数是全局哈希表，前面介绍过它包含了 ht[0] 和 ht[1]，第二个参数是需要进行键拷贝的 bucket 数量。

代码主要包括两部分，首先执行一个循环，根据要拷贝的 bucket 数量 n，依次完成这些 bucket 内部所有键的迁移。如果 ht[0] 哈希表已经迁移完成，键拷贝循环也将停止。当完成了 n 个 bucket 拷贝后。主要就是判断 ht[0] 中的数据是否已经迁移完，如果都迁移完了，那么释放掉 ht[0] 的空间，虽然数据都在 ht[1] 中了，但是由于 Redis 处理请求时都是使用 ht[0]，所以仍然需要把 ht[1] 的数据赋值给 ht[0]。赋值完成后，ht[1] 的大小被重置为 0 并等待下一次 rehash。最后 rehashidx 变量被设置为 -1 表示 rehash 结束了。

那么，渐进式 rehash 如何根据 bucket 进行迁移的呢？基于 rehashidx 来对 bucket 做数据迁移，比如当 rehashidx 值为 0 表示对 ht[0] 中的第一个 bucket 进行迁移，当 rehashidx 值为 1 时表示对 ht[0] 中的第二个 bucket 进行数据迁移。在 dicthash 函数的第一个主循环中，首先判断 rehashidx 指向的 bucket 是否为空，如果为空那么就将 rehashidx 的值加 1 并检查下一个 bucket。

dicthash 函数的逻辑如下图所示：

现在问题又来了，有没有可能连续几个 bucket 都为空呢？其实是有可能的，这时候 rehashidx 不断递增会遭成 Redis 主线程无法执行其它请求。

所以 dictrehash 函数中还设置了一个变量 empty_visits，通过字面看就能猜到它表示已经检查的空 bucket 数量，当检查了一定数量的空 bucket 后，这一轮的 rehash 就停止执行转而继续执行外部请求从而避免了 Redis 性能下降。

而 rehashidx 指向的 bucket 有数据可以迁移，Redis 就会把这个 bucket 中的的哈希项依次取出来，根据 ht[1]的表空间大小重新计算哈希项在 ht[1]中应该在哪个 bucket，然后把这个哈希项赋值到扩容的 ht[1]对应 bucket 中。如果当前 rehashidx 指向的 bucket 中数据都迁移完了，rehashidx 就会递增加 1 指向下一个 bucket。