Redis 的字典使用哈希表作為底層實(shí)現(xiàn)， 一個哈希表里面可以有多個哈希表節(jié)點(diǎn)， 而每個哈希表節(jié)點(diǎn)就保存了字典中的一個鍵值對。

接下來的三個小節(jié)將分別介紹 Redis 的哈希表、哈希表節(jié)點(diǎn)、以及字典的實(shí)現(xiàn)。

哈希表

Redis 字典所使用的哈希表由 dict.h/dictht 結(jié)構(gòu)定義：

typedef struct dictht {

    // 哈希表數(shù)組
    dictEntry **table;

    // 哈希表大小
    unsigned long size;

    // 哈希表大小掩碼，用于計(jì)算索引值
    // 總是等于 size - 1
    unsigned long sizemask;

    // 該哈希表已有節(jié)點(diǎn)的數(shù)量
    unsigned long used;

} dictht;

table 屬性是一個數(shù)組， 數(shù)組中的每個元素都是一個指向 dict.h/dictEntry 結(jié)構(gòu)的指針， 每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對。

size 屬性記錄了哈希表的大小， 也即是 table 數(shù)組的大小， 而 used 屬性則記錄了哈希表目前已有節(jié)點(diǎn)（鍵值對）的數(shù)量。

sizemask 屬性的值總是等于 size - 1 ， 這個屬性和哈希值一起決定一個鍵應(yīng)該被放到 table 數(shù)組的哪個索引上面。

圖 4-1 展示了一個大小為 4 的空哈希表 （沒有包含任何鍵值對）。

哈希表節(jié)點(diǎn)

哈希表節(jié)點(diǎn)使用 dictEntry 結(jié)構(gòu)表示， 每個 dictEntry 結(jié)構(gòu)都保存著一個鍵值對：

typedef struct dictEntry {

    // 鍵
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;

    // 指向下個哈希表節(jié)點(diǎn)，形成鏈表
    struct dictEntry *next;

} dictEntry;

key 屬性保存著鍵值對中的鍵， 而 v 屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個 uint64_t 整數(shù)， 又或者是一個 int64_t 整數(shù)。

next 屬性是指向另一個哈希表節(jié)點(diǎn)的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突（collision）的問題。

舉個例子， 圖 4-2 就展示了如何通過 next 指針， 將兩個索引值相同的鍵 k1 和 k0 連接在一起。

字典

Redis 中的字典由 dict.h/dict 結(jié)構(gòu)表示：

typedef struct dict {

    // 類型特定函數(shù)
    dictType *type;

    // 私有數(shù)據(jù)
    void *privdata;

    // 哈希表
    dictht ht[2];

    // rehash 索引
    // 當(dāng) rehash 不在進(jìn)行時，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

type 屬性和 privdata 屬性是針對不同類型的鍵值對， 為創(chuàng)建多態(tài)字典而設(shè)置的：

• type 屬性是一個指向 dictType 結(jié)構(gòu)的指針， 每個 dictType 結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對的函數(shù)， Redis 會為用途不同的字典設(shè)置不同的類型特定函數(shù)。
• 而 privdata 屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。

typedef struct dictType {

    // 計(jì)算哈希值的函數(shù)
    unsigned int (*hashFunction)(const void *key);

    // 復(fù)制鍵的函數(shù)
    void *(*keyDup)(void *privdata, const void *key);

    // 復(fù)制值的函數(shù)
    void *(*valDup)(void *privdata, const void *obj);

    // 對比鍵的函數(shù)
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);

    // 銷毀鍵的函數(shù)
    void (*keyDestructor)(void *privdata, void *key);

    // 銷毀值的函數(shù)
    void (*valDestructor)(void *privdata, void *obj);

} dictType;

ht 屬性是一個包含兩個項(xiàng)的數(shù)組， 數(shù)組中的每個項(xiàng)都是一個 dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進(jìn)行 rehash 時使用。

除了 ht[1] 之外， 另一個和 rehash 有關(guān)的屬性就是 rehashidx ： 它記錄了 rehash 目前的進(jìn)度， 如果目前沒有在進(jìn)行 rehash ， 那么它的值為 -1 。

圖 4-3 展示了一個普通狀態(tài)下（沒有進(jìn)行 rehash）的字典：