閱讀本文之前要了解的兩件事情，第一，Redis是一種Key-Value數(shù)據(jù)庫，第二，字典是一種保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)，

Redis字典

。所以不難猜出字典在Redis中應(yīng)用一定非常廣泛，實際上，Redis數(shù)據(jù)庫的底層實現(xiàn)就是字典，對數(shù)據(jù)庫的增刪查改也是構(gòu)建在對字典的操作上，那么想要深入理解Redis，字典的解密是必不可少的，接下來，就讓我們一層一層解開指點的面紗，看看它的真面目。

    首先看看Redis中有哪些地方使用到了字典

    一， 數(shù)據(jù)庫鍵空間

    Redis是一個鍵值對數(shù)據(jù)庫服務(wù)器，服務(wù)器中的每個數(shù)據(jù)庫都是一個RedisDB結(jié)構(gòu)，其中RedisDb結(jié)構(gòu)的dict字典保存了數(shù)據(jù)庫中的所有鍵值對，我們將這個字典稱為鍵空間(key space)，鍵空間和用戶直接所見的數(shù)據(jù)庫是直接對應(yīng)的

    二， Expires字典

    Redis數(shù)據(jù)庫結(jié)構(gòu)是一個RedisDb結(jié)構(gòu)，有一個屬性expires也是字典，這個字典中保存了數(shù)據(jù)庫中所有鍵的過期時間，我們稱這個字典叫做過期字典

    下面貼出RedisDb的數(shù)據(jù)結(jié)構(gòu)，加深了理解。

    三， 字典是Hash類型的底層實現(xiàn)之一

    這里之所以說是之一，是應(yīng)為Hash類型的實現(xiàn)可以是多種類型，在不同的場景下可以是不同的類型，但一個哈希鍵中包含的鍵值對比較多，有或者是鍵值對中元素都是比較長的字符串的時候，就會使用字典作為底層實現(xiàn)，否則就是壓縮列表作為底層實現(xiàn)。

    【注意】鍵空間中的鍵和過期字典中的鍵都指向都一個鍵對象，所以不會出現(xiàn)任何重復(fù)對象，也不會浪費內(nèi)存空間。

    然后我們來了解一下在Redis中字典是如何實現(xiàn)的。

    字典的定義在dict.h/dict中給出了，如下：

typedef struct dict {    dictType *type;    void *privdata;    dictht ht[2];    long rehashidx; /* rehashing not in progress if rehashidx == -1 */    int iterators; /* number of iterators currently running */} dict;

這是一個哈希表，table數(shù)組中的每個元素都是指向一個dictEntry結(jié)構(gòu)的指針，size是哈希表的大小，也就是table數(shù)組的大小，sizemask屬性總是等于size-1 ，sizemask和哈希值一起決定將一個鍵應(yīng)該被放到那個數(shù)組上，used表示目前哈希表有多少個節(jié)點，used/size 是一個哈希表的負(fù)載因子，這個因子決定了什么時候后對哈希表進(jìn)行擴(kuò)展和收縮。

   

typedef struct dictht {    dictEntry **table;    unsigned long size;    unsigned long sizemask;    unsigned long used;} dictht;

    下面是一個哈希表節(jié)點，每個dictEntry結(jié)構(gòu)都保持著一個鍵值對，其中next指針可以將多個哈希值相同的鍵值對連接在一起，一次來解決鍵沖突的問題(這里可以引申出哈希函數(shù)以及哈希沖突解決方案，Redis中使用的解決方案是鏈地址法，就是，如果多個值通過哈希函數(shù)得到的哈希值是相同的，那么就鏈接到這個地址后，還有一種解決哈希沖突的方案，就是尋地址法，就是當(dāng)出現(xiàn)哈希沖突的時候，對鍵值對在進(jìn)行一個哈希函數(shù)，得到一個沒有被占用的地址為止，這兩種方案各有利弊，鏈地址法可能會退化成一個鏈表，尋地址法可能在后期插入時，全是沖突)

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

    還有一個需要說的地方，就是哈希表的rehash

    隨著操作的不斷執(zhí)行，一個哈希表中保存的鍵值對會越來越多或者是越來越少，哈希表中鍵值對數(shù)量過多或者過少都是不好的，過多，就會相當(dāng)于是多個鏈表，過少也不好，查找的命中率也會很低，將哈希表的負(fù)載因子(used/size)維持在一個范圍之類是最好的，所以，當(dāng)哈希表的數(shù)量過大或者過小的時候，程序會對哈希表進(jìn)行擴(kuò)展或者收縮，

    擴(kuò)展好理解，如果size=4 ，但是used=8，相當(dāng)于每個鍵的后面都有個鏈，這樣查找起來是費勁的，這個時候可以通過Rehash來進(jìn)行完成，注意dict數(shù)據(jù)結(jié)構(gòu)中的那個

    dictht ht[2]，這里是兩個dictht，其中ht[1]是空閑的，在進(jìn)行擴(kuò)展的時候現(xiàn)將ht[1]擴(kuò)展成ht[0]的兩倍，然后將ht[0]中的鍵值對一個一個哈希到ht[1]中去，最后將ht[1]設(shè)置為ht[0]

    這里需要注意的是rehash的時機(jī)，一般是負(fù)載因子大于5的時候擴(kuò)展，負(fù)載因子小于0.1的時候收縮，還有一個問題是字典中有個屬性是rehashidx，這個屬性標(biāo)志rehash的狀態(tài)，如果是0，表示rehash正式開始，然后沒rehash一個鍵值對，就將這個值加一，當(dāng)ht[0]的值全部被轉(zhuǎn)移到ht[1]的時候，就將這個值設(shè)置成-1，表示rehash操作完成，

電腦資料

《Redis字典》(http://www.msguai.com)。

    其實還有很多要說的，比如漸進(jìn)式rehash，漸進(jìn)式就說說rehash過程不是一次性完成的，而是分多次，漸進(jìn)式完成的，在rehash過程中，所有的刪除，查找，更新都會在兩個哈希表中進(jìn)行，例如，如果查找一個元素，ht[0]中沒有，那么就去ht[1]中查找，新添加的一律都是添加到ht[1]中，ht[0]中不再進(jìn)行任何添加操作