最近工作有點(diǎn)忙铐炫，拖了好久才擠出時(shí)間學(xué)習(xí)dict源碼恳守。還是希望能堅(jiān)持讀下去句各。

先簡單介紹一下redis字典

字典的目的是為了通過某個(gè)信息(key) 找到另一個(gè)信息(value)粹断。為了快速從key找到value癌压，字典通常會(huì)用hash表作為底層的存儲(chǔ)，redis的字典也不例外撰洗，它的實(shí)現(xiàn)是基于時(shí)間復(fù)雜度為O(1)的hash算法（關(guān)于hash表的介紹可以參考《算法導(dǎo)論》"散列表"一章）
redis中字典的主要用途有以下兩個(gè)：

1.實(shí)現(xiàn)數(shù)據(jù)庫鍵空間（key space）篮愉；
2.用作 Hash 類型鍵的底層實(shí)現(xiàn)之一；

第一種情況：因?yàn)閞edis是基于key-val的存儲(chǔ)系統(tǒng)差导，整個(gè)db的鍵空間就是一個(gè)大字典试躏，這個(gè)字典里放了許多key-val對(duì)，不論value是String设褐、List颠蕴、Hash、Set络断、Zset中的哪種類型裁替，redis都會(huì)根據(jù)每個(gè)key生成一個(gè)字典的索引。
第二種情況：若value的類型是Redis中的Hash貌笨，在Hash數(shù)據(jù)量較大的情況下 redis會(huì)將Hash中的每個(gè)field也當(dāng)作key生成一個(gè)字典(出于性能考慮弱判，Hash數(shù)據(jù)量小的時(shí)候redis會(huì)使用壓縮列表ziplist來存Hash的filed)，最終 Hash的key是一個(gè)字典的索引昌腰，key中的所有field又分別是另一個(gè)字典的索引膀跌。

redis中dict的定義

上圖的結(jié)構(gòu)是dict.h文件的整個(gè)藍(lán)圖
首先從上圖能看出 redis解決hash沖突的方法用的是鏈地址法，將沖突的鍵值對(duì)按照一個(gè)單向鏈表來存儲(chǔ)捅伤，每個(gè)底層的key-val節(jié)點(diǎn)都是一個(gè)鏈表節(jié)點(diǎn)。

dictEntry

看看單個(gè)key-val節(jié)點(diǎn)結(jié)構(gòu)聲明的代碼：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//下一個(gè)節(jié)點(diǎn)的地址
} dictEntry;

沒什么可說的祠汇，就是一個(gè)鏈表節(jié)點(diǎn)的聲明仍秤，節(jié)點(diǎn)里存了key、value以及下一個(gè)節(jié)點(diǎn)的指針(下文直接用"dictEntry"指代"key-val節(jié)點(diǎn)")诗力。因?yàn)関alue有多種類型苇本，所以value用了union來存儲(chǔ)菜拓，c語言的union總結(jié)起來就是兩句話: In union, all members share the same memory location...Size of a union is taken according the size of largest member in union.(union的所有成員共享同一塊內(nèi)存尘惧，union的size取決于它的最大的成員的size)

dictht

通常實(shí)現(xiàn)一個(gè)hash表時(shí)會(huì)使用一個(gè)buckets存放dictEntry的地址喷橙，將key代入hash函數(shù)得到的值就是buckets的索引贰逾，這個(gè)值決定了我們要將此dictEntry節(jié)點(diǎn)放入buckets的哪個(gè)索引里菠秒。這個(gè)buckets實(shí)際上就是我們說的hash表践叠。
這個(gè)buckets存儲(chǔ)在哪里呢禁灼？
dict.h的dictht結(jié)構(gòu)中table存放的就是buckets的地址弄捕。以下是dictht的聲明：

typedef struct dictht {
    dictEntry **table;//buckets的地址
    unsigned long size;//buckets的大小,總保持為 2^n
    unsigned long sizemask;//掩碼守谓，用來計(jì)算hash值對(duì)應(yīng)的buckets索引
    unsigned long used;//當(dāng)前dictht有多少個(gè)dictEntry節(jié)點(diǎn)
} dictht;

成員變量used：要注意 used跟size沒有任何關(guān)系，這是當(dāng)前dictht包含多少個(gè)dictEntry節(jié)點(diǎn)的意思,漸進(jìn)rehash(下文會(huì)詳細(xì)介紹rehash)時(shí)會(huì)用這個(gè)成員判斷是否已經(jīng)rehash完成荞雏，而size是buckets的大小凤优。
成員變量sizemask：key通過hash函數(shù)得到的hash值 跟 sizemask 作"與運(yùn)算"别洪，得到的值就是這個(gè)key需要放入的buckets的索引：

h = dictHashKey(d, de->key) & d->ht[0].sizemask

d->ht[0].table[h]就是這個(gè)dictEntry該放入的地方挖垛。這應(yīng)該也是bucekts大小總保持2^n的原因痢毒，方便通過hash值與sizemask得到索引。

dict

上面說了栋荸，dictht實(shí)際上就是hash表的核心晌块，但是只有一個(gè)dictht很多事情還做不了匆背，所以redis定義了一個(gè)叫dict的結(jié)構(gòu)以支持字典的各種操作钝尸，如rehash和遍歷hash等珍促。

typedef struct dict {
    dictType *type;//dictType里存放的是一堆工具函數(shù)的函數(shù)指針猪叙，
    void *privdata;//保存type中的某些函數(shù)需要作為參數(shù)的數(shù)據(jù)
    dictht ht[2];//兩個(gè)dictht沐悦，ht[0]平時(shí)用五督，ht[1] rehash時(shí)用
    long rehashidx; /* rehashing not in progress if rehashidx == -1 *///當(dāng)前rehash到buckets的哪個(gè)索引充包，-1時(shí)表示非rehash狀態(tài)
    int iterators; /* number of iterators currently running *///安全迭代器的計(jì)數(shù)。
} dict;

迭代器的定義先不管冠场，等下文講到安全非安全迭代器的時(shí)候再細(xì)說碴裙。

hash算法

redis內(nèi)置3種hash算法

• dictIntHashFunction舔株，對(duì)正整數(shù)進(jìn)行hash
• dictGenHashFunction载慈，對(duì)字符串進(jìn)行hash
• dictGenCaseHashFunction办铡，對(duì)字符串進(jìn)行hash琳要，不區(qū)分大小寫

這些hash函數(shù)沒什么好說的焙蹭，有興趣google一下就好孔厉。
在講redis字典基本操作之前撰豺，有必要介紹一下rehash污桦，因?yàn)閐ict的增刪改查(CRUD)都會(huì)執(zhí)行被動(dòng)rehash凡橱。

rehash

什么是rehash

當(dāng)字典的dictEntry節(jié)點(diǎn)擴(kuò)展到一定規(guī)模時(shí)稼钩，hash沖突的鏈表會(huì)越來越長坝撑，使原本O(1)的hash運(yùn)算轉(zhuǎn)換成了O(n)的鏈表遍歷，從而導(dǎo)致字典的增刪改查(CRUD)越來越低效抚笔，這個(gè)時(shí)候redis會(huì)利用dict結(jié)構(gòu)中的dictht[1]擴(kuò)充一個(gè)新的buckets(調(diào)用dictExpand)，然后慢慢將dictht[0]的節(jié)點(diǎn)遷移至dictht[1]膨蛮、用dictht[1]替換掉dictht[0] (調(diào)用dictRehash)鸽疾。
具體擴(kuò)充過程如下：

• 1.調(diào)用dictAdd為dict添加一個(gè)dictEntry節(jié)點(diǎn)训貌。
• 2.調(diào)用_dictKeyIndex找到應(yīng)該放置在buckets的哪個(gè)索引里递沪。順便調(diào)用_dictExpandIfNeeded判斷是否需要擴(kuò)充 dictht[1]款慨。
• 3.若滿足條件：dictht[0]的dictEntry節(jié)點(diǎn)數(shù)/buckets的索引數(shù)>=1則調(diào)用dictExpand檩奠，若dictEntry節(jié)點(diǎn)數(shù)/buckets的索引數(shù)>=dict_force_resize_ratio(默認(rèn)是5)埠戳，則強(qiáng)制執(zhí)行dictExpand擴(kuò)充dictht[1]整胃。

需要注意的是上面的條件不是rehash的條件屁使，而是擴(kuò)充dictht[1]并打開dict rehash開關(guān)的條件蛮寂。(因?yàn)閞ehash不是一次性完成的共郭，若dictEntry節(jié)點(diǎn)非常多，rehash過程會(huì)進(jìn)行很久從而block其他操作岸蜗。所以redis采用了漸進(jìn)rehash璃岳，分步進(jìn)行铃慷，下文講rehash方式時(shí)會(huì)詳細(xì)介紹)犁柜。dictExpand做的只是把dictht[1]的buckets擴(kuò)充到合適的大小馋缅，再把dict的rehashidx從-1置為0(打開rehash開關(guān))萤悴。打開rehash開關(guān)之后該dict每次增刪改查(CRUD)都會(huì)執(zhí)行一次rehash覆履，把dictht[0]的buckets中的一個(gè)索引里的鏈表移動(dòng)到dictht[1]硝全。rehash的條件是rehashidx是否為-1柳沙。
放源碼:

static int dict_can_resize = 1; 
static unsigned int dict_force_resize_ratio = 5; 

//判斷dictht[1]是否需要擴(kuò)充(并將dict調(diào)整為正在rehash狀態(tài))；若dict剛創(chuàng)建柱恤，則擴(kuò)充dictht[0]  
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. */
    //這是為剛創(chuàng)建的dict準(zhǔn)備的梗顺，d->ht[0].size == 0時(shí)調(diào)用dictExpand只會(huì)擴(kuò)充dictht[0]寺谤，不會(huì)改變dict的rehash狀態(tài)
    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))
    {
        //1:1時(shí)如果全局變量dict_can_resize為1則expand眼俊，
        //或者節(jié)點(diǎn)數(shù)/bucket數(shù)超過dict_force_resize_ratio(5)則擴(kuò)充
        return dictExpand(d, d->ht[0].used*2);buckets大小擴(kuò)充至 dict已使用節(jié)點(diǎn)的2倍的下一個(gè)2^n疮胖。假如used=4澎灸，buckets會(huì)擴(kuò)充到8性昭；used=5糜颠，buckets會(huì)擴(kuò)充到16
    }
    return DICT_OK;
}

/* Expand or create the hash table */
//三個(gè)功能:
//1.為剛初始化的dict的dictht[0]分配table(buckets)
//2.為已經(jīng)達(dá)到rehash要求的dict的dictht[1]分配一個(gè)更大(下一個(gè)2^n)的table(buckets),并將rehashidx置為0
//3.為需要縮小bucket的dict分配一個(gè)更小的buckets括蝠，并將rehashidx置為0(打開rehash開關(guān))
int dictExpand(dict *d, unsigned long size)
{
    dictht n; /* the new hash table *///最終會(huì)賦值給d->ht[0]和d->ht[1]忌警，所以不用new一個(gè)dictht
    unsigned long realsize = _dictNextPower(size);//從4開始找大于等于size的最小2^n作為新的slot數(shù)量

    /* 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)//如果當(dāng)前使用的bucket數(shù)目大于想擴(kuò)充之后的size
        return DICT_ERR;

    /* Rehashing to the same table size is not useful. */
    if (realsize == d->ht[0].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) {//剛創(chuàng)建的dict
        d->ht[0] = n;//為d->ht[0]賦值
        return DICT_OK;
    }

    /* Prepare a second hash table for incremental rehashing */
    d->ht[1] = n;
    d->rehashidx = 0;//設(shè)置rehash狀態(tài)為正在進(jìn)行rehash
    return DICT_OK;
}

畫圖分析一下擴(kuò)充流程:
假設(shè)一個(gè)dict已經(jīng)有4個(gè)dictEntry節(jié)點(diǎn)(value分別為"a","b","c","d")，根據(jù)key的不同朋譬，存放在buckets的不同索引下徙赢。

現(xiàn)在如果我們想添加一個(gè)dictEntry狡赐，由于d->ht[0].used >= d->ht[0].size (4>=4)枕屉，滿足了擴(kuò)充dictht[1]的條件西潘，會(huì)執(zhí)行dictExpand喷市。根據(jù)擴(kuò)充規(guī)則咆蒿，dictht[1]的buckets會(huì)擴(kuò)充到8個(gè)槽位沃测。

之后再將要添加的dictEntry加入到dictht[1]的buckets中的某個(gè)索引下蒂破，不過這個(gè)操作不屬于dictExpand附迷，不展開了喇伯。
擴(kuò)充之后的dict的成員變量rehashidx被賦值為0稻据，此后每次CRUD都會(huì)執(zhí)行一次被動(dòng)rehash把dictht[0]的buckets中的一個(gè)鏈表遷移到dictht[1]中捻悯，直到遷移完畢算柳。

rehash的方式

剛才提到了被動(dòng)rehash瞬项，實(shí)際上dict的rehash分為兩種方式:

• 主動(dòng)方式：調(diào)用dictRehashMilliseconds執(zhí)行一毫秒。在redis的serverCron里調(diào)用，看名字就知道是為redis服務(wù)端準(zhǔn)備的定時(shí)事件唠倦，每次執(zhí)行1ms的dictRehash稠鼻，簡單粗暴候齿。慌盯。
• 被動(dòng)方式：字典的增刪改查(CRUD)調(diào)用dictAdd亚皂，dicFind灭必，dictDelete跟衅，dictGetRandomKey等函數(shù)時(shí)伶跷，會(huì)調(diào)用_dictRehashStep撩穿，遷移buckets中的一個(gè)非空bucket食寡。

放上源碼:

int dictRehashMilliseconds(dict *d, int ms) {
    long long start = timeInMilliseconds();
    int rehashes = 0;

    while(dictRehash(d,100)) {//每次最多執(zhí)行buckets的100個(gè)鏈表rehash
        rehashes += 100;
        if (timeInMilliseconds()-start > ms) break;//最多執(zhí)行ms毫秒
    }
    return rehashes;
}
static void _dictRehashStep(dict *d) {//只rehash一個(gè)bucket
    //沒有安全迭代器綁定在當(dāng)前dict上時(shí)才能rehash，下文講"安全迭代器"時(shí)會(huì)細(xì)說呻畸，這里只需要知道這是rehash buckets的1個(gè)鏈表
    if (d->iterators == 0) dictRehash(d,1);
}

上面可以看出伤为，不論是哪種rehash方式绞愚，底層都是通過dictRehash實(shí)現(xiàn)的位衩，它是字典rehash的核心代碼僚祷。

dictRehash

dictRehash有兩個(gè)參數(shù)辙谜，d是rehash的dict指針筷弦，n是需要遷移到dictht[1]的非空桶數(shù)目烂琴；返回值0表示rehash完畢，否則返回1号醉。

int dictRehash(dict *d, int n) {//rehash n個(gè)bucket到ht[1]畔派，或者掃了n*10次空bucket就退出
    int empty_visits = n*10; /* Max number of empty buckets to visit. *///最多只走empty_visits個(gè)空bucket线椰，一旦遍歷的空bucket數(shù)超過這個(gè)數(shù)則返回1，所以可能執(zhí)行這個(gè)函數(shù)的時(shí)候一個(gè)bucket也沒有rehash到ht[1]
    if (!dictIsRehashing(d)) return 0;//rehash已完成

    while(n-- && d->ht[0].used != 0) {//遍歷n個(gè)bucket,ht[0]中還有dictEntry
        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āng)前bucket為空時(shí)跳到下一個(gè)bucket并且
            d->rehashidx++;
            if (--empty_visits == 0) return 1;
        }
        //直到當(dāng)前bucket不為空bucket時(shí)
        de = d->ht[0].table[d->rehashidx];//當(dāng)前bucket里第一個(gè)dictEntry的指針(地址)
        /* Move all the keys in this bucket from the old to the new hash HT */
        while(de) {//把當(dāng)前bucket的所有ditcEntry節(jié)點(diǎn)都移到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;//hash函數(shù)算出的值& 新hashtable(buckets)的sizemask,保證h會(huì)小于新buckets的size
            de->next = d->ht[1].table[h];//插入到鏈表的最前面！省時(shí)間
            d->ht[1].table[h] = de;

            d->ht[0].used--;//老dictht的used(節(jié)點(diǎn)數(shù))-1
            d->ht[1].used++;//新dictht的used(節(jié)點(diǎn)數(shù))+1
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;//當(dāng)前bucket已經(jīng)完全移走
        d->rehashidx++;//下一個(gè)bucket
    }

    /* Check if we already rehashed the whole table... */
    if (d->ht[0].used == 0) {
        zfree(d->ht[0].table);//釋放掉ht[0].table的內(nèi)存(buckets)
        d->ht[0] = d->ht[1];//淺復(fù)制躺孝，table只是一個(gè)地址括细，直接給ht[0]就好
        _dictReset(&d->ht[1]);//ht[1]的table置空
        d->rehashidx = -1;
        return 0;
    }

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

拿上面的圖作為的例子調(diào)用一次dictRehash(d, 1)，會(huì)產(chǎn)生如下布局:

• 之前a和b的放在dictht[0]的同一個(gè)buckets索引[0]下览濒，但是經(jīng)過rehash，h = dictHashKey(d, de->key) & d->ht[1].sizemask乏苦，h可能依舊為0汇荐，也有可能變?yōu)?。ps:如果兩個(gè)dictEntry仍然落在同一個(gè)索引下振惰，它倆順序會(huì)顛倒。
• rehashidx+1
• 返回1 More to rehash

若在此基礎(chǔ)上在執(zhí)行一次dictRehash(d, 1)利赋，則會(huì)跳過索引為1的那個(gè)空bucket，遷移下一個(gè)bucket。

字典的基本操作

dictCreate:創(chuàng)建一個(gè)dict

有了rehash的基本認(rèn)識(shí)拦惋，下面就可以說說redis字典支持的一些常規(guī)操作了：
redis用dictCreate創(chuàng)建并初始化一個(gè)dict，放源碼一看就明白：

dict *dictCreate(dictType *type,
        void *privDataPtr)
{
    dict *d = zmalloc(sizeof(*d));

    _dictInit(d,type,privDataPtr);
    return d;
}

/* Initialize the hash table */
int _dictInit(dict *d, dictType *type,
        void *privDataPtr)
{
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}
static void _dictReset(dictht *ht)
{
    ht->table = NULL;
    ht->size = 0;
    ht->sizemask = 0;
    ht->used = 0;
}

需要注意的是創(chuàng)建初始化一個(gè)dict時(shí)并沒有為buckets分配空間安寺，table是賦值為null的厕妖。只有在往dict里添加dictEntry節(jié)點(diǎn)時(shí)才會(huì)為buckets分配空間我衬，真正意義上創(chuàng)建一張hash表叹放。
執(zhí)行dictCreate后會(huì)得到如下布局：

dictAdd(增):添加一個(gè)dictEntry節(jié)點(diǎn)

int dictAdd(dict *d, void *key, void *val)//完整的添加dictEntry節(jié)點(diǎn)的流程
{
    dictEntry *entry = dictAddRaw(d,key);//只在buckets的某個(gè)索引里新建一個(gè)dictEntry并調(diào)整鏈表的位置,只設(shè)置key，不設(shè)置不設(shè)置val

    if (!entry) return DICT_ERR;
    dictSetVal(d, entry, val);//為這個(gè)entry設(shè)置值
    return DICT_OK;
}

//_dictKeyIndex會(huì)判斷是否達(dá)到expand條件,若達(dá)到條件則執(zhí)行dictExpand將dictht[1]擴(kuò)大 并將改dict的rehash狀態(tài)置為正在進(jìn)行中(-1置為0)
dictEntry *dictAddRaw(dict *d, void *key)//new一個(gè)dictEntry然后把它放到某個(gè)buckets索引下的鏈表頭部挠羔，填上key
{
    int index;
    dictEntry *entry;
    dictht *ht;

    if (dictIsRehashing(d)) _dictRehashStep(d);//如果正在rehash則被動(dòng)rehash一步

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)//計(jì)算這個(gè)key在當(dāng)前dict應(yīng)該放到bucket的哪個(gè)索引里,key已存在則返回-1
        return NULL;

    /* Allocate the memory and store the new entry.
     * Insert the element in top, with the assumption that in a database
     * system it is more likely that recently added entries are accessed
     * more frequently. */
    //雖然_dictKeyIndex()時(shí)已經(jīng)確認(rèn)過是哪張dictht,但是調(diào)用者沒辦法知道井仰，所以再確認(rèn)一下
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];//在rehash則把dictEntry加到ht[1]
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;

    /* Set the hash entry fields. */
    dictSetKey(d, entry, key);//如果dict d沒有keyDup則直接entry->key = xxx,賦值
    return entry;
}

static int _dictKeyIndex(dict *d, const void *key)//根據(jù)dict和key返回這個(gè)key該存放的buckets的索引（但是用哪個(gè)dictht(ht[0]或ht[1])上層調(diào)用者是未知的）,key已存在則返回-1
{
    unsigned int h, idx, table;
    dictEntry *he;

    /* Expand the hash table if needed */
    if (_dictExpandIfNeeded(d) == DICT_ERR)
        return -1;
    /* Compute the key hash value */
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;
        /* Search if this slot does not already contain the given key */
        he = d->ht[table].table[idx];//buckets 的idx索引下的第一個(gè)dictEntry的地址
        while(he) {//遍歷一遍這個(gè)dictEntry鏈表
            if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經(jīng)存在,返回-1
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;//不在rehash時(shí)，直接跳出循環(huán)不做第二個(gè)dictht[1]的計(jì)算
    }
    return idx;
}

主要分為以下幾個(gè)步驟:

• 1.根據(jù)key的hash值找到應(yīng)該存放的位置(buckets索引)破加。
• 2.若dict是剛創(chuàng)建的還沒有為bucekts分配內(nèi)存俱恶，則會(huì)在找位置(_dictKeyIndex)時(shí)調(diào)用_dictExpandIfNeeded，為dictht[0]expand一個(gè)大小為4的buckets；若dict正好到了expand的時(shí)機(jī)合是，則會(huì)expand它的dictht[1]了罪，并將rehashidx置為0打開rehash開關(guān)，_dictKeyIndex返回的會(huì)是dictht[1]的索引聪全。
• 3.申請(qǐng)一個(gè)dictEntry大小的內(nèi)存插入到buckets對(duì)應(yīng)索引下的鏈表頭部泊藕，并給dictEntry設(shè)置next指針和key。
• 4.為dictEntry設(shè)置value

dictDelete(刪):刪除一個(gè)dictEntry節(jié)點(diǎn)

dict刪除函數(shù)主要有三個(gè)难礼，從低到高依次刪除dictEntry娃圆、dictht、dict蛾茉。

• dictDelete在redis在字典里的作用是刪除一個(gè)dictEntry并釋放dictEntry成員key和成員v指向的內(nèi)存讼呢；
• _dictClear刪除并釋放一個(gè)dict的指定dictht；
• dictRelease刪除并釋放整個(gè)dict谦炬。

//刪除dictEntry并釋放dictEntry成員key和成員v指向的內(nèi)存
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}
static int dictGenericDelete(dict *d, const void *key, int nofree)//刪除一個(gè)dictEntry節(jié)點(diǎn)悦屏，nofree參數(shù)指定是否釋放這個(gè)節(jié)點(diǎn)的key和val的內(nèi)存(如果key和val是指針的話),nofree為1不釋放，0為釋放
{
    unsigned int h, idx;
    dictEntry *he, *prevHe;
    int table;

    if (d->ht[0].size == 0) return DICT_ERR; /* d->ht[0].table is NULL */
    if (dictIsRehashing(d)) _dictRehashStep(d);//被動(dòng)rehash一次
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;//找到key對(duì)應(yīng)的bucket索引
        he = d->ht[table].table[idx];//索引的第一個(gè)dictEntry節(jié)點(diǎn)指針
        prevHe = NULL;
        while(he) {
            //單向鏈表刪除步驟
            if (key==he->key || dictCompareKeys(d, key, he->key)) {//key匹配
                /* Unlink the element from the list */
                if (prevHe)
                    prevHe->next = he->next;
                else
                    d->ht[table].table[idx] = he->next;
                if (!nofree) {
                    dictFreeKey(d, he);
                    dictFreeVal(d, he);
                }
                zfree(he);
                d->ht[table].used--;
                return DICT_OK;
            }
            prevHe = he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;//如果不在rehash键思，則不查第二個(gè)table(dictht[1])
    }
    return DICT_ERR; /* not found */
}

//刪除一個(gè)dict的指定dictht础爬，釋放dictht的table內(nèi)相關(guān)的全部內(nèi)存，并reset dictht
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {//傳遞dict指針是為了調(diào)用dictType的相關(guān)函數(shù),dictFreeVal里會(huì)調(diào)
    unsigned long i;

    /* Free all the elements */
    for (i = 0; i < ht->size && ht->used > 0; i++) {//buckets大小稚机，dictEntry使用數(shù)
        dictEntry *he, *nextHe;

        if (callback && (i & 65535) == 0) callback(d->privdata);

        if ((he = ht->table[i]) == NULL) continue;
        while(he) {
            //遍歷刪除dictEntry鏈表
            nextHe = he->next;
            dictFreeKey(d, he);
            dictFreeVal(d, he);
            zfree(he);
            ht->used--;
            he = nextHe;
        }
    }
    /* Free the table and the allocated cache structure */
    zfree(ht->table);
    /* Re-initialize the table */
    _dictReset(ht);
    return DICT_OK; /* never fails */
}

//刪除并釋放整個(gè)dict
void dictRelease(dict *d)
{
    _dictClear(d,&d->ht[0],NULL);
    _dictClear(d,&d->ht[1],NULL);
    zfree(d);
}

dictReplace(改):修改一個(gè)dictEntry節(jié)點(diǎn)的成員v(值)

//修改一個(gè)dictEntry的val幕帆，也是一種添加dictEntry的方式，如果dictAdd失敗(key已存在)則replace這個(gè)dictEntry的val
int dictReplace(dict *d, void *key, void *val)//用新val取代一個(gè)dictEntry節(jié)點(diǎn)的舊val
{
    dictEntry *entry, auxentry;

    /* Try to add the element. If the key
     * does not exists dictAdd will suceed. */
    if (dictAdd(d, key, val) == DICT_OK)//試著加一個(gè)新dictEntry赖条，失敗則說明key已存在
        return 1;
    /* It already exists, get the entry */
    entry = dictFind(d, key);//創(chuàng)建節(jié)點(diǎn)失敗則一定能找到這個(gè)已經(jīng)存在了的key
    /* Set the new value and free the old one. Note that it is important
     * to do that in this order, as the value may just be exactly the same
     * as the previous one. In this context, think to reference counting,
     * you want to increment (set), and then decrement (free), and not the
     * reverse. */
    auxentry = *entry;//需要替換val的dictEntry節(jié)點(diǎn),auxentry用來刪除(釋放)val
    dictSetVal(d, entry, val);//替換val的操作
    dictFreeVal(d, &auxentry);//考慮val可能是一個(gè)指針失乾，指針指向的內(nèi)容不會(huì)被刪除，所以調(diào)用這個(gè)dict的type類里的dictFreeVal釋放掉那塊內(nèi)存
    return 0;
}

代碼里還有一個(gè)dictReplaceRaw函數(shù)纬乍，這個(gè)函數(shù)跟replace沒啥關(guān)系碱茁，只是封裝了一下dictAddRaw，沒有替換的功能仿贬。

dictFind(查):根據(jù)key找到當(dāng)前dict存放該key的dictEntry

//返回dictEntry的地址
dictEntry *dictFind(dict *d, const void *key)//會(huì)執(zhí)行被動(dòng)rehash
{
    dictEntry *he;
    unsigned int h, idx, table;

    if (d->ht[0].used + d->ht[1].used == 0) return NULL; /* dict is empty */
    if (dictIsRehashing(d)) _dictRehashStep(d);//查找key的時(shí)候也會(huì)被動(dòng)rehash
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;//先計(jì)算當(dāng)前buckets中key應(yīng)存放的索引
        he = d->ht[table].table[idx];//buckets 的idx索引下的第一個(gè)dictEntry的地
        while(he) {//遍歷查找該鏈表
            if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經(jīng)存在,返回-1
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;//不在rehash時(shí)纽竣，直接跳出循環(huán)不在dictht[1]里查找
    }
    return NULL;
}

安全 非安全迭代器

介紹一下字典的迭代器
redis字典的迭代器分為兩種，一種是safe迭代器另一種是unsafe迭代器:
safe迭代器在迭代的過程中用戶可以對(duì)該dict進(jìn)行CURD操作茧泪，unsafe迭代器在迭代過程中用戶只能對(duì)該dict執(zhí)行迭代操作蜓氨。

• 上文說過每次執(zhí)行CURD操作時(shí)，如果dict的rehash開關(guān)已經(jīng)打開队伟，則會(huì)執(zhí)行一次被動(dòng)rehash操作將dictht[0]的一個(gè)鏈表遷移到dictht[1]上穴吹。這時(shí)若迭代器進(jìn)行迭代操作會(huì)導(dǎo)致重復(fù)迭代幾個(gè)剛被rehash到dictht[1]的dictEntry節(jié)點(diǎn)。那么一邊迭代一遍CRUD嗜侮，這是怎么實(shí)現(xiàn)的呢港令？
  redis在dict結(jié)構(gòu)里增加一個(gè)iterator成員啥容，用來表示綁定在當(dāng)前dict上的safe迭代器數(shù)量，dict每次CRUD執(zhí)行_dictRehashStep時(shí)判斷一下是否有綁定safe迭代器顷霹，如果有則不進(jìn)行rehash以免擾亂迭代器的迭代咪惠，這樣safe迭代時(shí)字典就可以正常進(jìn)行CRUD操作了。

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

• unsafe迭代器在執(zhí)行迭代過程中不允許對(duì)dict進(jìn)行其他操作淋淀，如何保證這一點(diǎn)呢遥昧？
  redis在第一次執(zhí)行迭代時(shí)會(huì)用dictht[0]、dictht[1]的used朵纷、size渠鸽、buckets地址計(jì)算一個(gè)fingerprint(指紋)，在迭代結(jié)束后釋放迭代器時(shí)再計(jì)算一遍fingerprint看看是否與第一次計(jì)算的一致柴罐，若不一致則用斷言終止進(jìn)程，生成指紋的函數(shù)如下:

//unsafe迭代器在第一次dictNext時(shí)用dict的兩個(gè)dictht的table憨奸、size革屠、used進(jìn)行hash算出一個(gè)結(jié)果
//最后釋放iterator時(shí)再調(diào)用這個(gè)函數(shù)生成指紋，看看結(jié)果是否一致排宰，不一致就報(bào)錯(cuò).
//safe迭代器不會(huì)用到這個(gè)
long long dictFingerprint(dict *d) {
    long long integers[6], hash = 0;
    int j;

    integers[0] = (long) d->ht[0].table;//把指針類型轉(zhuǎn)換成long
    integers[1] = d->ht[0].size;
    integers[2] = d->ht[0].used;
    integers[3] = (long) d->ht[1].table;
    integers[4] = d->ht[1].size;
    integers[5] = d->ht[1].used;

    /* We hash N integers by summing every successive integer with the integer
     * hashing of the previous sum. Basically:
     *
     * Result = hash(hash(hash(int1)+int2)+int3) ...
     *
     * This way the same set of integers in a different order will (likely) hash
     * to a different number. */
    for (j = 0; j < 6; j++) {
        hash += integers[j];
        /* For the hashing step we use Tomas Wang's 64 bit integer hash. */
        hash = (~hash) + (hash << 21); // hash = (hash << 21) - hash - 1;
        hash = hash ^ (hash >> 24);
        hash = (hash + (hash << 3)) + (hash << 8); // hash * 265
        hash = hash ^ (hash >> 14);
        hash = (hash + (hash << 2)) + (hash << 4); // hash * 21
        hash = hash ^ (hash >> 28);
        hash = hash + (hash << 31);
    }
    return hash;
}

介紹完redis迭代器的兩種類型似芝，看看dictIterator的定義:

dictIterator定義

typedef struct dictIterator {
    dict *d;
    long index;//當(dāng)前buckets索引，buckets索引類型是unsinged long板甘，而這個(gè)初始化會(huì)是-1,所以long
    int table, safe;//table是ht的索引只有0和1党瓮，safe是安全迭代器和不安全迭代器
    //安全迭代器就等于加了一個(gè)鎖在dict，使dict在CRUD時(shí)ditcEntry不能被動(dòng)rehash
    dictEntry *entry, *nextEntry;//當(dāng)前hash節(jié)點(diǎn)以及下一個(gè)hash節(jié)點(diǎn)
    /* unsafe iterator fingerprint for misuse detection. */
    long long fingerprint;//dict.c里的dictFingerprint(),不安全迭代器相關(guān)
} dictIterator;

接下來介紹迭代器相關(guān)函數(shù)

dictGetIterator:創(chuàng)建一個(gè)迭代器

//默認(rèn)是new一個(gè)unsafe迭代器
dictIterator *dictGetIterator(dict *d)//獲取一個(gè)iterator就是為這個(gè)dict new一個(gè)迭代器
{
    //不設(shè)置成員變量fingerprint盐类，在dictNext的時(shí)候才設(shè)置寞奸。
    dictIterator *iter = zmalloc(sizeof(*iter));

    iter->d = d;
    iter->table = 0;
    iter->index = -1;
    iter->safe = 0;
    iter->entry = NULL;
    iter->nextEntry = NULL;
    return iter;
}

dictIterator *dictGetSafeIterator(dict *d) {
    dictIterator *i = dictGetIterator(d);

    i->safe = 1;
    return i;
}

為指定dict創(chuàng)建一個(gè)unsafe迭代器：dictGetIterator()
為指定dict創(chuàng)建一個(gè)safe迭代器：dictGetSafeIterator()
需要注意的是創(chuàng)建safe迭代器時(shí)并不會(huì)改變dict結(jié)構(gòu)里iterator成員變量的計(jì)數(shù)，只有迭代真正發(fā)生的時(shí)候才會(huì)+1 表明該dict綁定了一個(gè)safe迭代器在跳。

dictNext:迭代一個(gè)dictEntry節(jié)點(diǎn)

dictEntry *dictNext(dictIterator *iter)//如果下一個(gè)dictEntry不為空枪萄，則返回。為空則繼續(xù)找下一個(gè)bucket的第一個(gè)dictEntry
{
    while (1) {
        if (iter->entry == NULL) {//新new的dictIterator的entry是null猫妙，或者到達(dá)一個(gè)bucket的鏈表尾部
            dictht *ht = &iter->d->ht[iter->table];//dictht的地址
            if (iter->index == -1 && iter->table == 0) {
                //剛new的dictIterator
                if (iter->safe)
                    iter->d->iterators++;
                else
                    iter->fingerprint = dictFingerprint(iter->d);//初始化unsafe迭代器的指紋瓷翻，只進(jìn)行一次
            }
            iter->index++;//buckets的下一個(gè)索引
            if (iter->index >= (long) ht->size) {
                //如果buckets的索引大于等于這個(gè)buckets的大小，則這個(gè)buckets迭代完畢
                
                if (dictIsRehashing(iter->d) && iter->table == 0) {//當(dāng)前用的dictht[0]
                    //考慮rehash割坠，換第二個(gè)dictht 
                    iter->table++;
                    iter->index = 0;//index復(fù)原成0齐帚，從第二個(gè)dictht的第0個(gè)bucket迭代
                    ht = &iter->d->ht[1];//設(shè)置這個(gè)是為了rehash時(shí)更新下面的iter->entry
                } else {
                    break;//迭代完畢了
                }
            }
            iter->entry = ht->table[iter->index];//更新entry為下一個(gè)bucket的第一個(gè)節(jié)點(diǎn)
        } else {
            iter->entry = iter->nextEntry;
        }
        if (iter->entry) {
            /* We need to save the 'next' here, the iterator user
             * may delete the entry we are returning. */
            iter->nextEntry = iter->entry->next;
            return iter->entry;
        }
    }
    return NULL;
}

雖然safe迭代器會(huì)禁止rehash，但在迭代時(shí)有可能已經(jīng)rehash了一部分彼哼，所以迭代器也會(huì)遍歷在dictht[1]中的所有dictEntry对妄。

dictScan

前面說的safe迭代器和unsafe迭代器都是建立在不能rehash的前提下。要通過這種迭代的方式遍歷所有節(jié)點(diǎn)會(huì)停止該dict的被動(dòng)rehash沪羔，阻止了rehash的正常進(jìn)行饥伊。dictScan就是用來解決這種問題的象浑，它可以在不停止rehash的前提下遍歷到所有dictEntry節(jié)點(diǎn)，不過也有非常小的可能性返回重復(fù)的節(jié)點(diǎn)琅豆，具體如何做到的可能得另花大量篇幅介紹愉豺，有興趣可以借助這篇博客理解。