字典本身就是很常見的數(shù)據(jù)結(jié)構(gòu)之一，在Redis中，Redis數(shù)據(jù)庫就是使用字典來作為底層實(shí)現(xiàn)的，除了用來表示數(shù)據(jù)庫之外，字典還是哈希鍵的底層實(shí)現(xiàn)之一。

建議閱讀：
1、字典部分源碼研究見： wenmingxing Redis源碼研究之dict

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

Redis的字典使用哈希表作為底層實(shí)現(xiàn)。

1.1 哈希表

Redis字典所使用的哈希表結(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è)dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對。

size屬性記錄了哈希表的大小，即table數(shù)組的大小，而used屬性則記錄了哈希表目前已有鍵值對的數(shù)量。

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

下圖展示了一個(gè)大小為4的空哈希表：

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

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

typedef struct dictEntry {

    // 鍵
    void *key;

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

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

} dictEntry;

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

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

如下圖表示一個(gè)完成的哈希表：

1.3 字典

Redis中的字典結(jié)果如下：

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屬性是針對不同類型的鍵值對，而創(chuàng)建多態(tài)字典而設(shè)置的：
type屬性是一個(gè)指向dictType結(jié)構(gòu)的指針，每個(gè)dictType結(jié)構(gòu)保存了一組用于操作特定類型鍵值對的函數(shù)，Redis會為用途不同的字典設(shè)置不同類型的特定函數(shù)。
而privadata屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。

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

另一個(gè)與rehash有關(guān)的就是rehashidx屬性，它積累了rehash目前的進(jìn)度，如果沒有進(jìn)行rehash，則它的值為-1。

下圖為一個(gè)普通狀態(tài)下的字典結(jié)構(gòu)：

II、哈希算法

將一個(gè)新的鍵值對添加到字典里面的時(shí)候，程序需要先根據(jù)鍵值對上面的鍵來計(jì)算出哈希值和索引值，然后再根據(jù)索引值，將包含新鍵值對的哈希表節(jié)點(diǎn)放到哈希數(shù)組的指定索引上面。

Redis計(jì)算哈希值和索引值的方法如下：

# 使用字典設(shè)置的哈希函數(shù)，計(jì)算鍵 key 的哈希值
hash = dict->type->hashFunction(key);

# 使用哈希表的 sizemask 屬性和哈希值，計(jì)算出索引值
# 根據(jù)情況不同， ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

下面舉例說明一個(gè)完整的添加鍵值對<k0, v0>過程：

1. 首先程序會先使用語句hash = dict->type->hashFunction(k0);計(jì)算的處k0的哈希值。
2. 假設(shè)計(jì)算出的哈希值為8，則程序繼續(xù)index = hash & dict->ht[0].sizemask = 8 & 3 = 0;計(jì)算得到k0的索引值為0，這表示包含這個(gè)鍵值對的節(jié)點(diǎn)應(yīng)該放置到哈希表數(shù)組的索引0位置上。
   

tip： Redis使用MurmurHash2算法來計(jì)算鍵的哈希值。

III、解決鍵沖突

Redis哈希表使用鏈地址法來解決鍵沖突，每個(gè)哈希表節(jié)點(diǎn)都有一個(gè)next指針，多個(gè)哈希表節(jié)點(diǎn)可以用next構(gòu)成一個(gè)單向鏈表，被分配到同一個(gè)索引上的節(jié)點(diǎn)可以用這個(gè)單向鏈表連接起來，從而解決鍵沖突問題。

下面的例子說明一個(gè)解決鍵沖突的實(shí)例：

另外因?yàn)閐ictEntry節(jié)點(diǎn)組成的鏈表沒有指向鏈表表尾的指針，為了考慮速度，程序總是將新節(jié)點(diǎn)添加到鏈表的表頭位置（這樣添加節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(1)）。

IV、rehash

隨著操作的不斷進(jìn)行，哈希表保存的鍵值對會逐漸增多或減少，為了讓哈希表負(fù)載因子維持在一個(gè)合理范圍之內(nèi)，當(dāng)哈希表保存的鍵值對太多或太少時(shí)，程序要對哈希表的大小進(jìn)行相應(yīng)的擴(kuò)展或收縮。

Redis對字典的哈希表執(zhí)行rehash的步驟如下：

1. 為字典的ht[1]哈希表分配空間，這個(gè)空間大小取決于要執(zhí)行的操作：
   如果執(zhí)行的是擴(kuò)展操作，則ht[1]的大小為第一個(gè)大于等于等于ht[0].used*2的2^n；
   如果執(zhí)行的收縮操作，則ht[1]的大小為第一個(gè)大于等于ht[0].used的2^n；

2. 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面：rehash指的是重新計(jì)算鍵的哈希值和索引值，然后將鍵值對放置到ht[1]的指定位置上。

3. 當(dāng)ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]，將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)建一個(gè)空白哈希表，為下一次rehash做準(zhǔn)備。

下面為一個(gè)rehash的實(shí)例 ：

哈希表的擴(kuò)展與收縮
當(dāng)以下條件中任意一個(gè)被滿足時(shí)，程序會自動開始對哈希表執(zhí)行擴(kuò)展操作：

1. 服務(wù)器目前沒有執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于1。
2. 服務(wù)器正在執(zhí)行BGSAVE或BGREWRITEAOF命令，并且哈希表負(fù)載因子大于等于5。

區(qū)分這兩種情況的目的在于，因?yàn)閳?zhí)行BGSAVE與BGREWRITEAOF過程中，Redis都需要創(chuàng)建子進(jìn)程，而大多數(shù)操作系統(tǒng)都采用寫時(shí)復(fù)制技術(shù)來優(yōu)化子進(jìn)程使用效率，所以在子進(jìn)程存在期間，服務(wù)器會提高執(zhí)行擴(kuò)展操作所需的負(fù)載因子，從而盡可能避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展操作，這可以避免不必要的內(nèi)存寫入，最大限度的節(jié)約空間。

另一方面，當(dāng)哈希表負(fù)載因子小于0.1時(shí)，程序自動開始對哈希表執(zhí)行收縮操作。

V、漸進(jìn)式rehash

Redis中的rehash動作并不是一次性、集中式完成的，而是分多次、漸進(jìn)式的完成的。

這樣做的目的是，如果服務(wù)器中包含很多鍵值對，要一次性的將這些鍵值對全部rehash到ht[1]的話，龐大的計(jì)算量可能導(dǎo)致服務(wù)器在一段時(shí)間內(nèi)停止服務(wù)于。

為了避免這種影響，Redis采用了漸進(jìn)式Redis：

1. 為ht[1]分配空間，讓字典同時(shí)持有ht[0]和ht[1]兩個(gè)哈希表。
2. 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并將它置為0，表示rehash工作開始。
3. 在rehash進(jìn)行期間，每次對字典執(zhí)行添加、刪除、查找或者更新操作時(shí)，程序除了執(zhí)行指定操作以外，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]中，當(dāng)rehash工作完成之后，程序?qū)ehashidx屬性的值+1。
4. 隨著字典操作的不斷進(jìn)行，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]的所有鍵值對都被rehash到ht[1]上，這時(shí)將rehashidx屬性設(shè)為-1，表示rehash完成。

漸進(jìn)式rehash的好處在于其采取分而治之的方式，將rehash鍵值對所需要的計(jì)算工作均攤到字典的每個(gè)添加、刪除、查找和更新操作上，從而避免了集中式rehash而帶來的龐大計(jì)算量。

下面為一個(gè)漸進(jìn)式rehash的實(shí)例：

漸進(jìn)式rehash執(zhí)行期間的哈希表操作
因?yàn)樵跐u進(jìn)式rehash的過程中，字典會同時(shí)使用ht[0]和ht[1]兩個(gè)哈希表，所以在漸進(jìn)式rehash進(jìn)行期間，字典的刪除、查找、更新等操作都是在兩個(gè)表上進(jìn)行的。

例如，查找操作會先在ht[0]上進(jìn)行，如果沒找到再在ht[1]上進(jìn)行。

添加操作的鍵值對會一律保存到ht[1]中，這一措施保證ht[0]包含的鍵值對只會減少不會增加。

VI、字典API

【參考】
[1] 《Redis的設(shè)計(jì)與實(shí)現(xiàn)》

歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明出處wenmingxing Redis之字典