阿里面試官：談?wù)剬edis哈希表的理解
Hash表回顧
哈希表是一種存儲數(shù)據(jù)的結(jié)構(gòu)，他有很多名字(鍵值對、字典、符號表、映射、關(guān)聯(lián)數(shù)組)。在哈希表中，鍵和值是一一對應(yīng)的關(guān)系，一個鍵key對應(yīng)一個值value。哈希表這個數(shù)據(jù)結(jié)構(gòu)可以通過鍵key，在O(1)時間復(fù)雜度的情況下獲得對應(yīng)的值。
由于C語言自己沒有內(nèi)置哈希表這一數(shù)據(jù)結(jié)構(gòu)，因此Redis自己實現(xiàn)了Hash表。
哈希沖突及處理辦法
哈希表最關(guān)鍵的問題就在于哈希沖突。即，兩個項，經(jīng)過哈希函數(shù)計算，發(fā)現(xiàn)其對應(yīng)的存儲方式位置一致。對于這種情況，就需要進行進一步處理了。
解決哈希沖突的辦法
大家應(yīng)該背過我寫的數(shù)據(jù)結(jié)構(gòu)與算法八股文背誦版，還記得解決Hash沖突的方法嘛。
線性探查法(開放地址)。
這個方法的核心是：一旦碰見有沖突，該項往后順延.
來看個例子吧。
1.按hash算法，新鍵值對應(yīng)該存在箭頭所處位置，可惜該位置有值了：
開放地址法
2.因此需要存儲順延的位置：
開放地址法
3.順延位置也有值了，再往后順延
開放地址法
4.順延位置還是有值，再往后順延，終于存儲上了
開放地址法
鏈地址法(拉鏈法)
Redis采用的方法就是這種拉鏈法。來看下面例子。新鍵值對計算應(yīng)該存到二號，二號此時已經(jīng)有一個鍵值對了。因此，直接通過鏈表的方式掛到二號鍵值對1的下面。
拉鏈法
對于新的鍵值對也是如此，通過鏈表的方式掛到二號鍵值對2的下面。
Rehash
在講rehash之前，首先需要引入一個定義：負載因子。來看一下負載因子的定義吧：
負載因子 = 散列表內(nèi)元素個數(shù)/散列表的長度
如果負載因子高，就說明哈希沖突概率大，這樣會嚴(yán)重拖慢查找效率。
如果負載因子低，就說明這哈希表好像占用空間太多了，大部分空間都沒元素。
為了使負載因子值在合理范圍內(nèi)，程序需要對哈希表進行擴展或收縮。由于空間變大或縮小，之前的鍵在老表的存儲位置，在新表中就不一定一樣了，需要重新計算。這個重新計算，并把老表元素轉(zhuǎn)移到新表元素的過程就叫做rehash。當(dāng)然無論是java中的hashmap，concurrenthashmap，還是今天要講的Redis哈希表，都涉及rehash過程。
Redis中哈希表的數(shù)據(jù)結(jié)構(gòu)
來看一下Redis的Hash表邏輯設(shè)計結(jié)構(gòu) Redis的哈希表主要由三個結(jié)構(gòu)構(gòu)成：
dictht。單純表示一個哈希表
dictEntry。哈希表的一項，可以看作就是一個鍵值對
dict。Redis給外層調(diào)用的哈希表結(jié)構(gòu)，包含兩個dictht
- typedef struct dictht {
- dictEntry **table; //哈希表數(shù)組（哈希表項集合）
- unsigned long size; //Hash表大小
- unsigned long sizemask; //哈希表掩碼
- unsigned long used;//Hash表已使用的大小
- } dictht;
稍微解釋一下各個項。
- table：哈希表項的指針數(shù)組
- size：哈希表大小，這應(yīng)該不用多解釋吧
- sizemask:掩碼。這個值其實設(shè)計思想很棒，假設(shè)Redis長度是3，你想訪問第5個元素，如果按之前的方法，那肯定是訪問到超出redis哈希表范圍的地址空間了。所以redis規(guī)定，你想訪問元素，先把index與size做與，把超過redis長度的部分就截斷了，就不會發(fā)生內(nèi)存安全問題。
- Hash表已使用的大小。不解釋。
講了Hash表，來看看哈希項
- typedef struct dictEntry {
- void *key;
- union {
- void *val;
- uint64_t u64;
- int64_t s64;
- double d;
- } v;
- struct dictEntry *next;
- } dictEntry;
我們知道，Redis采用拉鏈法解決哈希沖突的問題。因此，Redis的哈希表項就有一個next指針，指向下一個元素，通過該指針，就可以訪問多個具有相同哈希值的鍵值對。
最后我們來看看dict結(jié)構(gòu)。
- typedef struct dict {
- dictType *type;
- void *privdata;
- dictht ht[2];
- int reshaidx;
- } dict;
大家肯定很好奇，好好的dict，搞兩個哈希表做啥?當(dāng)然也有不好奇的小伙伴，但沒辦法，架不住面試官也很好奇啊。
答案揭曉，兩個hash表是為了rehash。
那什么情況下需要rehash呢?
- 如果redis沒在執(zhí)行后臺備份，當(dāng)負載因子大于等于1就執(zhí)行。(反正CPU閑著也是閑著)
- 如果redis在執(zhí)行后臺備份，當(dāng)負載因子大于等于5就執(zhí)行。(CPU在干備份了，咱對于實在擠的表改一改，等CPU閑下來，再把稍微偏擠的rehash)
我們來看一下如果出現(xiàn)需要rehash的情況，需要的執(zhí)行步驟：
- 分配空間給ht[1]。分配空間由ht[0]的具體參數(shù)決定。
- 將ht[0]存儲的鍵值對，重新計算hash值和索引值，并賦值到ht[1]的對應(yīng)位置中。
- 當(dāng)賦值完成后，釋放ht[0]所占用空間，并把ht[0]指向ht[1]目前的地址。
- ht[1]指向空表。
漸進式rehash
由于步驟二采用的計算方式如果在一定時間做，占用資源過高，所以redis提出了漸進式rehash的方式。拿大白話來講，就是原來是一次，一次性的搬運，現(xiàn)在變成了分批搬運。
在分批搬運的過程中，難免會收到其他各式各樣的請求。
- 對于寫請求，即往redis哈希表增加新的鍵值對時，redis會把數(shù)據(jù)直接存放到ht[1]表中。
- 對于查請求，即查詢特定鍵對應(yīng)的值時，redis首先會在ht[0]中查找，如果查找失敗，就會在ht[1]表中查找。
- 對于更新請求，redis首先會在ht[0]中查找，如果查找失敗，就會在ht[1]表中更新。
- 對于刪除請求，redis首先會在ht[0]中查找，如果查找失敗，就會在ht[1]表中刪除。
參考
https://www.cnblogs.com/tekkaman/p/5141936.html
https://blog.csdn.net/yangbodong22011/article/details/78467583
Redis的設(shè)計與實現(xiàn)
Redis源碼剖析與實戰(zhàn)
