字典 · Redis 設計與實現（第一版）

# 字典 [TOC=2,3] [字典（dictionary），又名映射（map）或關聯數組（associative array），](http://en.wikipedia.org/wiki/Associative_array) [http://en.wikipedia.org/wiki/Associative_array]是一種抽象數據結構，由一集鍵值對（key-value pairs）組成，各個鍵值對的鍵各不相同，程序可以添加新的鍵值對到字典中，或者基于鍵進行查找、更新或刪除等操作。本章先對字典在 Redis 中的應用進行介紹，接著講解字典的具體實現方式，以及這個字典實現要解決的問題，最后，以對字典迭代器的介紹作為本章的結束。 ### 字典的應用字典在 Redis 中的應用廣泛，使用頻率可以說和 SDS 以及雙端鏈表不相上下，基本上各個功能模塊都有用到字典的地方。其中，字典的主要用途有以下兩個： 1. 實現數據庫鍵空間（key space）； 1. 用作 Hash 類型鍵的底層實現之一；以下兩個小節分別介紹這兩種用途。 ### 實現數據庫鍵空間 Redis 是一個鍵值對數據庫，數據庫中的鍵值對由字典保存：每個數據庫都有一個對應的字典，這個字典被稱之為鍵空間（key space）。當用戶添加一個鍵值對到數據庫時（不論鍵值對是什么類型），程序就將該鍵值對添加到鍵空間；當用戶從數據庫中刪除鍵值對時，程序就會將這個鍵值對從鍵空間中刪除；等等。舉個例子，執行 [FLUSHDB](http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb] 可以清空鍵空間里的所有鍵值對數據： ~~~ redis> FLUSHDB OK ~~~ 執行 [DBSIZE](http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize] 則返回鍵空間里現有的鍵值對： ~~~ redis> DBSIZE (integer) 0 ~~~ 還可以用 [SET](http://redis.readthedocs.org/en/latest/string/set.html#set "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/set.html#set] 設置一個字符串鍵到鍵空間，并用 [GET](http://redis.readthedocs.org/en/latest/string/get.html#get "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/string/get.html#get] 從鍵空間中取出該字符串鍵的值： ~~~ redis> SET number 10086 OK redis> GET number "10086" redis> DBSIZE (integer) 1 ~~~ 后面的《[數據庫](#)》一章會對鍵空間以及數據庫的實現作詳細的介紹，屆時將看到，大部分針對數據庫的命令，比如 [DBSIZE](http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/server/dbsize.html#dbsize] 、 [FLUSHDB](http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/server/flushdb.html#flushdb] 、 [RANDOMKEY](http://redis.readthedocs.org/en/latest/key/randomkey.html#randomkey "(in Redis 命令參考 v2.8)") [http://redis.readthedocs.org/en/latest/key/randomkey.html#randomkey] ，等等，都是構建于對字典的操作之上的；而那些創建、更新、刪除和查找鍵值對的命令，也無一例外地需要在鍵空間上進行操作。 ### 用作 Hash 類型鍵的底層實現之一 Redis 的 Hash 類型鍵使用以下兩種數據結構作為底層實現: 1. 字典； 1. [壓縮列表](#)；因為壓縮列表比字典更節省內存，所以程序在創建新 Hash 鍵時，默認使用壓縮列表作為底層實現，當有需要時，程序才會將底層實現從壓縮列表轉換到字典。當用戶操作一個 Hash 鍵時，鍵值在底層就可能是一個哈希表： ~~~ 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" ~~~ 《[哈希表](#)》章節給出了關于哈希類型鍵的更多信息，并介紹了壓縮列表和字典之間的轉換條件。介紹完了字典的用途，現在讓我們來看看字典數據結構的定義。 ### 字典的實現實現字典的方法有很多種： - 最簡單的就是使用鏈表或數組，但是這種方式只適用于元素個數不多的情況下； - 要兼顧高效和簡單性，可以使用哈希表； - 如果追求更為穩定的性能特征，并希望高效地實現排序操作的話，則可使用更為復雜的平衡樹；在眾多可能的實現中，Redis 選擇了高效、實現簡單的哈希表，作為字典的底層實現。 `dict.h/dict` 給出了這個字典的定義： ~~~ /* * 字典 * * 每個字典使用兩個哈希表，用于實現漸進式 rehash */ typedef struct dict { // 特定于類型的處理函數 dictType *type; // 類型處理函數的私有數據 void *privdata; // 哈希表（2 個） dictht ht[2]; // 記錄 rehash 進度的標志，值為 -1 表示 rehash 未進行 int rehashidx; // 當前正在運作的安全迭代器數量 int iterators; } dict; ~~~ 以下是用于處理 `dict` 類型的 API ，它們的作用及相應的算法復雜度： | 操作 | 函數 | 算法復雜度 | |-----|-----|-----| | 創建一個新字典 | `dictCreate` | \(O(1)\) | | 添加新鍵值對到字典 | `dictAdd` | \(O(1)\) | | 添加或更新給定鍵的值 | `dictReplace` | \(O(1)\) | | 在字典中查找給定鍵所在的節點 | `dictFind` | \(O(1)\) | | 在字典中查找給定鍵的值 | `dictFetchValue` | \(O(1)\) | | 從字典中隨機返回一個節點 | `dictGetRandomKey` | \(O(1)\) | | 根據給定鍵，刪除字典中的鍵值對 | `dictDelete` | \(O(1)\) | | 清空并釋放字典 | `dictRelease` | \(O(N)\) | | 清空并重置（但不釋放）字典 | `dictEmpty` | \(O(N)\) | | 縮小字典 | `dictResize` | \(O(N)\) | | 擴大字典 | `dictExpand` | \(O(N)\) | | 對字典進行給定步數的 rehash | `dictRehash` | \(O(N)\) | | 在給定毫秒內，對字典進行rehash | `dictRehashMilliseconds` | \(O(N)\) | 注意 `dict` 類型使用了兩個指針，分別指向兩個哈希表。其中，0 號哈希表（`ht[0]`）是字典主要使用的哈希表，而 1 號哈希表（`ht[1]`）則只有在程序對 0 號哈希表進行 rehash 時才使用。接下來兩個小節將對哈希表的實現，以及哈希表所使用的哈希算法進行介紹。 ### 哈希表實現字典所使用的哈希表實現由 `dict.h/dictht` 類型定義： ~~~ /* * 哈希表 */ typedef struct dictht { // 哈希表節點指針數組（俗稱桶，bucket） dictEntry **table; // 指針數組的大小 unsigned long size; // 指針數組的長度掩碼，用于計算索引值 unsigned long sizemask; // 哈希表現有的節點數量 unsigned long used; } dictht; ~~~ `table` 屬性是個數組，數組的每個元素都是個指向 `dictEntry` 結構的指針。每個 `dictEntry` 都保存著一個鍵值對，以及一個指向另一個 `dictEntry` 結構的指針： ~~~ /* * 哈希表節點 */ typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 鏈往后繼節點 struct dictEntry *next; } dictEntry; ~~~ `next` 屬性指向另一個 `dictEntry` 結構，多個 `dictEntry` 可以通過 `next` 指針串連成鏈表，從這里可以看出，`dictht`[使用鏈地址法來處理鍵碰撞](http://en.wikipedia.org/wiki/Hash_table#Separate_chaining) [http://en.wikipedia.org/wiki/Hash_table#Separate_chaining]：當多個不同的鍵擁有相同的哈希值時，哈希表用一個鏈表將這些鍵連接起來。下圖展示了一個由 `dictht` 和數個 `dictEntry` 組成的哈希表例子： ![digraph hash_table_example { // setting rankdir = LR; node[shape = record, style = filled]; edge [style = bold]; // nodes ht1 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 3", fillcolor = "#95BBE3"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FADCAD"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // lines ht1:table -> bucket:head; 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;}](https://box.kancloud.cn/2015-09-13_55f4effb45132.svg) 如果再加上之前列出的 `dict` 類型，那么整個字典結構可以表示如下： ![digraph hash_table_example { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx: -1 | iterators: 0", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 3", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FADCAD"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; tnull1 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> bucket:head; ht1:table -> tnull1; 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;}](https://box.kancloud.cn/2015-09-13_55f4effb4d520.svg) 在上圖的字典示例中，字典雖然創建了兩個哈希表，但正在使用的只有 0 號哈希表，這說明字典未進行 rehash 狀態。 ### 哈希算法 Redis 目前使用兩種不同的哈希算法： 1. MurmurHash2 32 bit 算法：這種算法的分布率和速度都非常好，具體信息請參考 MurmurHash 的主頁： [http://code.google.com/p/smhasher/](http://code.google.com/p/smhasher/) 。 1. 基于 djb 算法實現的一個大小寫無關散列算法：具體信息請參考 [http://www.cse.yorku.ca/~oz/hash.html](http://www.cse.yorku.ca/~oz/hash.html) 。使用哪種算法取決于具體應用所處理的數據： - 命令表以及 Lua 腳本緩存都用到了算法 2 。 - 算法 1 的應用則更加廣泛：數據庫、集群、哈希鍵、阻塞操作等功能都用到了這個算法。 ### 創建新字典 `dictCreate` 函數創建并返回一個新字典： ~~~ dict *d = dictCreate(&hash_type, NULL); ~~~ `d` 的值可以用圖片表示如下： ![digraph empty_dict { // setting rankdir = LR; node[shape = record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> null0; ht1:table -> null1;}](https://box.kancloud.cn/2015-09-13_55f4effb59bc5.svg) 新創建的兩個哈希表都沒有為 `table` 屬性分配任何空間： - `ht[0]->table` 的空間分配將在第一次往字典添加鍵值對時進行； - `ht[1]->table` 的空間分配將在 rehash 開始時進行； ### 添加鍵值對到字典根據字典所處的狀態，將給定的鍵值對添加到字典可能會引起一系列復雜的操作： - 如果字典為未初始化（即字典的 0 號哈希表的 `table` 屬性為空），則程序需要對 0 號哈希表進行初始化； - 如果在插入時發生了鍵碰撞，則程序需要處理碰撞； - 如果插入新元素，使得字典滿足了 rehash 條件，則需要啟動相應的 rehash 程序；當程序處理完以上三種情況之后，新的鍵值對才會被真正地添加到字典上。整個添加流程可以用下圖表示： ![digraph dictAdd { node[shape=plaintext, style = filled]; edge [style = bold]; // start [label="dictAdd", fillcolor = "#A8E270"]; key_exists_or_not [label="鍵已經存在？", shape=diamond, fillcolor = "#95BBE3"]; start -> 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="開始漸進式 rehash "]; need_rehash_or_not -> begin_incremental_rehash [label="需要，\n并且 rehash 未進行"]; begin_incremental_rehash -> rehashing_or_not; rehashing_or_not [label="rehash\n 正在進行中？", shape=diamond, fillcolor = "#95BBE3"]; need_rehash_or_not -> rehashing_or_not [label="不需要，\n或者 rehash 正在進行"]; is_rehashing [label="選擇 ht[1] 作為新鍵值對的添加目標"]; not_rehashing [label="選擇 ht[0] 作為新鍵值對的添加目標"]; rehashing_or_not -> is_rehashing [label="是"]; rehashing_or_not -> not_rehashing [label="否"]; calc_hash_code_and_index_by_key [label="根據給定鍵，計算出哈希值，以及索引值"]; 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="創建新 dictEntry ，并保存給定鍵值對"]; calc_hash_code_and_index_by_key -> create_entry_and_assoc_key_and_value; add_entry_to_hashtable [label="根據索引值，將新節點添加到目標哈希表"]; create_entry_and_assoc_key_and_value -> add_entry_to_hashtable;}](https://box.kancloud.cn/2015-09-13_55f4effb62eda.svg) 在接下來的三節中，我們將分別看到，添加操作如何在以下三種情況中執行： 1. 字典為空； 1. 添加新鍵值對時發生碰撞處理； 1. 添加新鍵值對時觸發了 rehash 操作； ### 添加新元素到空白字典當第一次往空字典里添加鍵值對時，程序會根據 `dict.h/DICT_HT_INITIAL_SIZE` 里指定的大小為`d->ht[0]->table` 分配空間（在目前的版本中， `DICT_HT_INITIAL_SIZE` 的值為 `4` ）。以下是字典空白時的樣子： ![digraph empty_dict { // setting rankdir = LR; node[shape = record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> null0; ht1:table -> null1;}](https://box.kancloud.cn/2015-09-13_55f4effb6b8c5.svg) 以下是往空白字典添加了第一個鍵值對之后的樣子： ![digraph add_first_entry_to_empty_dict { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 1", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 "fillcolor = "#F2F2F2"]; entry [label="<head>dictEntry |{<start>key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> bucket:head; bucket:table1 -> entry:head; entry:next -> null0; ht1:table -> null1; // table nulls tnull0 [label="NULL", shape=plaintext]; tnull2 [label="NULL", shape=plaintext]; tnull3 [label="NULL", shape=plaintext]; bucket:table0 -> tnull0; bucket:table2 -> tnull2; bucket:table3 -> tnull3;}](https://box.kancloud.cn/2015-09-13_55f4effb75eea.svg) ### 添加新鍵值對時發生碰撞處理在哈希表實現中，當兩個不同的鍵擁有相同的哈希值時，稱這兩個鍵發生碰撞（collision），而哈希表實現必須想辦法對碰撞進行處理。字典哈希表所使用的碰撞解決方法被稱之為[鏈地址法](http://en.wikipedia.org/wiki/Hash_table#Separate_chaining) [http://en.wikipedia.org/wiki/Hash_table#Separate_chaining]：這種方法使用鏈表將多個哈希值相同的節點串連在一起，從而解決沖突問題。假設現在有一個帶有三個節點的哈希表，如下圖： ![digraph before_key_collision { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes bucket [label="dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>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 = "添加碰撞節點之前";}](https://box.kancloud.cn/2015-09-13_55f4effb81911.svg) 對于一個新的鍵值對 `key4` 和 `value4` ，如果 `key4` 的哈希值和 `key1` 的哈希值相同，那么它們將在哈希表的 `0` 號索引上發生碰撞。通過將 `key4-value4` 和 `key1-value1` 兩個鍵值對用鏈表連接起來，就可以解決碰撞的問題： ![digraph after_key_collision { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes bucket [label="dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FADCAD"]; pair_4 [label="<head>dictEntry |{key4 | value4 |<next>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 = "添加碰撞節點之后";}](https://box.kancloud.cn/2015-09-13_55f4effb8bfca.svg) ### 添加新鍵值對時觸發了 rehash 操作對于使用鏈地址法來解決碰撞問題的哈希表 `dictht` 來說，哈希表的性能取決于大小（`size`屬性）與保存節點數量（`used`屬性）之間的比率： - 哈希表的大小與節點數量，比率在 1:1 時，哈希表的性能最好； - 如果節點數量比哈希表的大小要大很多的話，那么哈希表就會退化成多個鏈表，哈希表本身的性能優勢便不復存在；舉個例子，下面這個哈希表，平均每次失敗查找只需要訪問 1 個節點（非空節點訪問 2 次，空節點訪問 1 次）： ![digraph good_performance_hash { rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // bucket bucket [label="bucket |<0> 0 |<1> 1 |<2> 2 |<3> 3 |<4> 4 |<5> 5 |<6> 6 |<7> 7", fillcolor = "#F2F2F2"]; // nodes node [height=.1]; node0 [label="Entry", fillcolor = "#FADCAD"]; node0_null [label="NULL", shape=plaintext]; node1 [label="Entry", fillcolor = "#FADCAD"]; node1_null [label="NULL", shape=plaintext]; node2 [label="NULL", shape=plaintext]; node3 [label="Entry", fillcolor = "#FADCAD"]; node3_null [label="NULL", shape=plaintext]; node4 [label="NULL", shape=plaintext]; node5 [label="Entry", fillcolor = "#FADCAD"]; node5_null [label="NULL", shape=plaintext]; node6 [label="NULL", shape=plaintext]; node7 [label="NULL", shape=plaintext]; bucket:0 -> node0; node0 -> node0_null; bucket:1 -> node1; node1 -> node1_null; bucket:2 -> node2; bucket:3 -> node3; node3 -> node3_null; bucket:4 -> node4; bucket:5 -> node5; node5 -> node5_null; bucket:6 -> node6; bucket:7 -> node7;}](https://box.kancloud.cn/2015-09-13_55f4effb98582.svg) 而下面這個哈希表，平均每次失敗查找需要訪問 5 個節點： ![digraph bad_performance_hash { rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // bucket bucket [label="bucket |<0> 0 |<1> 1 |<2> 2 |<3> 3 |<4> 4 |<5> 5 |<6> 6 |<7> 7", fillcolor = "#F2F2F2"]; // nodes node [height=.1]; // node 0 node0 [label="Entry", fillcolor = "#FADCAD"]; node01 [label="Entry", fillcolor = "#FADCAD"]; node02 [label="Entry", fillcolor = "#FADCAD"]; node03 [label="Entry", fillcolor = "#FADCAD"]; node04 [label="Entry", fillcolor = "#FADCAD"]; node05 [label="NULL", shape=plaintext]; bucket:0 -> node0; node0 -> node01; node01 -> node02; node02 -> node03; node03 -> node04; node04 -> node05; // node 1 node1 [label="Entry", fillcolor = "#FADCAD"]; node11 [label="Entry", fillcolor = "#FADCAD"]; node12 [label="Entry", fillcolor = "#FADCAD"]; node13 [label="NULL", shape=plaintext]; bucket:1 -> node1; node1 -> node11; node11 -> node12; node12 -> node13; // node 2 node2 [label="Entry", fillcolor = "#FADCAD"]; node21 [label="Entry", fillcolor = "#FADCAD"]; node22 [label="Entry", fillcolor = "#FADCAD"]; node23 [label="Entry", fillcolor = "#FADCAD"]; node24 [label="Entry", fillcolor = "#FADCAD"]; node25 [label="NULL", shape=plaintext]; bucket:2 -> node2; node2 -> node21; node21 -> node22; node22 -> node23; node23 -> node24; node24 -> node25; // node 3 node3 [label="Entry", fillcolor = "#FADCAD"]; node31 [label="Entry", fillcolor = "#FADCAD"]; node32 [label="Entry", fillcolor = "#FADCAD"]; node33 [label="Entry", fillcolor = "#FADCAD"]; node34 [label="Entry", fillcolor = "#FADCAD"]; node35 [label="NULL", shape=plaintext]; bucket:3 -> node3; node3 -> node31; node31 -> node32; node32 -> node33; node33 -> node34; node34 -> node35; // node 4 node4 [label="Entry", fillcolor = "#FADCAD"]; node41 [label="Entry", fillcolor = "#FADCAD"]; node42 [label="NULL", shape=plaintext]; bucket:4 -> node4; node4 -> node41; node41 -> node42; // node 5 node5 [label="Entry", fillcolor = "#FADCAD"]; node51 [label="Entry", fillcolor = "#FADCAD"]; node52 [label="Entry", fillcolor = "#FADCAD"]; node53 [label="Entry", fillcolor = "#FADCAD"]; node54 [label="Entry", fillcolor = "#FADCAD"]; node55 [label="NULL", shape=plaintext]; bucket:5 -> node5; node5 -> node51; node51 -> node52; node52 -> node53; node53 -> node54; node54 -> node55; // node 6 node6 [label="Entry", fillcolor = "#FADCAD"]; node61 [label="Entry", fillcolor = "#FADCAD"]; node62 [label="Entry", fillcolor = "#FADCAD"]; node63 [label="Entry", fillcolor = "#FADCAD"]; node64 [label="NULL", shape=plaintext]; bucket:6 -> node6; node6 -> node61; node61 -> node62; node62 -> node63; node63 -> node64; // node 7 node7 [label="Entry", fillcolor = "#FADCAD"]; node71 [label="Entry", fillcolor = "#FADCAD"]; node72 [label="Entry", fillcolor = "#FADCAD"]; node73 [label="Entry", fillcolor = "#FADCAD"]; node74 [label="Entry", fillcolor = "#FADCAD"]; node75 [label="NULL", shape=plaintext]; bucket:7 -> node7; node7 -> node71; node71 -> node72; node72 -> node73; node73 -> node74; node74 -> node75;}](https://box.kancloud.cn/2015-09-13_55f4effba0b02.svg) 為了在字典的鍵值對不斷增多的情況下保持良好的性能，字典需要對所使用的哈希表（`ht[0]`）進行 rehash 操作：在不修改任何鍵值對的情況下，對哈希表進行擴容，盡量將比率維持在 1:1 左右。 `dictAdd` 在每次向字典添加新鍵值對之前，都會對哈希表 `ht[0]` 進行檢查，對于 `ht[0]` 的 `size` 和 `used` 屬性，如果它們之間的比率 `ratio = used / size` 滿足以下任何一個條件的話，rehash 過程就會被激活： 1. 自然 rehash ： `ratio >= 1` ，且變量 `dict_can_resize` 為真。 1. 強制 rehash ： `ratio` 大于變量 `dict_force_resize_ratio` （目前版本中， `dict_force_resize_ratio` 的值為 `5` ）。 Note 什么時候 `dict_can_resize` 會為假？在前面介紹字典的應用時也說到過，數據庫就是字典，數據庫里的哈希類型鍵也是字典，當 Redis 使用子進程對數據庫執行后臺持久化任務時（比如執行 `BGSAVE` 或 `BGREWRITEAOF` 時），為了最大化地利用系統的 [copy on write](http://en.wikipedia.org/wiki/Copy-on-write) [http://en.wikipedia.org/wiki/Copy-on-write] 機制，程序會暫時將 `dict_can_resize` 設為假，避免執行自然 rehash ，從而減少程序對內存的觸碰（touch）。當持久化任務完成之后，`dict_can_resize` 會重新被設為真。另一方面，當字典滿足了強制 rehash 的條件時，即使 `dict_can_resize` 不為真（有 `BGSAVE` 或 `BGREWRITEAOF` 正在執行），這個字典一樣會被 rehash 。 ### Rehash 執行過程字典的 rehash 操作實際上就是執行以下任務： 1. 創建一個比 `ht[0]->table` 更大的 `ht[1]->table` ； 1. 將 `ht[0]->table` 中的所有鍵值對遷移到 `ht[1]->table` ； 1. 將原有 `ht[0]` 的數據清空，并將 `ht[1]` 替換為新的 `ht[0]` ；經過以上步驟之后，程序就在不改變原有鍵值對數據的基礎上，增大了哈希表的大小。作為例子，以下四個小節展示了一次對哈希表進行 rehash 的完整過程。 ### 1. 開始 rehash 這個階段有兩個事情要做： 1. 設置字典的 `rehashidx` 為 `0` ，標識著 rehash 的開始； 1. 為 `ht[1]->table` 分配空間，大小至少為 `ht[0]->used` 的兩倍；這時的字典是這個樣子： ![digraph rehash_step_one { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx: 0 | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 4", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 8 | sizemask: 7 | used: 0", fillcolor = "#95BBE3"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; bucket1 [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 |<table4> 4 |<table5> 5 |<table6> 6 |<table7> 7", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FADCAD"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FADCAD"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FADCAD"]; pair_4 [label="<head>dictEntry |{key4 | value4 |<next>next}", fillcolor = "#FADCAD"]; // null for bucket 0 null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // null for bucket 1 null10 [label="NULL", shape=plaintext]; null11 [label="NULL", shape=plaintext]; null12 [label="NULL", shape=plaintext]; null13 [label="NULL", shape=plaintext]; null14 [label="NULL", shape=plaintext]; null15 [label="NULL", shape=plaintext]; null16 [label="NULL", shape=plaintext]; null17 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> bucket:head; ht1:table -> bucket1:head; bucket:table0 -> pair_1:head; pair_1:next -> null0; bucket:table1 -> pair_4:head; pair_4:next -> null1; bucket:table2 -> pair_2:head; pair_2:next -> null2; bucket:table3 -> pair_3:head; pair_3:next -> null3; bucket1:table0 -> null10; bucket1:table1 -> null11; bucket1:table2 -> null12; bucket1:table3 -> null13; bucket1:table4 -> null14; bucket1:table5 -> null15; bucket1:table6 -> null16; bucket1:table7 -> null17;}](https://box.kancloud.cn/2015-09-13_55f4effbaf285.svg) ### 2. Rehash 進行中在這個階段， `ht[0]->table` 的節點會被逐漸遷移到 `ht[1]->table` ，因為 rehash 是分多次進行的（細節在下一節解釋），字典的 `rehashidx` 變量會記錄 rehash 進行到 `ht[0]` 的哪個索引位置上。以下是 `rehashidx` 值為 `2` 時，字典的樣子： ![digraph rehash_step_two { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx: 2 | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 1", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 8 | sizemask: 7 | used: 3", fillcolor = "#95BBE3"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; bucket1 [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 |<table4> 4 |<table5> 5 |<table6> 6 |<table7> 7", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FFC1C1"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FFC1C1"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FADCAD"]; pair_4 [label="<head>dictEntry |{key4 | value4 |<next>next}", fillcolor = "#FFC1C1"]; // null for bucket 0 null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // null for bucket 1 null10 [label="NULL", shape=plaintext]; null11 [label="NULL", shape=plaintext]; null12 [label="NULL", shape=plaintext]; null13 [label="NULL", shape=plaintext]; null14 [label="NULL", shape=plaintext]; null15 [label="NULL", shape=plaintext]; null16 [label="NULL", shape=plaintext]; null17 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> bucket:head; ht1:table -> bucket1:head; bucket:table0 -> null0; bucket:table1 -> null1; bucket:table2 -> null2; bucket:table3 -> pair_3:head; pair_3:next -> null3; bucket1:table0 -> null10; bucket1:table1 -> pair_4:head; pair_4:next -> null11; bucket1:table2 -> null12; bucket1:table3 -> pair_2:head; pair_2:next -> null13; bucket1:table4 -> null14; bucket1:table5 -> null15; bucket1:table6 -> pair_1:head; pair_1:next -> null16; bucket1:table7 -> null17;}](https://box.kancloud.cn/2015-09-13_55f4effbbcf51.svg) 注意除了節點的移動外，字典的 `rehashidx` 、 `ht[0]->used` 和 `ht[1]->used` 三個屬性也產生了變化。 ### 3. 節點遷移完畢到了這個階段，所有的節點都已經從 `ht[0]` 遷移到 `ht[1]` 了： ![digraph rehash_step_three { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx: 3 | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 4 | sizemask: 3 | used: 0", fillcolor = "#95BBE3"]; ht1 [label="<dictht>dictht |<table> table | size: 8 | sizemask: 7 | used: 4", fillcolor = "#95BBE3"]; bucket [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 ", fillcolor = "#F2F2F2"]; bucket1 [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 |<table4> 4 |<table5> 5 |<table6> 6 |<table7> 7", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FFC1C1"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FFC1C1"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FFC1C1"]; pair_4 [label="<head>dictEntry |{key4 | value4 |<next>next}", fillcolor = "#FFC1C1"]; // null for bucket 0 null0 [label="NULL", shape=plaintext]; null1 [label="NULL", shape=plaintext]; null2 [label="NULL", shape=plaintext]; null3 [label="NULL", shape=plaintext]; // null for bucket 1 null10 [label="NULL", shape=plaintext]; null11 [label="NULL", shape=plaintext]; null12 [label="NULL", shape=plaintext]; null13 [label="NULL", shape=plaintext]; null14 [label="NULL", shape=plaintext]; null15 [label="NULL", shape=plaintext]; null16 [label="NULL", shape=plaintext]; null17 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht1:dictht [label="ht[1]"]; ht0:table -> bucket:head; ht1:table -> bucket1:head; bucket:table0 -> null0; bucket:table1 -> null1; bucket:table2 -> null2; bucket:table3 -> null3; bucket1:table0 -> pair_3:head; pair_3:next -> null10; bucket1:table1 -> pair_4:head; pair_4:next -> null11; bucket1:table2 -> null12; bucket1:table3 -> pair_2:head; pair_2:next -> null13; bucket1:table4 -> null14; bucket1:table5 -> null15; bucket1:table6 -> pair_1:head; pair_1:next -> null16; bucket1:table7 -> null17;}](https://box.kancloud.cn/2015-09-13_55f4effbcc6da.svg) ### 4. Rehash 完畢在 rehash 的最后階段，程序會執行以下工作： 1. 釋放 `ht[0]` 的空間； 1. 用 `ht[1]` 來代替 `ht[0]` ，使原來的 `ht[1]` 成為新的 `ht[0]` ； 1. 創建一個新的空哈希表，并將它設置為 `ht[1]` ； 1. 將字典的 `rehashidx` 屬性設置為 `-1` ，標識 rehash 已停止；以下是字典 rehash 完畢之后的樣子： ![digraph rehash_step_four { // setting rankdir = LR; node[shape=record, style = filled]; edge [style = bold]; // nodes dict [label="dict | type | privdata |<ht> ht[2] | rehashidx: -1 | iterators", fillcolor = "#A8E270"]; ht0 [label="<dictht>dictht |<table> table | size: 8 | sizemask: 7 | used: 4", fillcolor = "#95BBE3"]; ht3 [label="<dictht>dictht |<table> table | size: 0 | sizemask: 0 | used: 0", fillcolor = "#95BBE3"]; bucket1 [label="<head>dictEntry**\n(bucket) |<table0> 0 |<table1> 1 |<table2> 2 |<table3> 3 |<table4> 4 |<table5> 5 |<table6> 6 |<table7> 7", fillcolor = "#F2F2F2"]; pair_1 [label="<head>dictEntry |{key1 | value1 |<next>next}", fillcolor = "#FFC1C1"]; pair_2 [label="<head>dictEntry |{key2 | value2 |<next>next}", fillcolor = "#FFC1C1"]; pair_3 [label="<head>dictEntry |{key3 | value3 |<next>next}", fillcolor = "#FFC1C1"]; pair_4 [label="<head>dictEntry |{key4 | value4 |<next>next}", fillcolor = "#FFC1C1"]; // null for bucket 1 null10 [label="NULL", shape=plaintext]; null11 [label="NULL", shape=plaintext]; null12 [label="NULL", shape=plaintext]; null13 [label="NULL", shape=plaintext]; null14 [label="NULL", shape=plaintext]; null15 [label="NULL", shape=plaintext]; null16 [label="NULL", shape=plaintext]; null17 [label="NULL", shape=plaintext]; // lines dict:ht -> ht0:dictht [label="ht[0]"]; dict:ht -> ht3:dictht [label="ht[1]"]; null_bucket [label="NULL", shape=plaintext]; ht3:table -> null_bucket; ht0:table -> bucket1:head; bucket1:table0 -> pair_3:head; pair_3:next -> null10; bucket1:table1 -> pair_4:head; pair_4:next -> null11; bucket1:table2 -> null12; bucket1:table3 -> pair_2:head; pair_2:next -> null13; bucket1:table4 -> null14; bucket1:table5 -> null15; bucket1:table6 -> pair_1:head; pair_1:next -> null16; bucket1:table7 -> null17;}](https://box.kancloud.cn/2015-09-13_55f4effbd61a1.svg) 對比字典 rehash 前后，新的 `ht[0]` 空間更大，并且字典原有的鍵值對也沒有被修改或者刪除。 ### 漸進式 rehash 在上一節，我們了解了字典的 rehash 過程，需要特別指出的是， rehash 程序并不是在激活之后，就馬上執行直到完成的，而是分多次、漸進式地完成的。假設這樣一個場景：在一個有很多鍵值對的字典里，某個用戶在添加新鍵值對時觸發了 rehash 過程，如果這個 rehash 過程必須將所有鍵值對遷移完畢之后才將結果返回給用戶，這樣的處理方式將是非常不友好的。另一方面，要求服務器必須阻塞直到 rehash 完成，這對于 Redis 服務器本身也是不能接受的。為了解決這個問題，Redis 使用了漸進式（incremental）的 rehash 方式：通過將 rehash 分散到多個步驟中進行，從而避免了集中式的計算。漸進式 rehash 主要由 `_dictRehashStep` 和 `dictRehashMilliseconds` 兩個函數進行： - `_dictRehashStep` 用于對數據庫字典、以及哈希鍵的字典進行被動 rehash ； - `dictRehashMilliseconds` 則由 Redis 服務器常規任務程序（server cron job）執行，用于對數據庫字典進行主動 rehash ； ### _dictRehashStep 每次執行 `_dictRehashStep` ，`ht[0]->table` 哈希表第一個不為空的索引上的所有節點就會全部遷移到 `ht[1]->table` 。在 rehash 開始進行之后（`d->rehashidx` 不為 `-1`），每次執行一次添加、查找、刪除操作，`_dictRehashStep` 都會被執行一次： ![digraph rehash_step { node[shape=plaintext, style = filled]; edge [style = bold]; // callers dictAdd [label="dictAdd", fillcolor = "#A8E270"]; dictFind [label="dictFind", fillcolor = "#A8E270"]; dictDelete [label="dictDelete", fillcolor = "#A8E270"]; dictGetRandomKey [label="dictGetRandomKey", fillcolor = "#A8E270"]; // rehash rehashing_or_not [shape=diamond, label="正在進行 rehash ？", fillcolor = "#95BBE3"]; _dictRehashStep [label="_dictRehashStep", fillcolor = "#A8E270"]; one_index [label="將 ht[0] 第一個不為空索引上的所有節點遷移至 ht[1]"]; // edge dictAdd -> rehashing_or_not; dictFind -> rehashing_or_not; dictDelete -> rehashing_or_not; dictGetRandomKey -> rehashing_or_not; rehashing_or_not -> _dictRehashStep [label="是"]; _dictRehashStep -> one_index;}](https://box.kancloud.cn/2015-09-13_55f4effbe0bf3.svg) 因為字典會保持哈希表大小和節點數的比率在一個很小的范圍內，所以每個索引上的節點數量不會很多（從目前版本的 rehash 條件來看，平均只有一個，最多通常也不會超過五個），所以在執行操作的同時，對單個索引上的節點進行遷移，幾乎不會對響應時間造成影響。 ### dictRehashMilliseconds `dictRehashMilliseconds` 可以在指定的毫秒數內，對字典進行 rehash 。當 Redis 的服務器常規任務執行時，`dictRehashMilliseconds` 會被執行，在規定的時間內，盡可能地對數據庫字典中那些需要 rehash 的字典進行 rehash ，從而加速數據庫字典的 rehash 進程（progress）。 ### 其他措施在哈希表進行 rehash 時，字典還會采取一些特別的措施，確保 rehash 順利、正確地進行： - 因為在 rehash 時，字典會同時使用兩個哈希表，所以在這期間的所有查找、刪除等操作，除了在 `ht[0]` 上進行，還需要在 `ht[1]` 上進行。 - 在執行添加操作時，新的節點會直接添加到 `ht[1]` 而不是 `ht[0]` ，這樣保證 `ht[0]` 的節點數量在整個 rehash 過程中都只減不增。 ### 字典的收縮上面關于 rehash 的章節描述了通過 rehash 對字典進行擴展（expand）的情況，如果哈希表的可用節點數比已用節點數大很多的話，那么也可以通過對哈希表進行 rehash 來收縮（shrink）字典。收縮 rehash 和上面展示的擴展 rehash 的操作幾乎一樣，執行以下步驟： 1. 創建一個比 `ht[0]->table` 小的 `ht[1]->table` ； 1. 將 `ht[0]->table` 中的所有鍵值對遷移到 `ht[1]->table` ； 1. 將原有 `ht[0]` 的數據清空，并將 `ht[1]` 替換為新的 `ht[0]` ；擴展 rehash 和收縮 rehash 執行完全相同的過程，一個 rehash 是擴展還是收縮字典，關鍵在于新分配的 `ht[1]->table` 的大小： - 如果 rehash 是擴展操作，那么 `ht[1]->table` 比 `ht[0]->table` 要大； - 如果 rehash 是收縮操作，那么 `ht[1]->table` 比 `ht[0]->table` 要小；字典的收縮規則由 `redis.c/htNeedsResize` 函數定義： ~~~ /* * 檢查字典的使用率是否低于系統允許的最小比率 * * 是的話返回 1 ，否則返回 0 。 */ int htNeedsResize(dict *dict) { long long size, used; // 哈希表大小 size = dictSlots(dict); // 哈希表已用節點數量 used = dictSize(dict); // 當哈希表的大小大于 DICT_HT_INITIAL_SIZE // 并且字典的填充率低于 REDIS_HT_MINFILL 時 // 返回 1 return (size && used && size > DICT_HT_INITIAL_SIZE && (used*100/size < REDIS_HT_MINFILL)); } ~~~ 在默認情況下，`REDIS_HT_MINFILL` 的值為 `10` ，也即是說，當字典的填充率低于 10% 時，程序就可以對這個字典進行收縮操作了。字典收縮和字典擴展的一個區別是： - 字典的擴展操作是自動觸發的（不管是自動擴展還是強制擴展）； - 而字典的收縮操作則是由程序手動執行。因此，使用字典的程序可以決定何時對字典進行收縮： - 當字典用于實現哈希鍵的時候，每次從字典中刪除一個鍵值對，程序就會執行一次 `htNeedsResize` 函數，如果字典達到了收縮的標準，程序將立即對字典進行收縮； - 當字典用于實現數據庫鍵空間（key space）的時候，收縮的時機由 `redis.c/tryResizeHashTables` 函數決定，具體信息請參考《[數據庫](#)》一章的《[數據庫空間的收縮和擴展](#)》小節； ### 字典其他操作除了添加操作和伸展/收縮操作之外，字典還定義了一些其他操作，比如常見的查找、刪除和更新。因為鏈地址法哈希表實現的相關信息可以從任何一本數據結構或算法書上找到，這里不再對字典的其他操作進行介紹，不過前面對創建字典、添加鍵值對、收縮和擴展 rehash 的討論已經涵蓋了字典模塊的核心內容。 ### 字典的迭代字典帶有自己的[迭代器](http://en.wikipedia.org/wiki/Iterator) [http://en.wikipedia.org/wiki/Iterator]實現 ——對字典進行迭代實際上就是對字典所使用的哈希表進行迭代： - 迭代器首先迭代字典的第一個哈希表，然后，如果 rehash 正在進行的話，就繼續對第二個哈希表進行迭代。 - 當迭代哈希表時，找到第一個不為空的索引，然后迭代這個索引上的所有節點。 - 當這個索引迭代完了，繼續查找下一個不為空的索引，如此反覆，直到整個哈希表都迭代完為止。整個迭代過程可以用偽代碼表示如下： ~~~ def iter_dict(dict): # 迭代 0 號哈希表 iter_table(ht[0]->table) # 如果正在執行 rehash ，那么也迭代 1 號哈希表 if dict.is_rehashing(): iter_table(ht[1]->table) def iter_table(table): # 遍歷哈希表上的所有索引 for index in table: # 跳過空索引 if table[index].empty(): continue # 遍歷索引上的所有節點 for node in table[index]: # 處理節點 do_something_with(node) ~~~ 字典的迭代器有兩種： - 安全迭代器：在迭代進行過程中，可以對字典進行修改。 - 不安全迭代器：在迭代進行過程中，不對字典進行修改。以下是迭代器的數據結構定義： ~~~ /* * 字典迭代器 */ typedef struct dictIterator { dict *d; // 正在迭代的字典 int table, // 正在迭代的哈希表的號碼（0 或者 1） index, // 正在迭代的哈希表數組的索引 safe; // 是否安全？ dictEntry *entry, // 當前哈希節點 *nextEntry; // 當前哈希節點的后繼節點 } dictIterator; ~~~ 以下函數是這個迭代器的 API ，API 的作用及相關算法復雜度： | 函數 | 作用 | 算法復雜度 | |-----|-----|-----| | `dictGetIterator` | 創建一個不安全迭代器。 | \(O(1)\) | | `dictGetSafeIterator` | 創建一個安全迭代器。 | \(O(1)\) | | `dictNext` | 返回迭代器指向的當前節點，如果迭代完畢，返回 `NULL` 。 | \(O(1)\) | | `dictReleaseIterator` | 釋放迭代器。 | \(O(1)\) | ### 小結 - 字典是由鍵值對構成的抽象數據結構。 - Redis 中的數據庫和哈希鍵都基于字典來實現。 - Redis 字典的底層實現為哈希表，每個字典使用兩個哈希表，一般情況下只使用 0 號哈希表，只有在 rehash 進行時，才會同時使用 0 號和 1 號哈希表。 - 哈希表使用鏈地址法來解決鍵沖突的問題。 - Rehash 可以用于擴展或收縮哈希表。 - 對哈希表的 rehash 是分多次、漸進式地進行的。