Redis 源碼分析：dict.c 和 dict.h
簡介
哈希表是 redis 的核心結構之一，在 redis 的源碼中， dict.c 和 dict.h 就定義了 redis 所使用的哈希結構，在這篇文章中，我們將對 dict.c 和 dict.h 進行注解和分析，籍此加深對 redis 的理解。
數據結構概覽
dict.h 中定義了被 dict.c 的程序所使用的幾個數據結構，如 dict 、dictht 和 dictEntry 等，它們之間的關系可以用下圖來描述(點擊放大）：
數據結構實現細節
上一節的大圖給出了數據結構之間相互關系，現在，讓我們將注意力集中到 dict 、 dictht 和 dictEntry 這三個核心數據結構上面。
dict 結構的定義如下：
/* 字典結構 */
typedef struct dict {
dictType *type; // 為哈希表中不同類型的值所使用的一族函數
void *privdata;
dictht ht[2]; // 每個字典使用兩個哈希表
int rehashidx; // 指示 rehash 是否正在進行，如果不是則為 -1
int iterators; // 當前正在使用的 iterator 的數量
} dict; 代碼的注釋基本都說明相關屬性的作用了，需要補充的一些是：
每個字典使用兩個哈希表，是因為要實現漸增式 rehash ，redis 會逐個逐個地將 0 號哈希表的元素移動到 1 號哈希表，直到 0 號哈希表被清空為止，文章的后面會給出相關細節，不要心急！
另外， rehashidx 記錄的實際上是 rehash 進行到的索引，比如如果 rehash 進行到第 10 個元素，那么 rehashidx 的值就為 9，以此類推，如果沒有在進行 rehash ，rehashidx 的值就為 -1 。
接著來看看哈希表結構 —— dictht 結構，這個哈希表是一個 seprate chaining hash table 實現，它通過將哈希值相同的元素放到一個鏈表中來解決沖突問題：
typedef struct dictht {
dictEntry **table; // 節點指針數組
unsigned long size; // 桶的數量
unsigned long sizemask; // mask 碼，用于地址索引計算
unsigned long used; // 已有節點數量
} dictht; table 屬性組成了一個數組，數組里帶有節點指針，用作鏈表。
size 、 sizemask 和 used 這三個屬性初看上去讓人有點頭暈，實際上，它們分別代表的是：
size ：桶的數量，也即是， table 數組的大小。
sizemask ：這個值通過 size – 1 計算出來，給定 key 的哈希值計算出來之后，就會和這個數值進行 & 操作，決定元素被放到 table 數組的那一個位置上。
used ：這個值代表目前哈希表中元素的數量，也即是哈希表總共保存了多少 dictEntry 結構。
好的，最后，就是鏈表節點結構 —— dictEntry 了：
typedef struct dictEntry {
void *key; // 鍵
union {
void *val;
uint64_t u64;
int64_t s64;
} v; // 值(可以有幾種不同類型)
struct dictEntry *next; // 指向下一個哈希節點(形成鏈表)
} dictEntry; 這個結構。。。阿，好吧，這個結構沒啥要說的，趕緊進入下一部分吧。
字典創建流程
在初步解了幾個核心數據結構之后，是時候可以來看看相關的函數怎么來使用這些數據結構了，讓我們從最開始的創建字典開始，一步步研究字典（以及哈希表）的運作流程。
因為調用流程可以給我們一個高層次的觀點來了解數據結構的運作流程，而不必陷入到代碼細節中，因此，文章這里只給出程序調用流程的部分核心代碼，如果你對代碼的其他細節有興趣，可以到我的 github 上去找注釋版的代碼，上面有完整的代碼，而且我給大部分函數都加上了注釋。
OK，說回來字典這邊，創建新字典執行的調用鏈是： dictCreate -> _dictInit -> _dictReset
其中 dictCreate 函數為 dict 結構分配了空間，然后將新的 dict 傳給 _dictInit 函數，讓它初始化 dict 結構的相關屬性，而 _dictInit 又調用 _dictReset ，對字典的 ht 屬性（也即是兩個哈希表）進行常量屬性的設置。
注意， _dictReset 只是為字典所屬的兩個哈希表進行常量屬性的設置(size、 sizemask 和 used），但并不為哈希表的鏈表數組分配內存：
static void _dictReset(dictht *ht)
{
ht->table = NULL;
ht->size = 0;
ht->sizemask = 0;
ht->used = 0;
} 0 號哈希表的創建流程
我們知道，一個 dict 結構使用兩個哈希表，也即是 d->ht[0] 和 d->ht[1] ，為了稱呼方便，我們將他們分別叫做 0 號和 1 號哈希表。
從上一節可以知道， dictCreate 并不為哈希表的鏈表數組分配內存( d->ht[0]->table 和 d->ht[1]->table 都被設為 NULL），那么，什么時候哈希表的鏈表數組會被初始化呢？
答案是，當首次通過 dictAdd 向字典添加元素的時候， 0 號哈希表的鏈表數組會被初始化。
首次向字典增加元素將執行以下的調用序列： dictAdd -> dictAddRaw -> _dictKeyIndex -> dictExpandIfNeeded -> dictExpand
其中 dictAdd 是 dictAddRaw 的調用者， dictAddRaw 是添加元素這一工作的底層實現，而 dictAddRaw 為了計算新元素的 key 的地址索引，會調用 _dictKeyIndex ：
dictEntry *dictAddRaw(dict *d, void *key)
{
// 被省略的代碼...
// 計算 key 的 index 值
// 如果 key 已經存在，_dictKeyIndex 返回 -1
if ((index = _dictKeyIndex(d, key)) == -1)
return NULL;
// 被省略的代碼...
} 然后 _dictKeyIndex 會在計算 地址索引前，會先調用 _dictExpandIfNeeded 檢查兩個哈希表是否有空間容納新元素：
static int _dictKeyIndex(dict *d, const void *key)
{
// 被省略的代碼...
/* Expand the hashtable if needed */
if (_dictExpandIfNeeded(d) == DICT_ERR)
return -1;
// 被省略的代碼...
} 到 _dictExpandIfNeeded 這步，一些有趣的事情就開始發生了， _dictExpandIfNeeded 會檢測到 0 號哈希表還沒有分配任何空間，于是它調用 dictExpand ，傳入 DICT_HT_INITIAL_SIZE 常量作為 0 號哈希表的初始大小（目前的版本 DICT_HT_INITIAL_SIZE = 4 )，為 0 號哈希表分配空間：
static int _dictExpandIfNeeded(dict *d)
{
// 被忽略的代碼...
/* If the hash table is empty expand it to the intial size. */
if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);
// 被忽略的代碼...
} dictExpand 會創建一個分配了鏈表數組的新哈希表，然后進行判斷，決定是該將新哈希表賦值給 0 號哈希表還是 1 號哈希表。
這里因為我們的 0 號哈希表的 size 還是 0 ，因此，這里會執行 if 語句的第一個 case ，將新哈希表賦值給 0 號哈希表：
int dictExpand(dict *d, unsigned long size)
{
// 被省略的代碼...
// 計算哈希表的(真正)大小
unsigned long realsize = _dictNextPower(size);
// 創建新哈希表
dictht n;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*)); // 分配鏈表數組
n.used = 0;
// 字典的 0 號哈希表是否已經初始化？
// 如果沒有的話，我們將新建哈希表作為字典的 0 號哈希表
if (d->ht[0].table == NULL) {
d->ht[0] = n;
} else {
// 否則，將新建哈希表作為字典的 1 號哈希表，并將它用于 rehash
d->ht[1] = n;
d->rehashidx = 0;
}
// 被省略的代碼...
} 字典的擴展和 1 號哈希表的創建
在 0 號哈希表創建之后，我們就有了一個可以執各式各樣操作（添加、刪除、查找，諸如此類）的字典實例了。
但是這里還有一個問題： 這個最初創建的 0 號哈希表非常小（當前版本的 DICT_HT_INITIAL_SIZE = 4)，它很快就會被元素填滿，這時候， rehash 操作就會被激活。
（字典的）哈希表的完整 rehash 操作分為兩步：
1） 首先就是創建一個比現有哈希表更大的新哈希表（expand）
2） 然后將舊哈希表的所有元素都遷移到新哈希表去（rehash）
當使用 dictAdd 對字典添加元素的時候， _dictExpandIfNeeded 會一直對 0 號哈希表的使用情況進行檢查（還記得 dictAdd 的調用鏈嗎？忘了的話翻到上一節去看看），當 rehash 條件被滿足的時候，它就會調用 dictExpand 函數，對字典進行擴展：
static int _dictExpandIfNeeded(dict *d)
{
// 被省略的代碼...
// expand 有兩種
// 1) used >= size 且 dict_can_resize 為真，正常 expand
// 2) dict_can_resize 不為真，但 used/size 大于指定比率，強制 expand
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
d->ht[0].size : d->ht[0].used)*2);
}
// 被省略的代碼...
} 可以看到，當代碼注釋中所說的兩種情況的其中一種被滿足的時候， dictExpand 函數就會被調用， 0 號哈希表的桶數量和節點數量兩個數值之間的較大者乘以 2 ，就會被作為第二個參數傳入 dictExpand 函數。
這次調用 dictExpand 函數執行的是和之前創建 0 號哈希表時不同的路徑 —— 這一次，程序執行的是 else case，它將新哈希表賦值給 1 號哈希表，并將字典的 rehashidx 屬性從 -1 改為 0：
int dictExpand(dict *d, unsigned long size)
{
// 被省略的代碼...
// 計算哈希表的(真正)大小
unsigned long realsize = _dictNextPower(size);
// 創建新哈希表
dictht n;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 字典的 0 號哈希表是否已經初始化？
// 如果沒有的話，我們將新建哈希表作為字典的 0 號哈希表
if (d->ht[0].table == NULL) {
d->ht[0] = n;
} else {
// 否則，將新建哈希表作為字典的 1 號哈希表，并將它用于 rehash
d->ht[1] = n;
d->rehashidx = 0;
}
// 被省略的代碼...
} 漸增式 rehash 和平攤操作
在上一節的最后，我們看到，當 expand 執行完畢之后，字典同時使用兩個哈希表，并且字典的 rehashidx 屬性從 -1 被改為 0 ，這是一個重要的改動，它標志著 rehash 可以進行了。
但是 rehash 操作在那里？我們什么時候調用它？嗯。。。源碼里的確有一個 dictRehash 函數，它可以將指定數量的元素從 0 號哈希表 rehash 到 1 號哈希表，但是，redis 并不是使用它一下子將 0 號哈希表的所有元素全都 rehash 到 1 號哈希表，因為這樣集中式的 rehash 會引起大量的計算工作（想一想，假如現在需要 rehash 的不是 4 個元素，而是 4 十萬個，4 千萬個，4 億呢？），進而影響整個系統的性能。
為了避免上面所說的問題， redis 采取了一種更平滑的 rehash 策略，redis 文檔里稱之為漸增式 rehash (incremental rehashing)，它將 rehash 操作平攤到 dictAddRaw 、dictGetRandomKey 、dictFind 、dictGenericDelete 這些函數里面，每當上面這些函數被執行的時候（或者其他人調用它們時）, _dictRehashStep 函數就會執行，將 1 個元素從 0 號哈希表 rehash 到 1 號哈希表，這樣就避免了集中式的 rehash 。
以下是 dictFind 函數，它是其中一個平攤 rehash 操作的函數：
dictEntry *dictFind(dict *d, const void *key)
{
// 被忽略的代碼...
// 檢查字典(的哈希表)能否執行 rehash 操作
// 如果可以的話，執行平攤 rehash 操作
if (dictIsRehashing(d)) _dictRehashStep(d);
// 被忽略的代碼...
} 其中 dictIsRehashing 就是檢查字典的 rehashidx 屬性是否不為 -1 ：
#define dictIsRehashing(ht) ((ht)->rehashidx != -1)
如果條件成立成立的話， _dictRehashStep 就會被執行，將一個元素從 0 號哈希表轉移到 1 號哈希表：
static void _dictRehashStep(dict *d) {
if (d->iterators == 0) dictRehash(d,1);
} （代碼中的 iterators == 0 表示在 rehash 時不能有迭代器，因為迭代器可能會修改元素，所以不能在有迭代器的情況下進行 rehash 。）
就這樣，如同愚公移山一般， 0 號哈希表的元素被逐個逐個地，從 0 號 rehash 到 1 號，最終整個 0 號哈希表被清空，這時 _dictRehashStep 再調用 dictRehash ，被清空的 0 號哈希表就會被刪除，然后原來的 1 號哈希表成為新的 0 號哈希表（當有需要再次進行 rehash 的時候，這個循環就會再次開始）：
int dictRehash(dict *d, int n) {
// 被忽略的代碼...
while(n--) {
dictEntry *de, *nextde;
// 0 號哈希表的所有元素 rehash 完畢？
if (d->ht[0].used == 0) {
zfree(d->ht[0].table); // 清空 0 號
d->ht[0] = d->ht[1]; // 用原來的 1 號代替 0 號
_dictReset(&d->ht[1]); // 重置 1 號哈希表
d->rehashidx = -1; // 重置字典的 rehash flag
return 0;
}
// 被忽略的代碼...
}
// 被忽略的代碼...
} 最后，還有之前一直都沒有提到的一個確保 rehash 得以最終完成的重要條件是：當 rehashidx 不等于 -1 ，也即是 dictIsRehashing 為真時，所有新添加的元素都會直接被加到 1 號數據庫，這樣 0 號哈希表的大小就會只減不增，最終 rehash 總會有完成的一刻（假如新加入的元素還繼續被放進 0 號哈希表，那么盡管平攤 rehash 一直在努力地進行，但說不定 rehash 還是永遠也完成不了）：
dictEntry *dictAddRaw(dict *d, void *key)
{
// 被省略的代碼...
// 如果字典正在進行 rehash ，那么將新元素添加到 1 號哈希表，
// 否則，使用 0 號哈希表
ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];
// 被省略的代碼...
} 最后：哈希表的大小
我們知道哈希表最初的大小是由 DICT_HT_INITIAL_SIZE 決定的，而當 rehash 開始之后，根據給定的條件，哈希表的大小就會發生變動：
static int _dictExpandIfNeeded(dict *d)
{
// 被省略的代碼...
if (d->ht[0].used >= d->ht[0].size &&
(dict_can_resize ||
d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))
{
return dictExpand(d, ((d->ht[0].size > d->ht[0].used) ?
d->ht[0].size : d->ht[0].used)*2);
}
// 被省略的代碼...
} 可以看到， d->ht[0].size 和 d->ht[0].used 兩個數之間的較大者乘以 2 ，會作為 size 參數被傳入 dictExpand 函數，但是，盡管如此，這個數值仍然還不是哈希表的最終大小，因為在 dictExpand 里面，_dictNextPower 函數會根據傳入的 size 參數計算出真正的表大小：
int dictExpand(dict *d, unsigned long size)
{
// 被省略的代碼...
// 計算哈希表的(真正)大小
unsigned long realsize = _dictNextPower(size);
// 創建新哈希表
dictht n;
n.size = realsize;
n.sizemask = realsize-1;
n.table = zcalloc(realsize*sizeof(dictEntry*));
n.used = 0;
// 被省略的代碼...
} 至于 _dictNextPower 函數，它不斷計算 2 的乘冪，直到遇到比 size 參數大的冪，就返回這個乘冪作為哈希表的大小：
static unsigned long _dictNextPower(unsigned long size)
{
unsigned long i = DICT_HT_INITIAL_SIZE;
if (size >= LONG_MAX) return LONG_MAX;
while(1) {
if (i >= size)
return i;
i *= 2;
}
} 雖然桶的元素個數 d->ht[0].size 剛開始是固定的(DICT_HT_INITIAL_SIZE)，但是，因為我們沒有辦法預知 d->ht[0].used 的值，所以我們沒有辦法預知哈希表的大小，不過，我們可以確定以下兩個哈希表大小的性質：
1） 哈希表的大小總是 2 的乘冪（也即是 2^N，此處 N 未知）
2）1 號哈希表的大小總比 0 號哈希表大
就這樣了！
對 redis 的 dict.c 和 dict.h 的源碼分析就到這了，本人一直認為，好的源碼分析應該能在不貼太多代碼的情況下把原理和流程講明白，在這篇文章我已經盡力地將實踐這個原則，不過因為是第 一次寫源碼分析類的文章，而且才剛開始讀 redis 的源碼，難免有不如人意之處，希望朋友們不吝指出。
dict 的結構本身還是很簡單的，唯一的遺憾是，dictht 作為字典的內部實現，本該被隱藏起來的，現在卻完全暴露了出來（什么， _dictReset(&d->ht[1])，你是說真的？），如果能在模塊化方面多做一點努力的話，代碼會更容易看一些，當然這里也有歷 史遺留的因素在里面。
最后， 我為 redis 的源碼分析項目專門建立了一個 github project ，上面有完整的源碼文件，大部分加上了注釋（目前只有 dict.c 和 dict.h），如果對代碼的完整細節有興趣，可以到上面去取： https://github.com/huangz1990/reading_redis_source