我們平時用Redis的時候，只是了解到了它對外的一些結(jié)構(gòu)，如：string、list、set、hash、zset，但是我們卻很少能了解到Redis內(nèi)部用的存儲結(jié)構(gòu)，小編將在這篇文章和大家秀一下Redis中的一個內(nèi)部結(jié)構(gòu)——dict。

一、dict是什么

不知道大家在用Redis的時候有沒有注意到，我們在使用大多數(shù)Redis命令的時候，都會讓你輸入一個key，后面才會讓你輸入具體的值。

我們本篇文章所述的dict在Redis中最主要的作用就是用于維護(hù)Redis數(shù)據(jù)庫中所有Key、value映射的數(shù)據(jù)結(jié)構(gòu)，也就是我們在輸入set、zadd等命令時輸入的key與后面值的映射。321，上代碼。代碼來源(dict.h)。 如下代碼所示，dict結(jié)構(gòu)體里面有一個dictht 數(shù)組，dictht 里面的dictEntry 就是具體存放key、value映射關(guān)系的。

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; //  hashtable 容量
    unsigned long sizemask;  // size -1
    unsigned long used;  // hashtable 元素個數(shù)   used / size =1
} dictht;
typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];// ht[0] , ht[1] =null
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

小貼紙：dictEntry 中用到了union聯(lián)合體這種結(jié)構(gòu)。也就是多個變量的結(jié)構(gòu)同時使用一塊內(nèi)存區(qū)域，區(qū)域的取值大小為該結(jié)構(gòu)中長度最大的變量的值。這有利于減少內(nèi)存碎片，提高內(nèi)存利用率，在Java中的壓縮指針技術(shù)就用到了聯(lián)合體。

二、dict數(shù)據(jù)結(jié)構(gòu)

1.結(jié)構(gòu)梳理

我們仔細(xì)看上面代碼中的結(jié)構(gòu)，小編可以直接告訴你，其實它就是一個哈希表結(jié)構(gòu)，在Java中相當(dāng)于一個HashMap，因為Redis需要保證快速響應(yīng)，所以選擇哈希表作為存儲結(jié)構(gòu)是一個不錯的決定。我們這里只一起了解結(jié)構(gòu)中存具體數(shù)據(jù)的部分。

• dictEntry：其實它就是一個鏈表結(jié)構(gòu)，里面維護(hù)了key、value。
• dictht ：它維護(hù)了一個dictEntry 指針數(shù)組。 雖然我們?nèi)庋勰芸吹蕉x的是指針的指針，dictEntry **table。但其實指針的指針是指向了dictEntry 數(shù)組指針的首地址。Redis源碼里大多會這么用 table[index]。指針這塊有點(diǎn)繞，可以暫時直接認(rèn)為它就是一個指針數(shù)組。
• dict： dict里面維護(hù)了一個dictht ht[2] 數(shù)組，相當(dāng)于兩個dictht 結(jié)構(gòu)。為什么要存兩個dictht 結(jié)構(gòu)呢。因為既然是哈希表那就要涉及到擴(kuò)容，redis是單線程的，不可能一下子將所有的數(shù)據(jù)都轉(zhuǎn)移到新的哈希表中，這樣可能會造成服務(wù)長時間不可用，所以它退而求其次，選擇了"漸進(jìn)式擴(kuò)容"。

小貼紙：Redis中的漸進(jìn)式擴(kuò)容，采用的是在內(nèi)存中放置兩個哈希表結(jié)構(gòu)，無需擴(kuò)容時，使用的是哈希表0，在擴(kuò)容期間，將擴(kuò)容標(biāo)識設(shè)置為true，當(dāng)有新數(shù)據(jù)進(jìn)來的時候，發(fā)現(xiàn)正在擴(kuò)容，就會在將新數(shù)據(jù)直接放入哈希表1。而表0中的數(shù)據(jù)會在每次有請求命令并且請求的數(shù)據(jù)在表0中時，將請求命令涉及到的數(shù)據(jù)直接掛到表1上。 在擴(kuò)容期間如果執(zhí)行查找命令會查找表0+表1的數(shù)據(jù)。

當(dāng)然，Redis如果一直不執(zhí)行命令的話。它也會有一個后臺定時任務(wù)，對字典進(jìn)行主動搬遷，它不會對未完成的事置之不理

// 服務(wù)器定時任務(wù)
void databaseCron() {
    ...
    if (server.activerehashing) {
        for (j = 0; j < dbs_per_call; j++) {
            int work_done = incrementallyRehash(rehash_db);
            if (work_done) {
                /* If the function did some work, stop here, we'll do
                 * more at the next cron loop. */
                break;
            } else {
                /* If this db didn't need rehash, we'll try the next one. */
                rehash_db++;
                rehash_db %= server.dbnum;
            }
        }
    }
}

2. 擴(kuò)容條件

• 當(dāng)hash表中元素的個數(shù)等于數(shù)組長度時，就會開始擴(kuò)容，擴(kuò)容的新數(shù)組是原數(shù)組的2倍。
• 當(dāng)Redis發(fā)生其他情況沒有在元素個數(shù)等于數(shù)組長度時擴(kuò)容，那么Redis會有一個強(qiáng)制擴(kuò)容的條件，就是元素個數(shù)達(dá)到數(shù)組長度5倍時進(jìn)行強(qiáng)制擴(kuò)容。

/* Expand the hash table if needed */
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);

    /* 元素個數(shù)大于等于數(shù)組長度&&（能擴(kuò)容(bgsave時盡量不擴(kuò)容)或元素大于5倍時強(qiáng)制擴(kuò)容）
	 * static unsigned int 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))
    {
        return dictExpand(d, d->ht[0].used*2);
    }
    return DICT_OK;
}

3. 縮容條件

既然有擴(kuò)容，當(dāng)前就有縮容，要不占那么大內(nèi)存不是浪費(fèi)嗎？

• 當(dāng)元素小于數(shù)組長度的10%時進(jìn)行縮容。

int htNeedsResize(dict *dict) {
    long long size, used;

    size = dictSlots(dict);
    used = dictSize(dict);
    return (size > DICT_HT_INITIAL_SIZE &&
            (used*100/size < HASHTABLE_MIN_FILL));
}

dict結(jié)構(gòu)的實現(xiàn)相對來說比較簡單，本文就介紹到這。