Redis 的字典使用哈希表作為底層實現， 一個哈希表里面可以有多個哈希表節點， 而每個哈希表節點就保存了字典中的一個鍵值對。 接下來的三個小節將分別介紹 Redis 的哈希表、哈希表節點、以及字典的實現。 ## 哈希表 Redis 字典所使用的哈希表由?`dict.h/dictht`?結構定義： ~~~ typedef struct dictht { // 哈希表數組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼，用于計算索引值 // 總是等于 size - 1 unsigned long sizemask; // 該哈希表已有節點的數量 unsigned long used; } dictht; ~~~ `table`?屬性是一個數組， 數組中的每個元素都是一個指向?`dict.h/dictEntry`?結構的指針， 每個?`dictEntry`?結構保存著一個鍵值對。 `size`?屬性記錄了哈希表的大小， 也即是?`table`?數組的大小， 而?`used`?屬性則記錄了哈希表目前已有節點（鍵值對）的數量。 `sizemask`?屬性的值總是等于?`size?-?1`?， 這個屬性和哈希值一起決定一個鍵應該被放到?`table`?數組的哪個索引上面。 圖 4-1 展示了一個大小為?`4`?的空哈希表 （沒有包含任何鍵值對）。  ## 哈希表節點 哈希表節點使用?`dictEntry`?結構表示， 每個?`dictEntry`?結構都保存著一個鍵值對： ~~~ typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下個哈希表節點，形成鏈表 struct dictEntry *next; } dictEntry; ~~~ `key`?屬性保存著鍵值對中的鍵， 而?`v`?屬性則保存著鍵值對中的值， 其中鍵值對的值可以是一個指針， 或者是一個?`uint64_t`?整數， 又或者是一個?`int64_t`?整數。 `next`?屬性是指向另一個哈希表節點的指針， 這個指針可以將多個哈希值相同的鍵值對連接在一次， 以此來解決鍵沖突（collision）的問題。 舉個例子， 圖 4-2 就展示了如何通過?`next`?指針， 將兩個索引值相同的鍵?`k1`?和?`k0`?連接在一起。  ## 字典 Redis 中的字典由?`dict.h/dict`?結構表示： ~~~ typedef struct dict { // 類型特定函數 dictType *type; // 私有數據 void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 // 當 rehash 不在進行時，值為 -1 int rehashidx; /* rehashing not in progress if rehashidx == -1 */ } dict; ~~~ `type`?屬性和?`privdata`?屬性是針對不同類型的鍵值對， 為創建多態字典而設置的： * `type`?屬性是一個指向?`dictType`?結構的指針， 每個?`dictType`?結構保存了一簇用于操作特定類型鍵值對的函數， Redis 會為用途不同的字典設置不同的類型特定函數。 * 而?`privdata`?屬性則保存了需要傳給那些類型特定函數的可選參數。 ~~~ typedef struct dictType { // 計算哈希值的函數 unsigned int (*hashFunction)(const void *key); // 復制鍵的函數 void *(*keyDup)(void *privdata, const void *key); // 復制值的函數 void *(*valDup)(void *privdata, const void *obj); // 對比鍵的函數 int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 銷毀鍵的函數 void (*keyDestructor)(void *privdata, void *key); // 銷毀值的函數 void (*valDestructor)(void *privdata, void *obj); } dictType; ~~~ `ht`?屬性是一個包含兩個項的數組， 數組中的每個項都是一個?`dictht`?哈希表， 一般情況下， 字典只使用?`ht[0]`?哈希表，?`ht[1]`?哈希表只會在對?`ht[0]`?哈希表進行 rehash 時使用。 除了?`ht[1]`?之外， 另一個和 rehash 有關的屬性就是?`rehashidx`?： 它記錄了 rehash 目前的進度， 如果目前沒有在進行 rehash ， 那么它的值為?`-1`?。 圖 4-3 展示了一個普通狀態下（沒有進行 rehash）的字典：