字典是redis底層數(shù)據(jù)結(jié)構(gòu)之一，在dict.c中實現(xiàn)，下面分析下他的實現(xiàn)。

一.簡介

redis的dict仍然是一個數(shù)組+鏈表實現(xiàn)的哈希表。區(qū)別為redis的dict有兩個哈希表，第二個哈希表resize時使用，如下為它頭文件中定義的結(jié)構(gòu)：

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

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    //當(dāng)前哈希表中
    unsigned long used;
} dictht;

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; //rehash進度
    unsigned long iterators; /* number of iterators currently running */
} dict;

redis的字典有兩個哈希表dictht[0]和dictht[1],只有rehash時兩個哈希表才同時使用，平時只有dictht[0]哈希表中有數(shù)據(jù)。
rehashidx用來標(biāo)記rehash正在執(zhí)行到哪個槽，如果沒有rehashing則返回-1.
redis rehash最大的特點是漸進性rehash，將rehash操作分散在插入，刪除等操作中。這點和ThreadPoolExecutor實現(xiàn)思想很像有木有。

二.實現(xiàn)分析：
1.插入：

int dictAdd(dict *d, void *key, void *val)
{
    dictEntry *entry = dictAddRaw(d,key,NULL);

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);
    return DICT_OK;
}

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)
{
    long index;
    dictEntry *entry;
    dictht *ht;
    
    //如果正在rehashing，則執(zhí)行一次_dictRehashStep操作。
    if (dictIsRehashing(d)) _dictRehashStep(d);

    //獲取插入的key在數(shù)組的中的位置
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1)
        return NULL;

    //如果正在執(zhí)行rehash操作則將entry插入ht[1],否在插入ht[0]
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
    entry = zmalloc(sizeof(*entry));
    //放入鏈表頭
    entry->next = ht->table[index];
    ht->table[index] = entry;
    //負(fù)載+1
    ht->used++;

    dictSetKey(d, entry, key);
    return entry;
}

//返回一個key所在的數(shù)組下標(biāo)并判斷該key是否存在。如果沒有執(zhí)行rehash，則只搜索ht[0]并返回該key在ht[0]的下標(biāo)。如果正在rehash則兩個哈希表都搜索并返回在ht[1]的下標(biāo).
static long _dictKeyIndex(dict *d, const void *key, uint64_t hash, dictEntry **existing)
{
    unsigned long idx, table;
    dictEntry *he;
    if (existing) *existing = NULL;

    //如果當(dāng)前負(fù)載已經(jīng)達到負(fù)載因子，則擴容。
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    
    //先搜索第一個哈希表，搜索完第一個哈希表之后，如果當(dāng)前字典沒有在執(zhí)行rehash，則不搜索第二個哈希表。如果正在執(zhí)行rehash，則在搜索第二個哈希表。
    for (table = 0; table <= 1; table++) {
        //取余計算key應(yīng)放置的數(shù)組下標(biāo)
        idx = hash & d->ht[table].sizemask;
        //沿著當(dāng)前槽的鏈表向后搜索是否有該key，如果有返回-1.
        he = d->ht[table].table[idx];
        while(he) {
            if (key==he->key || dictCompareKeys(d, key, he->key)) {
                if (existing) *existing = he;
                return -1;
            }
            he = he->next;
        }
        //如果沒有rehashing，則不再搜索ht[1]
        if (!dictIsRehashing(d)) break;
    }
    return idx;
}

//檢查當(dāng)前哈希表是否需要擴容，正在rehash的話不擴容，擴容后大小為比used*2大的最接近的2的n次冪。
static int _dictExpandIfNeeded(dict *d)
{
    //正在rehash的話不擴容。
    if (dictIsRehashing(d)) return DICT_OK;

    //如果ht[0]是空，則初始化
    if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
    
    //負(fù)載因為為1.但是如果正在執(zhí)行bgsave操作，負(fù)載因子為dict_force_resize_ratio 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))
    {
        //擴容，擴容數(shù)為當(dāng)前已有元素數(shù)量*2
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

//擴容
int dictExpand(dict *d, unsigned long size)
{
    //如果正在rehashing或者擴容之后負(fù)載仍然大于1，返回錯誤
    if (dictIsRehashing(d) || d->ht[0].used > size)
        return DICT_ERR;

    dictht n; /* the new hash table */
    //確保size為2的倍數(shù)
    unsigned long realsize = _dictNextPower(size);

    //如果擴容之后的size仍等于ht[0]size，則返回錯誤。
    if (realsize == d->ht[0].size) return DICT_ERR;

    //開辟哈希表空間
    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;
    }

    //將新建的哈希表賦值給ht[1]
    d->ht[1] = n;
    d->rehashidx = 0;
    return DICT_OK;
}

插入操作有幾個要點：
1.漸進性hash:
插入時會判斷當(dāng)前字典是否正在rehashing，如果正在rehashing，會執(zhí)行一次rehash操作.
2.二倍擴容
擴容后大小為比used*2大的最接近的2的n次冪。這樣&運算即可算出key要插入的數(shù)組下標(biāo)。
3.負(fù)載因子為1
但是如果dict_can_resize標(biāo)志位為true，表明正在執(zhí)行rdb寫入操作，此時負(fù)載因子為5.
4.頭插法
新的節(jié)點插入到表頭
5.如果正在rehash，則新節(jié)點直接插入到ht[1]。

rehash：

int dictRehash(dict *d, int n) {
    int empty_visits = n*10; /* Max number of empty buckets to visit. */
    if (!dictIsRehashing(d)) return 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;
        }
        de = d->ht[0].table[d->rehashidx];
        //將當(dāng)前槽上鏈表的所有節(jié)點都引動到ht[1]
        while(de) {
            uint64_t h;

            nextde = de->next;
            /* Get the index in the new hash table */
            h = dictHashKey(d, de->key) & d->ht[1].sizemask;
            de->next = d->ht[1].table[h];
            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++;
    }

    //檢查時候完成，完成的話將整個ht[1]賦值給ht[0].
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);
        d->ht[0] = d->ht[1];
        _dictReset(&d->ht[1]);
        d->rehashidx = -1;
        return 0;
    }

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

rehash操作很簡單，一次rehash操作移動一個槽。rehash完成后會釋放ht[0],并將ht[1]賦值給ht[0].