【死磕 Redis】----- Redis 數(shù)據(jù)結構：dict
字典，又稱映射，是一種用于保存鍵值對的抽象數(shù)據(jù)結構。在 Redis 中，字典得到了廣泛的使用，比如 Redis 的數(shù)據(jù)庫就是使用字典來作為底層實現(xiàn)的
Redis 中的字典有 dict.h/dict 結構表示，如下：
typedefstruct dict {
// 類型特定函數(shù)
// type里面主要記錄了一系列的函數(shù),可以說是規(guī)定了一系列的接口
dictType *type;
// 私有數(shù)據(jù)
// privdata保存了需要傳遞給那些類型特定函數(shù)的可選參數(shù)
void*privdata;
//兩張哈希表
dictht ht[2];
//rehash 索引，并沒有rehash時，值為 -1
long rehashidx;
//目前正在運行的安全迭代器的數(shù)量
unsignedlong iterators; /* number of iterators currently running */
} dict;
type：是一個指向 dictType 結構的指針，每個 dictType 結構保存了一簇用于操作特定類型鍵值對的函數(shù)，Redis 會為用途不同的字典設置不同的類型特定函數(shù)。
privdata：保存了需要傳給那些類型特定函數(shù)的可選參數(shù)
ht[2]：表示兩張 hash 表（dictht），一般情況下只使用 ht[0]，ht[1] 用于 rehash 時
rehashidx：記錄 rehash 目前的進度，如果目前沒有在進行 rehash，那么他的值就是 -1
結構如下圖：
Redis 字典底層是用哈希表（dictht）實現(xiàn)，dictht 結構如下：
typedefstruct dictht {
// 哈希表數(shù)組, 每個元素都是一條鏈表
dictEntry **table;
// 哈希表大小
unsignedlong size;
// 哈希表大小掩碼，用于計算索引值
// 總是等于 size - 1
unsignedlong sizemask;
// 該哈希表已有節(jié)點的數(shù)量
unsignedlong used;
} dictht;
table：是一個數(shù)組，數(shù)組中的每個元素都是一個指向 dictEntry 結構的指針，每個 dictEntry 結構都保存著一個鍵值對的鏈表
size：表示哈希表的大小
sizemask：哈希表大小掩碼，用于計算索引值，其值總是等于?
size-1used：表示該哈希表已有節(jié)點的數(shù)量
結構如下圖：
哈希表的節(jié)點用 dictEntry 表示，如下：
typedefstruct dictEntry {
// 鍵
void*key;
// 值
union{
void*val;
uint64_t u64;
int64_t s64;
double d;
} v;
// 指向下個哈希表節(jié)點，形成鏈表
struct dictEntry *next;
} dictEntry;
key：保存鍵值對中的鍵
v：保存鍵值對中的值，可以是一個指針，可以是unit64t的一個整數(shù)，也可以是int64t的一個整數(shù)
next：下一個哈希表結點的指針，采用“鏈地址法”解決鍵沖突
結構如下：
至此，整個字典的結構已經(jīng)介紹完畢，下圖是一個完整的結構圖：
當我們需要將一個鍵值對插入到字典里面，需要先用哈希函數(shù)計算 key 的哈希值，然后借助 sizemask 和 哈希值得到索引值 index，根據(jù)得到的索引值找到對應 dictEntry* 然后插入。插入節(jié)點和查找節(jié)點的邏輯其實和 HashMap 的 put 和 get 的邏輯沒區(qū)別，這里就不介紹，下面重點介紹 rehash 過程。
當哈希表的數(shù)據(jù)越來越多時，鏈表的長度就會越來越長，這樣查詢的效率就會降低，所以有必要進行哈希表擴展。而隨著元素的過期在不增加元素的前提下會導致哈希表的鍵值對很少但是 size 比較大，這個時候又會造成內存的浪費，所以有必要進行哈希表收縮。這里擴展、收縮的過程就是 rehash 的過程。
Redis 對字典的哈希表進行 rehash 的過程如下：
為 dict 的 ht[1] 分配內存空間，分配內存空間的大小取決于操作類型以及?
ht[0].used:如果執(zhí)行的操作是擴展操作，則 ht[1] 的大小為第一個大于等于 $ht[0].used * 2 * 2^n$ 的整數(shù)
如果執(zhí)行的操作是收縮操作，則 ht[1] 的大小為第一個大于等于 $ht[0].used * 2^n$ 的整數(shù)
重新計算 ht[0] 中所有的鍵值對，將其遷移到 ht[1] 指定的位置。需要注意的是，這個過程并不是一次性完成的，而是漸進式完成的。
當 ht[0] 中所有的鍵值對都遷移到 ht[1] 中去后（ht[0] 為空），則把 ht[0] 釋放掉，把ht[1] 設置為 ht[0] ，并重新在 ht[1] 上新建一個空表，為下次 rehash 做準備。
ht[0] 采用漸進式的方式將其中元素遷移到 ht[1] 中的主要原因為了避免對服務器性能造成影響，因為如果 ht[0] 中的元素非常多，幾百萬，幾千萬甚至上億，那么要一次性將這些鍵值對全部遷移到 ht[1] 中的話，龐大的計算可能會造成服務器在一定時間內停止服務，所以需要采用漸進式、分多次的方式進行 rehash。詳細步驟如下：
為 ht[1] 分配空間，讓字典同時持有 ht[0] 和 ht[1] 兩個哈希表
在字典中維持一個索引計數(shù)器變量 rehashidx，并將其值設置為 0，表示 rehash 過程正式開始
在 rehash 期間，每次對字典執(zhí)行任意操作時，程序除了執(zhí)行對應操作之外，還會順帶將 ht[0] 在 rehashidx 索引上的所有鍵值對 rehash 到 ht[1] ，操作完后將 rehashidx 的值加一
在 rehash 期間，對字典進行 ht[0].size 次操作之后，rehashidx 的值會增加到 ht[0].size，此時 ht[0] 的所有鍵值對都已經(jīng)遷移到 ht[1] 了，程序會將 rehashidx 重新置為-1，以此表示 rehash 完成
這里需要注意的是，在 rehash 的過程中，ht[0] 和 ht[1] 可能同時存在鍵值對，因此在執(zhí)行查詢操作的時候兩個哈希表都得查，而如果是執(zhí)行插入鍵值對操作，則直接在 ht[1] 上操作就行，不在 ht[0] 上進行任何的添加操作。
租后再說下 Redis 在什么條件下會對哈希表進行擴展或者收縮呢：
服務器當前沒有在執(zhí)行 BGSAVE 或 BGREWRITEAOF 命令且哈希表的負載因子大于等于 1 時進行擴展操作
服務器正在執(zhí)行 BGSAVE 或 BGREWRITEAO F命令且哈希表的負載因子大于等于5時進行擴展操作
當前負載因子小于0.1時進行收縮操作
之所以在服務器進行BGSAVE或BGREWRITEAOF的時候負載因子比較大才進行擴展操作是因為此時Redis會創(chuàng)建子進程，而大多數(shù)操作系統(tǒng)采取了寫時復制的技術來優(yōu)化子進程使用效率，不適合在這種時候會做大規(guī)模的數(shù)據(jù)遷移活動，說白了就是為了節(jié)約內存和提升效率）
參考
《Redis 設計與實現(xiàn)》
Redis之字典
【死磕 Redis】----- Redis 通信協(xié)議 RESP
【死磕 Redis】----- 理解 pipeline 管道
【死磕 Redis】-----如何排查 Redis 中的慢查詢