Redis 字典

字典

字典（dictionary），又名映射（map）或關(guān)聯(lián)數(shù)組（associative array）， [http://en.wikipedia.org/wiki/Associative_array]是一種抽象數(shù)據(jù)結(jié)構(gòu)，由一集鍵值對(duì)（key-value pairs）組成，各個(gè)鍵值對(duì)的鍵各不相同，程序可以添加新的鍵值對(duì)到字典中，或者基于鍵進(jìn)行查找、更新或刪除等操作。

本章先對(duì)字典在 Redis 中的應(yīng)用進(jìn)行介紹，接著講解字典的具體實(shí)現(xiàn)方式，以及這個(gè)字典實(shí)現(xiàn)要解決的問(wèn)題，最后，以對(duì)字典迭代器的介紹作為本章的結(jié)束。

字典的應(yīng)用

字典在 Redis 中的應(yīng)用廣泛，使用頻率可以說(shuō)和 SDS 以及雙端鏈表不相上下，基本上各個(gè)功能模塊都有用到字典的地方。

其中，字典的主要用途有以下兩個(gè)：

1. 實(shí)現(xiàn)數(shù)據(jù)庫(kù)鍵空間（key space）；
2. 用作 Hash 類(lèi)型鍵的底層實(shí)現(xiàn)之一；

以下兩個(gè)小節(jié)分別介紹這兩種用途。

實(shí)現(xiàn)數(shù)據(jù)庫(kù)鍵空間

Redis 是一個(gè)鍵值對(duì)數(shù)據(jù)庫(kù)，數(shù)據(jù)庫(kù)中的鍵值對(duì)由字典保存：每個(gè)數(shù)據(jù)庫(kù)都有一個(gè)對(duì)應(yīng)的字典，這個(gè)字典被稱(chēng)之為鍵空間（key space）。

當(dāng)用戶(hù)添加一個(gè)鍵值對(duì)到數(shù)據(jù)庫(kù)時(shí)（不論鍵值對(duì)是什么類(lèi)型），程序就將該鍵值對(duì)添加到鍵空間；當(dāng)用戶(hù)從數(shù)據(jù)庫(kù)中刪除鍵值對(duì)時(shí)，程序就會(huì)將這個(gè)鍵值對(duì)從鍵空間中刪除；等等。

舉個(gè)例子，執(zhí)行 FLUSHDB [http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb] 可以清空鍵空間里的所有鍵值對(duì)數(shù)據(jù)：

redis> FLUSHDB
OK

執(zhí)行 DBSIZE [http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize] 則返回鍵空間里現(xiàn)有的鍵值對(duì)：

redis> DBSIZE
(integer) 0

還可以用 SET [http://redis.readthedocs.org/en/latest/string/set.html#set] 設(shè)置一個(gè)字符串鍵到鍵空間，并用 GET [http://redis.readthedocs.org/en/latest/string/get.html#get] 從鍵空間中取出該字符串鍵的值：

redis> SET number 10086
OK

redis> GET number
"10086"

redis> DBSIZE
(integer) 1

后面的《數(shù)據(jù)庫(kù)》一章會(huì)對(duì)鍵空間以及數(shù)據(jù)庫(kù)的實(shí)現(xiàn)作詳細(xì)的介紹，屆時(shí)將看到，大部分針對(duì)數(shù)據(jù)庫(kù)的命令，比如 DBSIZE [http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize] 、 FLUSHDB [http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb] 、 RANDOMKEY [http://redis.readthedocs.org/en/latest/key/randomkey.html#randomkey] ，等等，都是構(gòu)建于對(duì)字典的操作之上的；而那些創(chuàng)建、更新、刪除和查找鍵值對(duì)的命令，也無(wú)一例外地需要在鍵空間上進(jìn)行操作。

用作 Hash 類(lèi)型鍵的底層實(shí)現(xiàn)之一

Redis 的 Hash 類(lèi)型鍵使用以下兩種數(shù)據(jù)結(jié)構(gòu)作為底層實(shí)現(xiàn):

1. 字典；
2. 壓縮列表；

因?yàn)閴嚎s列表比字典更節(jié)省內(nèi)存，所以程序在創(chuàng)建新 Hash 鍵時(shí)，默認(rèn)使用壓縮列表作為底層實(shí)現(xiàn)，當(dāng)有需要時(shí)，程序才會(huì)將底層實(shí)現(xiàn)從壓縮列表轉(zhuǎn)換到字典。

當(dāng)用戶(hù)操作一個(gè) Hash 鍵時(shí)，鍵值在底層就可能是一個(gè)哈希表：

redis> HSET book name "The design and implementation of Redis"
(integer) 1

redis> HSET book type "source code analysis"
(integer) 1

redis> HSET book release-date "2013.3.8"
(integer) 1

redis> HGETALL book
1) "name"
2) "The design and implementation of Redis"
3) "type"
4) "source code analysis"
5) "release-date"
6) "2013.3.8"

《哈希表》章節(jié)給出了關(guān)于哈希類(lèi)型鍵的更多信息，并介紹了壓縮列表和字典之間的轉(zhuǎn)換條件。

介紹完了字典的用途，現(xiàn)在讓我們來(lái)看看字典數(shù)據(jù)結(jié)構(gòu)的定義。

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

實(shí)現(xiàn)字典的方法有很多種：

• 最簡(jiǎn)單的就是使用鏈表或數(shù)組，但是這種方式只適用于元素個(gè)數(shù)不多的情況下；
• 要兼顧高效和簡(jiǎn)單性，可以使用哈希表；
• 如果追求更為穩(wěn)定的性能特征，并希望高效地實(shí)現(xiàn)排序操作的話(huà)，則可使用更為復(fù)雜的平衡樹(shù)；

在眾多可能的實(shí)現(xiàn)中，Redis 選擇了高效、實(shí)現(xiàn)簡(jiǎn)單的哈希表，作為字典的底層實(shí)現(xiàn)。

dict.h/dict 給出了這個(gè)字典的定義：

/*
 * 字典
 *
 * 每個(gè)字典使用兩個(gè)哈希表，用于實(shí)現(xiàn)漸進(jìn)式 rehash
 */
typedef struct dict {

    // 特定于類(lèi)型的處理函數(shù)
    dictType *type;

    // 類(lèi)型處理函數(shù)的私有數(shù)據(jù)
    void *privdata;

    // 哈希表（2 個(gè)）
    dictht ht[2];

    // 記錄 rehash 進(jìn)度的標(biāo)志，值為 -1 表示 rehash 未進(jìn)行
    int rehashidx;

    // 當(dāng)前正在運(yùn)作的安全迭代器數(shù)量
    int iterators;

} dict;

以下是用于處理 dict 類(lèi)型的 API ，它們的作用及相應(yīng)的算法復(fù)雜度：

注意 dict 類(lèi)型使用了兩個(gè)指針，分別指向兩個(gè)哈希表。

其中，0 號(hào)哈希表（ht[0]）是字典主要使用的哈希表，而 1 號(hào)哈希表（ht[1]）則只有在程序?qū)?0 號(hào)哈希表進(jìn)行 rehash 時(shí)才使用。

接下來(lái)兩個(gè)小節(jié)將對(duì)哈希表的實(shí)現(xiàn)，以及哈希表所使用的哈希算法進(jìn)行介紹。

哈希表實(shí)現(xiàn)

字典所使用的哈希表實(shí)現(xiàn)由 dict.h/dictht 類(lèi)型定義：

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表節(jié)點(diǎn)指針數(shù)組（俗稱(chēng)桶，bucket）
    dictEntry **table;

    // 指針數(shù)組的大小
    unsigned long size;

    // 指針數(shù)組的長(zhǎng)度掩碼，用于計(jì)算索引值
    unsigned long sizemask;

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

} dictht;

table 屬性是個(gè)數(shù)組，數(shù)組的每個(gè)元素都是個(gè)指向 dictEntry 結(jié)構(gòu)的指針。

每個(gè) dictEntry 都保存著一個(gè)鍵值對(duì)，以及一個(gè)指向另一個(gè) dictEntry 結(jié)構(gòu)的指針：

/*
 * 哈希表節(jié)點(diǎn)
 */
typedef struct dictEntry {

    // 鍵
    void *key;

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

    // 鏈往后繼節(jié)點(diǎn)
    struct dictEntry *next;

} dictEntry;

next 屬性指向另一個(gè) dictEntry 結(jié)構(gòu)，多個(gè) dictEntry 可以通過(guò) next 指針串連成鏈表，從這里可以看出，dictht使用鏈地址法來(lái)處理鍵碰撞 [http://en.wikipedia.org/wiki/Hash_table#Separate_chaining]：當(dāng)多個(gè)不同的鍵擁有相同的哈希值時(shí)，哈希表用一個(gè)鏈表將這些鍵連接起來(lái)。

下圖展示了一個(gè)由 dictht 和數(shù)個(gè) dictEntry 組成的哈希表例子：

dictht |

如果再加上之前列出的 dict 類(lèi)型，那么整個(gè)字典結(jié)構(gòu)可以表示如下：

ht[2] | rehashidx: -1 | iterators: 0", fillcolor = "#A8E270"]; ht0 [label="dictht |

在上圖的字典示例中，字典雖然創(chuàng)建了兩個(gè)哈希表，但正在使用的只有 0 號(hào)哈希表，這說(shuō)明字典未進(jìn)行 rehash 狀態(tài)。

哈希算法

Redis 目前使用兩種不同的哈希算法：

1. MurmurHash2 32 bit 算法：這種算法的分布率和速度都非常好， 具體信息請(qǐng)參考 MurmurHash 的主頁(yè)： http://code.google.com/p/smhasher/ 。
2. 基于 djb 算法實(shí)現(xiàn)的一個(gè)大小寫(xiě)無(wú)關(guān)散列算法：具體信息請(qǐng)參考 http://www.cse.yorku.ca/~oz/hash.html 。

使用哪種算法取決于具體應(yīng)用所處理的數(shù)據(jù)：

• 命令表以及 Lua 腳本緩存都用到了算法 2 。
• 算法 1 的應(yīng)用則更加廣泛：數(shù)據(jù)庫(kù)、集群、哈希鍵、阻塞操作等功能都用到了這個(gè)算法。

創(chuàng)建新字典

dictCreate 函數(shù)創(chuàng)建并返回一個(gè)新字典：

dict *d = dictCreate(&hash_type, NULL);

d 的值可以用圖片表示如下：

ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="dictht |

新創(chuàng)建的兩個(gè)哈希表都沒(méi)有為 table 屬性分配任何空間：

• ht[0]->table 的空間分配將在第一次往字典添加鍵值對(duì)時(shí)進(jìn)行；
• ht[1]->table 的空間分配將在 rehash 開(kāi)始時(shí)進(jìn)行；

添加鍵值對(duì)到字典

根據(jù)字典所處的狀態(tài)，將給定的鍵值對(duì)添加到字典可能會(huì)引起一系列復(fù)雜的操作：

• 如果字典為未初始化（即字典的 0 號(hào)哈希表的 table 屬性為空），則程序需要對(duì) 0 號(hào)哈希表進(jìn)行初始化；
• 如果在插入時(shí)發(fā)生了鍵碰撞，則程序需要處理碰撞；
• 如果插入新元素，使得字典滿(mǎn)足了 rehash 條件，則需要啟動(dòng)相應(yīng)的 rehash 程序；

當(dāng)程序處理完以上三種情況之后，新的鍵值對(duì)才會(huì)被真正地添加到字典上。

整個(gè)添加流程可以用下圖表示：

key_exists_or_not; return_null_if_key_exists [label="返回 NULL ，\n表示添加失敗"]; key_exists_or_not -> return_null_if_key_exists [label="是"]; dict_empty_or_not [label="ht[0]\n 未分配任何空間？", shape=diamond, fillcolor = "#95BBE3"]; key_exists_or_not -> dict_empty_or_not [label="否"]; init_hash_table_one [label="初始化 ht[0]"]; dict_empty_or_not -> init_hash_table_one [label="是"]; init_hash_table_one -> need_rehash_or_not; need_rehash_or_not [label="需要 rehash ？", shape=diamond, fillcolor = "#95BBE3"]; dict_empty_or_not -> need_rehash_or_not [label="否"]; begin_incremental_rehash [label="開(kāi)始漸進(jìn)式 rehash "]; need_rehash_or_not -> begin_incremental_rehash [label="需要，\n并且 rehash 未進(jìn)行"]; begin_incremental_rehash -> rehashing_or_not; rehashing_or_not [label="rehash\n 正在進(jìn)行中？", shape=diamond, fillcolor = "#95BBE3"]; need_rehash_or_not -> rehashing_or_not [label="不需要，\n或者 rehash 正在進(jìn)行"]; is_rehashing [label="選擇 ht[1] 作為新鍵值對(duì)的添加目標(biāo)"]; not_rehashing [label="選擇 ht[0] 作為新鍵值對(duì)的添加目標(biāo)"]; rehashing_or_not -> is_rehashing [label="是"]; rehashing_or_not -> not_rehashing [label="否"]; calc_hash_code_and_index_by_key [label="根據(jù)給定鍵，計(jì)算出哈希值，以及索引值"]; is_rehashing -> calc_hash_code_and_index_by_key; not_rehashing -> calc_hash_code_and_index_by_key; create_entry_and_assoc_key_and_value [label="創(chuàng)建新 dictEntry ，并保存給定鍵值對(duì)"]; calc_hash_code_and_index_by_key -> create_entry_and_assoc_key_and_value; add_entry_to_hashtable [label="根據(jù)索引值，將新節(jié)點(diǎn)添加到目標(biāo)哈希表"]; create_entry_and_assoc_key_and_value -> add_entry_to_hashtable;}" />

在接下來(lái)的三節(jié)中，我們將分別看到，添加操作如何在以下三種情況中執(zhí)行：

1. 字典為空；
2. 添加新鍵值對(duì)時(shí)發(fā)生碰撞處理；
3. 添加新鍵值對(duì)時(shí)觸發(fā)了 rehash 操作；

添加新元素到空白字典

當(dāng)?shù)谝淮瓮兆值淅锾砑渔I值對(duì)時(shí)，程序會(huì)根據(jù) dict.h/DICT_HT_INITIAL_SIZE 里指定的大小為d->ht[0]->table 分配空間（在目前的版本中， DICT_HT_INITIAL_SIZE 的值為 4 ）。

以下是字典空白時(shí)的樣子：

ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="dictht |

以下是往空白字典添加了第一個(gè)鍵值對(duì)之后的樣子：

ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="dictht |

添加新鍵值對(duì)時(shí)發(fā)生碰撞處理

在哈希表實(shí)現(xiàn)中，當(dāng)兩個(gè)不同的鍵擁有相同的哈希值時(shí)，稱(chēng)這兩個(gè)鍵發(fā)生碰撞（collision），而哈希表實(shí)現(xiàn)必須想辦法對(duì)碰撞進(jìn)行處理。

字典哈希表所使用的碰撞解決方法被稱(chēng)之為鏈地址法 [http://en.wikipedia.org/wiki/Hash_table#Separate_chaining]：這種方法使用鏈表將多個(gè)哈希值相同的節(jié)點(diǎn)串連在一起，從而解決沖突問(wèn)題。

假設(shè)現(xiàn)在有一個(gè)帶有三個(gè)節(jié)點(diǎn)的哈希表，如下圖：

0 | 1 | 2 | 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="dictEntry |{key1 | value1 |next}", fillcolor = "#FADCAD"]; pair_2 [label="dictEntry |{key2 | value2 |next}", fillcolor = "#FADCAD"]; pair_3 [label="dictEntry |{key3 | value3 |next}", fillcolor = "#FADCAD"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // lines bucket:table0 -> pair_1:head; pair_1:next -> null0; bucket:table1 -> null1; bucket:table2 -> pair_2:head; pair_2:next -> null2; bucket:table3 -> pair_3:head; pair_3:next -> null3; // label label = "添加碰撞節(jié)點(diǎn)之前";}" />

對(duì)于一個(gè)新的鍵值對(duì) key4 和 value4 ，如果 key4 的哈希值和 key1 的哈希值相同，那么它們將在哈希表的 0 號(hào)索引上發(fā)生碰撞。

通過(guò)將 key4-value4 和 key1-value1 兩個(gè)鍵值對(duì)用鏈表連接起來(lái)，就可以解決碰撞的問(wèn)題：

0 | 1 | 2 | 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="dictEntry |{key1 | value1 |next}", fillcolor = "#FADCAD"]; pair_2 [label="dictEntry |{key2 | value2 |next}", fillcolor = "#FADCAD"]; pair_3 [label="dictEntry |{key3 | value3 |next}", fillcolor = "#FADCAD"]; pair_4 [label="dictEntry |{key4 | value4 |next}", fillcolor = "#FFC1C1"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // lines bucket:table0 -> pair_4:head; pair_4:next -> pair_1:head; pair_1:next -> null0; bucket:table1 -> null1; bucket:table2 -> pair_2:head; pair_2:next -> null2; bucket:table3 -> pair_3:head; pair_3:next -> null3; // label label = "添加碰撞節(jié)點(diǎn)之后";}" />

添加新鍵值對(duì)時(shí)觸發(fā)了 rehash 操作

對(duì)于使用鏈地址法來(lái)解決碰撞問(wèn)題的哈希表 dictht 來(lái)說(shuō)，哈希表的性能取決于大小（size屬性）與保存節(jié)點(diǎn)數(shù)量（used屬性）之間的比率：

• 哈希表的大小與節(jié)點(diǎn)數(shù)量，比率在 1:1 時(shí)，哈希表的性能最好；
• 如果節(jié)點(diǎn)數(shù)量比哈希表的大小要大很多的話(huà)，那么哈希表就會(huì)退化成多個(gè)鏈表，哈希表本身的性能優(yōu)勢(shì)便不復(fù)存在；

舉個(gè)例子，下面這個(gè)哈希表，平均每次失敗查找只需要訪(fǎng)問(wèn) 1 個(gè)節(jié)點(diǎn)（非空節(jié)點(diǎn)訪(fǎng)問(wèn) 2 次，空節(jié)點(diǎn)訪(fǎng)問(wèn) 1 次）：