Redis 字典的實(shí)現(xiàn)

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

接下來(lái)的三個(gè)小節(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 屬性是一個(gè)數(shù)組， 數(shù)組中的每個(gè)元素都是一個(gè)指向 dict.h/dictEntry 結(jié)構(gòu)的指針， 每個(gè) dictEntry 結(jié)構(gòu)保存著一個(gè)鍵值對(duì)。

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

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

圖 4-1 展示了一個(gè)大小為 4 的空哈希表 （沒(méi)有包含任何鍵值對(duì)）。

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

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

typedef struct dictEntry {

    // 鍵
    void *key;

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

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

} dictEntry;

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

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

舉個(gè)例子， 圖 4-2 就展示了如何通過(guò) next 指針， 將兩個(gè)索引值相同的鍵 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)行時(shí)，值為 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

} dict;

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

• type 屬性是一個(gè)指向 dictType 結(jié)構(gòu)的指針， 每個(gè) dictType 結(jié)構(gòu)保存了一簇用于操作特定類型鍵值對(duì)的函數(shù)， Redis 會(huì)為用途不同的字典設(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);

    // 對(duì)比鍵的函數(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 屬性是一個(gè)包含兩個(gè)項(xiàng)的數(shù)組， 數(shù)組中的每個(gè)項(xiàng)都是一個(gè) dictht 哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會(huì)在對(duì) ht[0] 哈希表進(jìn)行 rehash 時(shí)使用。

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

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