Redis 字典結構細談
Redis 字典底層基於哈希表實現。
一、哈希表結構
1、dictht：
typedef struct dictht {
dictEntry **table; //哈希表數組，存儲具體的鍵值對元素，對象類型 dictEntry
unsigned long size; //哈希表容量
unsigned long sizemask; //哈希表大小掩碼，計算索引使用
unsigned long used; //已使用容量
} dictht
2、示例數據：
二、哈希表節點
1、dictEntry：
typedef struct dictEntry {
void *key; //鍵值對 key
union{ //鍵值對 value 三種類型
void *val;
uint64_tu64;
int64_ts64;
} v;
struct dictEntry *next; //下一個節點指針
} dictEntry;
說明：next 為指向下一個節點的指針，是我們熟悉的鏈表節點結構，單向鏈表，用於處理鍵哈希衝突問題。
相同哈希值的鍵的鍵值對會以鏈表的形式存在同一位置。
2、示例數據：
三、Redis 字典
1、dict：
typedef struct dict{
dictType *type; //類型特定函數
void *privdata; //私有數據
dictht ht[2]; //哈希表數組，類型為dictht，ht[0]為實際存儲數據使用，ht[1] 為rehash時使用
int rehashidx; //rehash進度標誌，-1 代表當前不在 rehash
} dict
2、示例數據：
四、添加元素
向字典中添加元素主要涉及一下幾步操作：
1、計算鍵值對鍵的哈希值
hash：dict->type->hashFunction(key)
使用dictType內部的哈希函數得到鍵哈希值
2、計算需要放入的位置索引
index：hash&dict->ht[0].sizemask
使用上一步計算得到的哈希值與哈希表的sizemask屬性進行與操作得到需要放入的位置索引值
3、鍵衝突解決
沒有完美的哈希函數，哈希衝突往往無法避免，當多個鍵被所引導同一個位置時，這種現象，我們稱之為鍵衝突。
解決間衝突，Redis 採用鏈地址法，也即將衝突的鍵值對組成一條鏈條放到同一個哈希位置上。上面第二節我們介紹過 dictEntry的結構，其中包含一個指向另一個節點的指針next。
這裡需要說明的一點是，衝突節點插入時，是插入到鏈表的頭部，這樣只需要執行操作一次操作即可，也即時間複雜度為O(1)。
如下圖：（k2，v2）與（k1，v1）發生衝突，直接將（k2，v2）插入到鏈表頭部：
五、rehash
rehash過程是在重新規劃哈希表佔用空間時發生的。
負載因子 load_factor：已保存節點數量（dict.ht[0].used）/ 哈希表容量（dict.ht[0].size）
負載因子用以表名當前哈希表的使用狀態，它需要保持在一個合理的範圍，以保障資源的最優利用。通常需要適時的對哈希表進行擴展或者收縮來對負載因子進行維護，而這個過程，我們稱之為 rehash。
這裡涉及到一個問題，就是什麼時候需要進行伸縮維護？
1、擴展時機：
當前無bgsave及bgrewriteaop操作，load_factor >= 1
當前存在bgsave及bgrewriteaop操作，load_factor >= 5
Redis服務器通過fork子進程形式執行bgsave及bgrewriteaop操作，此時整個服務的資源耗費較大，為了避免可能發生的rehash帶來額外的資源壓力，此期間，服務器會調高觸發執行擴展操作的負載因子界限。
2、收縮時機：
load_factor < 0.1
3、rehash 基本操作：
a) 為dict.ht[1]分配空間：
空間大小計算如下：
擴展：最小n滿足2n >= dict.ht[0].used * 2
收縮：最小n滿足2n >= dict.ht[0].used
如下圖：ht[0].used = 3，假定無bg相關任務，則h[1]大小需要計算：2n >= 3 * 2 = 6
n = 3，ht[1].size = 23 = 8
b) rehash
對於dict.ht[0] 中的元素，依據dict.ht[1]特性（sizemask）重新計算索引值，並放置到dict.ht[1]中。
c) 當所有元素遷移完畢，釋放dict.ht[0]，並將dict.ht[1]設置為dict.ht[0]，重新在dict.ht[1]上創建空的哈希表。
六、漸進式rehash
所謂漸進式，是針對大數據量字典數據。直接一次性的執行rehash會導致服務資源的集中佔用，影響正常的服務響應。因此需要進行分而治之。
這裡會用到上面我們介紹的dict字典結構中的 rehashidx屬性，用以標識當前rehash進度。
首先將rehashidx置0，標示rehash開始，每次rehash一個元素，rehashidx值增加1，當最終所有元素rehash完成，將rehashidx置-1。
這裡需要說明下rehash中對正常的服務請求的處理：
1、刪除、查找、更新：
會涉及到兩個哈希表（ht[0]、ht[1]）操作，如查找元素，首先嘗試在ht[0]上查找，找不到，則繼續在h[1]上查找。
2、添加
添加元素只會在h[1]上操作，h[0]上只減不增。
