趁着年轻

字典和hash表的实现都大同小异，所以简单说一下不同点。

0.概要

redis的字典是使用hash表实现的，相同hash值的key保存在list中，也就是index= hash(key)， index代表了key所在的数组下标，也就是槽位。查找操作找到槽位后，需要遍历下面的链表的元素去查找对应的key。插入操作将新key插入到链表的头部。

1.rehash调整大小操作：

redis会在适当的时候自动的调整hash表的大小，自然想到，比如链表太长了，那么就需要调整大小了，代码中_dictExpandIfNeeded参与了自动调整大小的操作。

当每个槽位的平均容积大于1:1 或者大于配置的dict_force_resize_ratio（默认是5:1,由dict_can_resize开关控制）,那么redis就会将hash表的大小加倍。具体看下面代码：

/* Expand the hash table if needed */
static int _dictExpandIfNeeded(dict *d)
{//超过1:１或者配置了RESIZE比例，那么就重整一下HASH表，设置大小为2倍、
    /* 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. */
    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].size > d->ht[0].used) ? d->ht[0].size : d->ht[0].used)*2);
    }
    return DICT_OK;
}

dictExpand函数出发了rehash的操作，也就说，我们这里加大了hash表的大小，自然也就设及到需要将老的hash表里面的所有数据，重新填入新的hash表里面去。
redis是使用双hash表的机制来实现这个的。d->ht[0]是常规的hash表，d->ht[1]使用来rehash的时候的新空间，当d->ht[0]的数据全部拷贝到d->ht[1]里面后，redis将切换指针指向。下面看下dictExpand代码。

/* Expand or create the hash table */
int dictExpand(dict *d, unsigned long size)
{//新建一个dictht元素，分配内存，然后设置到d->ht[1] = n;上面，当做新的哈希表
    dictht n; /* the new hash table */
    unsigned long realsize = _dictNextPower(size);//向上取整，求2^n

    /* the size is invalid if it is smaller than the number of
     * elements already inside the hash table */
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    /* Allocate the new hash table and initialize all pointers to NULL */
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;

    /* Is this the first initialization? If so it's not really a rehashing
     * we just set the first hash table so that it can accept keys. */
    if (d->ht[0].table == NULL) {
        d->ht[0] = n;
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

2.平摊rehash操作的代价：

我们知道，redis里面肯定存有大量数据，一次重新调整的代价不可小觑，如果阻塞的进行一次全部拷贝，势必造成redis的卡死。

redis是采用巧妙的方法将这个代价平摊到每次查询等操作上来的。

比如serverCron后台定时任务会每次调用databasesCron()进而调用incrementallyRehash，后者每次处理一个数据库。在需要的时候，会调用dictRehashMilliseconds去做1毫秒钟的rehash操作。

int incrementallyRehash(int dbid) {
//databasesCron调用这里，做一毫秒的增量rehash
    /* Keys dictionary */
    if (dictIsRehashing(server.db[dbid].dict)) {
        dictRehashMilliseconds(server.db[dbid].dict,1);
        return 1; /* already used our millisecond for this loop... */
    }
    /* Expires */
    if (dictIsRehashing(server.db[dbid].expires)) {
        dictRehashMilliseconds(server.db[dbid].expires,1);
        return 1; /* already used our millisecond for this loop... */
    }
    return 0;
}
int dictRehashMilliseconds(dict *d, int ms) {
//做ms毫秒的hash重整迁移操作。每次迁移100个槽位的数据。
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {//每次整理100个
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;
    }
    return rehashes;
}

从这里可以看到，redis会在后台慢慢的，每次用1毫秒的时间去做rehash操作，虽然生硬，但有效。
另外，也会在每次查询的时候平摊这个动作。

比如每次查找某个key的时候，调用dictFind，后者会在需要的时候顺便做一下rehash的操作。类似的还有dictGenericDelete，dictAddRaw等函数调用的时候。

dictEntry *dictFind(dict *d, const void *key)
{//根据key查找hash表里面的ht0或者ht1,返回对应的元素dictEntry结构
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].size == 0) return NULL; /* We don't have a table at all */
    if (dictIsRehashing(d)) _dictRehashStep(d);
//``````
}
/* This function performs just a step of rehashing, and only if there are
 * no safe iterators bound to our hash table. When we have iterators in the
 * middle of a rehashing we can't mess with the two hash tables otherwise
 * some element can be missed or duplicated.
 *
 * This function is called by common lookup or update operations in the
 * dictionary so that the hash table automatically migrates from H1 to H2
 * while it is actively used. */
static void _dictRehashStep(dict *d) {//用于正的查找和更新的时候，顺便调用一下这个用来调整hash表。
    if (d->iterators == 0) dictRehash(d,1);
}

附带看一下调整操作的代码，基本就是找到下一个要调整的槽位，将其链表一个个拷贝到新的 d->ht[1].table中。

int dictRehash(dict *d, int n) {
    if (!dictIsRehashing(d)) return 0;

    while(n--) {
        dictEntry *de, *nextde;

        /* Check if we already rehashed the whole table... */
        if (d->ht[0].used == 0) {//第0个哈希表已经没有有效的表项了，那就OK了，释放内存吧。
            zfree(d->ht[0].table);//释放内存
            d->ht[0] = d->ht[1];//切换哈希表为刚刚rehash的新的表项。
            _dictReset(&d->ht[1]);//清空值
            d->rehashidx = -1;
            return 0;
        }

        /* 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)d->rehashidx);
        while(d->ht[0].table[d->rehashidx] == NULL)
			d->rehashidx++;//找一个非空的表项
        de = d->ht[0].table[d->rehashidx];
		//找到了，就这个，厦门准备将这个表项里面的链表拷贝到新的哈希表里面
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {//将这个链表的数据插入到ht[1]表项中。
            unsigned int h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;//得到这个key在新table中的下标
            de->next = d->ht[1].table[h];//将这个表项插入到新ht的头部
            d->ht[1].table[h] = de;//放到新的里面去，注意是插入到头部
            d->ht[0].used--;
            d->ht[1].used++;
            de = nextde;//下一个
        }
        d->ht[0].table[d->rehashidx] = NULL;
        d->rehashidx++;//跳过这个槽位
    }
    return 1;
}

这样在每次查找key的时候，做一次rehash，调整一个槽位的数据。平摊到某次的代价就小了，不至于某个客户端的查询操作得等所有槽位都迁移完成了才能得到满足。