摘要：里存放的是一堆工具函數的函數指針，保存中的某些函數需要作為參數的數據兩個，平時用，時用當前到的哪個索引，時表示非狀態安全迭代器的計數。迭代器的定義先不管，等下文講到安全非安全迭代器的時候再細說。

最近工作有點忙，拖了好久才擠出時間學習dict源碼。還是希望能堅持讀下去。

字典的目的是為了通過某個信息(key) 找到另一個信息(value)。為了快速從key找到value，字典通常會用hash表作為底層的存儲，redis的字典也不例外，它的實現是基于時間復雜度為O(1)的hash算法（關于hash表的介紹可以參考《算法導論》"散列表"一章）
redis中字典的主要用途有以下兩個：

1.實現數據庫鍵空間（key space）；
2.用作 Hash 類型鍵的底層實現之一；

第一種情況：因為redis是基于key-val的存儲系統，整個db的鍵空間就是一個大字典，這個字典里放了許多key-val對，不論value是String、List、Hash、Set、Zset中的哪種類型，redis都會根據每個key生成一個字典的索引。
第二種情況：若value的類型是Redis中的Hash，在Hash數據量較大的情況下 redis會將Hash中的每個field也當作key生成一個字典(出于性能考慮，Hash數據量小的時候redis會使用壓縮列表ziplist來存Hash的filed)，最終 Hash的key是一個字典的索引，key中的所有field又分別是另一個字典的索引。

上圖的結構是dict.h文件的整個藍圖
首先從上圖能看出 redis解決hash沖突的方法用的是鏈地址法，將沖突的鍵值對按照一個單向鏈表來存儲，每個底層的key-val節點都是一個鏈表節點。

看看單個key-val節點結構聲明的代碼：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;//下一個節點的地址
} dictEntry;

沒什么可說的，就是一個鏈表節點的聲明，節點里存了key、value以及下一個節點的指針(下文直接用"dictEntry"指代"key-val節點")。因為value有多種類型，所以value用了union來存儲，c語言的union總結起來就是兩句話: In union, all members share the same memory location...Size of a union is taken according the size of largest member in union.(union的所有成員共享同一塊內存，union的size取決于它的最大的成員的size)

通常實現一個hash表時會使用一個buckets存放dictEntry的地址，將key代入hash函數得到的值就是buckets的索引，這個值決定了我們要將此dictEntry節點放入buckets的哪個索引里。這個buckets實際上就是我們說的hash表。
這個buckets存儲在哪里呢？
dict.h的dictht結構中table存放的就是buckets的地址。以下是dictht的聲明：

typedef struct dictht {
    dictEntry **table;//buckets的地址
    unsigned long size;//buckets的大小,總保持為?2^n
    unsigned long sizemask;//掩碼，用來計算hash值對應的buckets索引
    unsigned long used;//當前dictht有多少個dictEntry節點
} dictht;

成員變量used：要注意 used跟size沒有任何關系，這是當前dictht包含多少個dictEntry節點的意思,漸進rehash(下文會詳細介紹rehash)時會用這個成員判斷是否已經rehash完成，而size是buckets的大小。
成員變量sizemask：key通過hash函數得到的hash值 跟 sizemask 作"與運算"，得到的值就是這個key需要放入的buckets的索引：

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

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

上面說了，dictht實際上就是hash表的核心，但是只有一個dictht很多事情還做不了，所以redis定義了一個叫dict的結構以支持字典的各種操作，如rehash和遍歷hash等。

typedef struct dict {
    dictType *type;//dictType里存放的是一堆工具函數的函數指針，
    void *privdata;//保存type中的某些函數需要作為參數的數據
    dictht ht[2];//兩個dictht，ht[0]平時用，ht[1] rehash時用
    long rehashidx; /* rehashing not in progress if rehashidx == -1 *///當前rehash到buckets的哪個索引，-1時表示非rehash狀態
    int iterators; /* number of iterators currently running *///安全迭代器的計數。
} dict;

迭代器的定義先不管，等下文講到安全非安全迭代器的時候再細說。

redis內置3種hash算法

dictIntHashFunction，對正整數進行hash

dictGenHashFunction，對字符串進行hash

dictGenCaseHashFunction，對字符串進行hash，不區分大小寫

這些hash函數沒什么好說的，有興趣google一下就好。
在講redis字典基本操作之前，有必要介紹一下rehash，因為dict的增刪改查(CRUD)都會執行被動rehash。

當字典的dictEntry節點擴展到一定規模時，hash沖突的鏈表會越來越長，使原本O(1)的hash運算轉換成了O(n)的鏈表遍歷，從而導致字典的增刪改查(CRUD)越來越低效，這個時候redis會利用dict結構中的dictht[1]擴充一個新的buckets(調用dictExpand)，然后慢慢將dictht[0]的節點遷移至dictht[1]、用dictht[1]替換掉dictht[0] (調用dictRehash)。
具體擴充過程如下：

1.調用dictAdd為dict添加一個dictEntry節點。

2.調用_dictKeyIndex找到應該放置在buckets的哪個索引里。順便調用_dictExpandIfNeeded判斷是否需要擴充 dictht[1]。

3.若滿足條件：dictht[0]的dictEntry節點數/buckets的索引數>=1則調用dictExpand，若dictEntry節點數/buckets的索引數>=dict_force_resize_ratio(默認是5)，則強制執行dictExpand擴充dictht[1]。

需要注意的是上面的條件不是rehash的條件，而是擴充dictht[1]并打開dict rehash開關的條件。(因為rehash不是一次性完成的，若dictEntry節點非常多，rehash過程會進行很久從而block其他操作。所以redis采用了漸進rehash，分步進行，下文講rehash方式時會詳細介紹)。dictExpand做的只是把dictht[1]的buckets擴充到合適的大小，再把dict的rehashidx從-1置為0(打開rehash開關)。打開rehash開關之后該dict每次增刪改查(CRUD)都會執行一次rehash，把dictht[0]的buckets中的一個索引里的鏈表移動到dictht[1]。rehash的條件是rehashidx是否為-1。
放源碼:

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

//判斷dictht[1]是否需要擴充(并將dict調整為正在rehash狀態)；若dict剛創建，則擴充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. */
    //這是為剛創建的dict準備的，d->ht[0].size == 0時調用dictExpand只會擴充dictht[0]，不會改變dict的rehash狀態
    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時如果全局變量dict_can_resize為1則expand，
        //或者節點數/bucket數超過dict_force_resize_ratio(5)則擴充
        return dictExpand(d, d->ht[0].used*2);buckets大小擴充至 dict已使用節點的2倍的下一個2^n。假如used=4，buckets會擴充到8；used=5，buckets會擴充到16
    }
    return DICT_OK;
}

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

    /* 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)//如果當前使用的bucket數目大于想擴充之后的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) {//剛創建的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;//設置rehash狀態為正在進行rehash
    return DICT_OK;
}

畫圖分析一下擴充流程:
假設一個dict已經有4個dictEntry節點(value分別為"a","b","c","d")，根據key的不同，存放在buckets的不同索引下。

現在如果我們想添加一個dictEntry，由于d->ht[0].used >= d->ht[0].size (4>=4)，滿足了擴充dictht[1]的條件，會執行dictExpand。根據擴充規則，dictht[1]的buckets會擴充到8個槽位。

之后再將要添加的dictEntry加入到dictht[1]的buckets中的某個索引下，不過這個操作不屬于dictExpand，不展開了。
擴充之后的dict的成員變量rehashidx被賦值為0，此后每次CRUD都會執行一次被動rehash把dictht[0]的buckets中的一個鏈表遷移到dictht[1]中，直到遷移完畢。

剛才提到了被動rehash，實際上dict的rehash分為兩種方式:

主動方式：調用dictRehashMilliseconds執行一毫秒。在redis的serverCron里調用，看名字就知道是為redis服務端準備的定時事件，每次執行1ms的dictRehash，簡單粗暴。。

被動方式：字典的增刪改查(CRUD)調用dictAdd，dicFind，dictDelete，dictGetRandomKey等函數時，會調用_dictRehashStep，遷移buckets中的一個非空bucket。

放上源碼:

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

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

上面可以看出，不論是哪種rehash方式，底層都是通過dictRehash實現的，它是字典rehash的核心代碼。

dictRehash有兩個參數，d是rehash的dict指針，n是需要遷移到dictht[1]的非空桶數目；返回值0表示rehash完畢，否則返回1。

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

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

            d->ht[0].used--;//老dictht的used(節點數)-1
            d->ht[1].used++;//新dictht的used(節點數)+1
            de = nextde;
        }
        d->ht[0].table[d->rehashidx] = NULL;//當前bucket已經完全移走
        d->rehashidx++;//下一個bucket
    }

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

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

拿上面的圖作為的例子調用一次dictRehash(d, 1)，會產生如下布局:

之前a和b的放在dictht[0]的同一個buckets索引[0]下，但是經過rehash，h = dictHashKey(d, de->key) & d->ht[1].sizemask，h可能依舊為0，也有可能變為4。ps:如果兩個dictEntry仍然落在同一個索引下，它倆順序會顛倒。

rehashidx+1

返回1 More to rehash

若在此基礎上在執行一次dictRehash(d, 1)，則會跳過索引為1的那個空bucket，遷移下一個bucket。

有了rehash的基本認識，下面就可以說說redis字典支持的一些常規操作了：
redis用dictCreate創建并初始化一個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;
}

需要注意的是創建初始化一個dict時并沒有為buckets分配空間，table是賦值為null的。只有在往dict里添加dictEntry節點時才會為buckets分配空間，真正意義上創建一張hash表。
執行dictCreate后會得到如下布局：

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

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

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

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

    /* Get the index of the new element, or -1 if
     * the element already exists. */
    if ((index = _dictKeyIndex(d, key)) == -1)//計算這個key在當前dict應該放到bucket的哪個索引里,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()時已經確認過是哪張dictht,但是調用者沒辦法知道，所以再確認一下
    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)//根據dict和key返回這個key該存放的buckets的索引（但是用哪個dictht(ht[0]或ht[1])上層調用者是未知的）,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索引下的第一個dictEntry的地址
        while(he) {//遍歷一遍這個dictEntry鏈表
            if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經存在,返回-1
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;//不在rehash時，直接跳出循環不做第二個dictht[1]的計算
    }
    return idx;
}

主要分為以下幾個步驟:

1.根據key的hash值找到應該存放的位置(buckets索引)。

2.若dict是剛創建的還沒有為bucekts分配內存，則會在找位置(_dictKeyIndex)時調用_dictExpandIfNeeded，為dictht[0]expand一個大小為4的buckets；若dict正好到了expand的時機，則會expand它的dictht[1]，并將rehashidx置為0打開rehash開關，_dictKeyIndex返回的會是dictht[1]的索引。

3.申請一個dictEntry大小的內存插入到buckets對應索引下的鏈表頭部，并給dictEntry設置next指針和key。

4.為dictEntry設置value

dict刪除函數主要有三個，從低到高依次刪除dictEntry、dictht、dict。

dictDelete在redis在字典里的作用是刪除一個dictEntry并釋放dictEntry成員key和成員v指向的內存；

_dictClear刪除并釋放一個dict的指定dictht；

dictRelease刪除并釋放整個dict。

//刪除dictEntry并釋放dictEntry成員key和成員v指向的內存
int dictDelete(dict *ht, const void *key) {
    return dictGenericDelete(ht,key,0);
}
static int dictGenericDelete(dict *d, const void *key, int nofree)//刪除一個dictEntry節點，nofree參數指定是否釋放這個節點的key和val的內存(如果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);//被動rehash一次
    h = dictHashKey(d, key);

    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;//找到key對應的bucket索引
        he = d->ht[table].table[idx];//索引的第一個dictEntry節點指針
        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，則不查第二個table(dictht[1])
    }
    return DICT_ERR; /* not found */
}

//刪除一個dict的指定dictht，釋放dictht的table內相關的全部內存，并reset dictht
int _dictClear(dict *d, dictht *ht, void(callback)(void *)) {//傳遞dict指針是為了調用dictType的相關函數,dictFreeVal里會調
    unsigned long i;

    /* Free all the elements */
    for (i = 0; i < ht->size && ht->used > 0; i++) {//buckets大小，dictEntry使用數
        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 */
}

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

//修改一個dictEntry的val，也是一種添加dictEntry的方式，如果dictAdd失敗(key已存在)則replace這個dictEntry的val
int dictReplace(dict *d, void *key, void *val)//用新val取代一個dictEntry節點的舊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)//試著加一個新dictEntry，失敗則說明key已存在
        return 1;
    /* It already exists, get the entry */
    entry = dictFind(d, key);//創建節點失敗則一定能找到這個已經存在了的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節點,auxentry用來刪除(釋放)val
    dictSetVal(d, entry, val);//替換val的操作
    dictFreeVal(d, &auxentry);//考慮val可能是一個指針，指針指向的內容不會被刪除，所以調用這個dict的type類里的dictFreeVal釋放掉那塊內存
    return 0;
}

代碼里還有一個dictReplaceRaw函數，這個函數跟replace沒啥關系，只是封裝了一下dictAddRaw，沒有替換的功能。

//返回dictEntry的地址
dictEntry *dictFind(dict *d, const void *key)//會執行被動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的時候也會被動rehash
    h = dictHashKey(d, key);
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;//先計算當前buckets中key應存放的索引
        he = d->ht[table].table[idx];//buckets 的idx索引下的第一個dictEntry的地
        while(he) {//遍歷查找該鏈表
            if (key==he->key || dictCompareKeys(d, key, he->key))//如果key已經存在,返回-1
                return he;
            he = he->next;
        }
        if (!dictIsRehashing(d)) return NULL;//不在rehash時，直接跳出循環不在dictht[1]里查找
    }
    return NULL;
}

介紹一下字典的迭代器
redis字典的迭代器分為兩種，一種是safe迭代器另一種是unsafe迭代器:
safe迭代器在迭代的過程中用戶可以對該dict進行CURD操作，unsafe迭代器在迭代過程中用戶只能對該dict執行迭代操作。

上文說過每次執行CURD操作時，如果dict的rehash開關已經打開，則會執行一次被動rehash操作將dictht[0]的一個鏈表遷移到dictht[1]上。這時若迭代器進行迭代操作會導致重復迭代幾個剛被rehash到dictht[1]的dictEntry節點。那么一邊迭代一遍CRUD，這是怎么實現的呢？

redis在dict結構里增加一個iterator成員，用來表示綁定在當前dict上的safe迭代器數量，dict每次CRUD執行_dictRehashStep時判斷一下是否有綁定safe迭代器，如果有則不進行rehash以免擾亂迭代器的迭代，這樣safe迭代時字典就可以正常進行CRUD操作了。

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

unsafe迭代器在執行迭代過程中不允許對dict進行其他操作，如何保證這一點呢？

redis在第一次執行迭代時會用dictht[0]、dictht[1]的used、size、buckets地址計算一個fingerprint(指紋)，在迭代結束后釋放迭代器時再計算一遍fingerprint看看是否與第一次計算的一致，若不一致則用斷言終止進程，生成指紋的函數如下:

//unsafe迭代器在第一次dictNext時用dict的兩個dictht的table、size、used進行hash算出一個結果
//最后釋放iterator時再調用這個函數生成指紋，看看結果是否一致，不一致就報錯.
//safe迭代器不會用到這個
long long dictFingerprint(dict *d) {
    long long integers[6], hash = 0;
    int j;

    integers[0] = (long) d->ht[0].table;//把指針類型轉換成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的定義:

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

接下來介紹迭代器相關函數

//默認是new一個unsafe迭代器
dictIterator *dictGetIterator(dict *d)//獲取一個iterator就是為這個dict new一個迭代器
{
    //不設置成員變量fingerprint，在dictNext的時候才設置。
    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創建一個unsafe迭代器：dictGetIterator()
為指定dict創建一個safe迭代器：dictGetSafeIterator()
需要注意的是創建safe迭代器時并不會改變dict結構里iterator成員變量的計數，只有迭代真正發生的時候才會+1 表明該dict綁定了一個safe迭代器。

dictEntry *dictNext(dictIterator *iter)//如果下一個dictEntry不為空，則返回。為空則繼續找下一個bucket的第一個dictEntry
{
    while (1) {
        if (iter->entry == NULL) {//新new的dictIterator的entry是null，或者到達一個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迭代器的指紋，只進行一次
            }
            iter->index++;//buckets的下一個索引
            if (iter->index >= (long) ht->size) {
                //如果buckets的索引大于等于這個buckets的大小，則這個buckets迭代完畢
                
                if (dictIsRehashing(iter->d) && iter->table == 0) {//當前用的dictht[0]
                    //考慮rehash，換第二個dictht 
                    iter->table++;
                    iter->index = 0;//index復原成0，從第二個dictht的第0個bucket迭代
                    ht = &iter->d->ht[1];//設置這個是為了rehash時更新下面的iter->entry
                } else {
                    break;//迭代完畢了
                }
            }
            iter->entry = ht->table[iter->index];//更新entry為下一個bucket的第一個節點
        } 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迭代器會禁止rehash，但在迭代時有可能已經rehash了一部分，所以迭代器也會遍歷在dictht[1]中的所有dictEntry。

前面說的safe迭代器和unsafe迭代器都是建立在不能rehash的前提下。要通過這種迭代的方式遍歷所有節點會停止該dict的被動rehash，阻止了rehash的正常進行。dictScan就是用來解決這種問題的，它可以在不停止rehash的前提下遍歷到所有dictEntry節點，不過也有非常小的可能性返回重復的節點，具體如何做到的可能得另花大量篇幅介紹，有興趣可以借助這篇博客理解。