字典簡介

字典， 又稱符號表（symbol table）、關(guān)聯(lián)數(shù)組（associative array）或者映射（map）， 是一種用于保存鍵值對（key-value pair）的抽象數(shù)據(jù)結(jié)構(gòu)。
在字典中， 一個鍵（key）可以和一個值（value）進行關(guān)聯(lián)（或者說將鍵映射為值）， 這些關(guān)聯(lián)的鍵和值就被稱為鍵值對。

字典中的每個鍵都是獨一無二的， 程序可以在字典中根據(jù)鍵查找與之關(guān)聯(lián)的值， 或者通過鍵來更新值， 又或者根據(jù)鍵來刪除整個鍵值對， 等等。

字典經(jīng)常作為一種數(shù)據(jù)結(jié)構(gòu)內(nèi)置在很多高級編程語言里面， 但 Redis 所使用的 C 語言并沒有內(nèi)置這種數(shù)據(jù)結(jié)構(gòu)， 因此 Redis 構(gòu)建了自己的字典實現(xiàn)。

字典在 Redis 中的應(yīng)用相當廣泛， 比如 Redis 的數(shù)據(jù)庫就是使用字典來作為底層實現(xiàn)的， 對數(shù)據(jù)庫的增、刪、查、改操作也是構(gòu)建在對字典的操作之上的。
如，當我們執(zhí)行命令：

redis> SET msg "hello world"
OK

在數(shù)據(jù)庫中創(chuàng)建一個鍵為 "msg" ， 值為 "hello world" 的鍵值對時， 這個鍵值對就是保存在代表數(shù)據(jù)庫的字典里面的。

字典的實現(xiàn)

Redis 的字典使用哈希表作為底層實現(xiàn)， 一個哈希表里面可以有多個哈希表節(jié)點， 而每個哈希表節(jié)點就保存了字典中的一個鍵值對。接下來的三個小節(jié)將分別介紹 Redis 的哈希表、哈希表節(jié)點、以及字典的實現(xiàn)。

• 哈希表

typedef struct dictht {
    dictEntry **table; /* 哈希表數(shù)組 */
    unsigned long size; /* 哈希表大小 */
    unsigned long sizemask; /*哈希表大小掩碼，用于計算索引值 總是等于 size - 1*/
    unsigned long used; /* 該哈希表已有節(jié)點的數(shù)量 */
} dictht;

1. table 屬性是一個數(shù)組， 數(shù)組中的每個元素都是一個指向 dict.h/dictEntry 結(jié)構(gòu)的指針， 每個 dictEntry 結(jié)構(gòu)保存著一個鍵值對。
2. size 屬性記錄了哈希表的大小， 也即是 table 數(shù)組的大小， 而 used 屬性則記錄了哈希表目前已有節(jié)點（鍵值對）的數(shù)量。
3. sizemask 屬性的值總是等于 size - 1 ， 這個屬性和哈希值一起決定一個鍵應(yīng)該被放到 table 數(shù)組的哪個索引上面。

• 哈希表節(jié)點

typedef struct dictEntry {
    void *key; /* 鍵 */
    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; /* 指向下個哈希表節(jié)點，形成鏈表，hash鍵沖突時才被用到 */
} dictEntry;

1. 哈希表節(jié)點使用dictEntry結(jié)構(gòu)表示， 每個dictEntry結(jié)構(gòu)都保存著一個鍵值對
2. key屬性保存著鍵值對中的鍵， 而v屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個uint64_t整數(shù)， 又或者是一個int64_t整數(shù)。
3. next屬性是指向另一個哈希表節(jié)點的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突（collision）的問題。

• 字典
  字典結(jié)構(gòu)用dict表示，此結(jié)構(gòu)能很方便的支持rehash

typedef struct dict {
    dictType *type; /* 類型特定函數(shù) */
    void *privdata; /* 私有數(shù)據(jù) */
    dictht ht[2]; /* 哈希表 */
    int rehashidx; /* rehash 索引 當 rehash 不在進行時，值為 -1 */
    int iterators; /* 目前正在運行的安全迭代器的數(shù)量 */
} dict;

1. type屬性和privdata屬性是針對不同類型的鍵值對， 為創(chuàng)建多態(tài)字典而設(shè)置的
2. ht屬性是一個包含兩個項的數(shù)組， 數(shù)組中的每個項都是一個dictht哈希表， 一般情況下， 字典只使用 ht[0] 哈希表， ht[1] 哈希表只會在對 ht[0] 哈希表進行 rehash 時使用
3. 除了 ht[1] 之外， 另一個和 rehash 有關(guān)的屬性就是rehashidx： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那么它的值為 -1 。

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

普通字典結(jié)構(gòu).png

哈希算法

當要將一個新的鍵值對添加到字典里面時， 程序需要先根據(jù)鍵值對的鍵計算出哈希值和索引值， 然后再根據(jù)索引值， 將包含新鍵值對的哈希表節(jié)點放到哈希表數(shù)組的指定索引上面。
Redis 計算哈希值和索引值的方法如下：

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

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

可以看出，redis對進入的字符串首先做一層hashFunction操作，將其轉(zhuǎn)換成unsigned int型, 再將其和hash表的sizemask做與操作，得到index。

圖4-4.png

圖4-5.png

解決沖突

當有兩個或以上數(shù)量的鍵被分配到了哈希表數(shù)組的同一個索引上面時， 我們稱這些鍵發(fā)生了沖突（collision）。

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

此處簡單，不再摘出書中例子。

rehash

隨著操作的不斷執(zhí)行， 哈希表保存的鍵值對會逐漸地增多或者減少， 為了讓哈希表的負載因子（load factor）維持在一個合理的范圍之內(nèi)， 當哈希表保存的鍵值對數(shù)量太多或者太少時， 程序需要對哈希表的大小進行相應(yīng)的擴展或者收縮。

擴展和收縮哈希表的工作可以通過執(zhí)行 rehash （重新散列）操作來完成， Redis 對字典的哈希表執(zhí)行 rehash 的步驟如下：

1. 為字典的 ht[1] 哈希表分配空間， 這個哈希表的空間大小取決于要執(zhí)行的操作， 以及 ht[0] 當前包含的鍵值對數(shù)量 （也即是 ht[0].used 屬性的值）：
   • 如果執(zhí)行的是擴展操作， 那么 ht[1] 的大小為第一個大于等于 ht[0].used * 2 的 2^n （2 的 n 次方冪）；
   • 如果執(zhí)行的是收縮操作， 那么 ht[1] 的大小為第一個大于等于 ht[0].used 的 2^n 。
2. 將保存在 ht[0] 中的所有鍵值對 rehash 到 ht[1] 上面： rehash 指的是重新計算鍵的哈希值和索引值， 然后將鍵值對放置到 ht[1] 哈希表的指定位置上。
3. 當 ht[0] 包含的所有鍵值對都遷移到了 ht[1] 之后 （ht[0] 變?yōu)榭毡恚?釋放 ht[0] ， 將 ht[1] 設(shè)置為 ht[0] ， 并在 ht[1] 新創(chuàng)建一個空白哈希表， 為下一次 rehash 做準備。

舉個例子， 假設(shè)程序要對圖 4-8 所示字典的 ht[0] 進行擴展操作， 那么程序?qū)?zhí)行以下步驟：

1. ht[0].used 當前的值為 4 ， 4 * 2 = 8 ， 而 8 （2^3）恰好是第一個大于等于 4 的 2 的 n 次方， 所以程序會將 ht[1] 哈希表的大小設(shè)置為 8 。 圖 4-9 展示了 ht[1] 在分配空間之后， 字典的樣子。
2. 將 ht[0] 包含的四個鍵值對都 rehash 到 ht[1] ， 如圖 4-10 所示。
3. 釋放 ht[0] ，并將 ht[1] 設(shè)置為 ht[0] ，然后為 ht[1] 分配一個空白哈希表，如圖 4-11 所示。

至此， 對哈希表的擴展操作執(zhí)行完畢， 程序成功將哈希表的大小從原來的 4 改為了現(xiàn)在的 8 。
圖 4-12 至圖 4-17 展示了一次完整的漸進式 rehash 過程， 注意觀察在整個 rehash 過程中， 字典的 rehashidx 屬性是如何變化的。

4-12.png

4-13.png

4-14.png

4-15.png

4-16.png

4-17.png

字典API