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)的字典:

- 介紹
- 前言
- 致謝
- 簡介
- 第一部分:數據結構與對象
- 簡單動態字符串
- SDS 的定義
- SDS 與 C 字符串的區別
- SDS API
- 重點回顧
- 參考資料
- 鏈表
- 鏈表和鏈表節點的實現
- 鏈表和鏈表節點的 API
- 重點回顧
- 字典
- 字典的實現
- 哈希算法
- 解決鍵沖突
- rehash
- 漸進式 rehash
- 字典 API
- 重點回顧
- 跳躍表
- 跳躍表的實現
- 跳躍表 API
- 重點回顧
- 整數集合
- 整數集合的實現
- 升級
- 升級的好處
- 降級
- 整數集合 API
- 重點回顧
- 壓縮列表
- 壓縮列表的構成
- 壓縮列表節點的構成
- 連鎖更新
- 壓縮列表 API
- 重點回顧
- 對象
- 對象的類型與編碼
- 字符串對象
- 列表對象
- 哈希對象
- 集合對象
- 有序集合對象
- 類型檢查與命令多態
- 內存回收
- 對象共享
- 對象的空轉時長
- 重點回顧
- 第二部分:單機數據庫的實現
- 數據庫
- 數據庫鍵空間
- 重點回顧
- RDB 持久化
- RDB 文件結構
- 重點回顧
- AOF 持久化
- AOF 持久化的實現
- 重點回顧
- 事件
- 文件事件
- 重點回顧
- 參考資料
- 客戶端
- 客戶端屬性
- 重點回顧
- 服務器
- 命令請求的執行過程
- 重點回顧
- 第三部分:多機數據庫的實現
- 復制
- 舊版復制功能的實現
- 重點回顧
- Sentinel
- 啟動并初始化 Sentinel
- 重點回顧
- 參考資料
- 集群
- 節點
- 重點回顧
- 第四部分:獨立功能的實現
- 發布與訂閱
- 頻道的訂閱與退訂
- 重點回顧
- 參考資料
- 事務
- 事務的實現
- 重點回顧
- Lua 腳本
- 創建并修改 Lua 環境
- 重點回顧
- 排序
- SORT <key> 命令的實現
- 重點回顧
- 二進制位數組
- GETBIT 命令的實現
- 重點回顧
- 慢查詢日志
- 慢查詢記錄的保存
- 慢查詢日志的閱覽和刪除
- 添加新日志
- 重點回顧
- 監視器
- 成為監視器
- 向監視器發送命令信息
- 重點回顧
- 源碼、相關資源和勘誤