騰訊面試官：說說Redis的哈希表是如何擴容的蚤假？
面試者：what吧兔？額......境蔼，（我懵了Ｋ磐ā）這個我還沒了解過罐监，尬...弓柱。但我了解java里面的HashMap的擴容侧但，我覺得應(yīng)該有相通的一些原理在里面吧禀横，然后我就把HashMap的擴容機制balabla的說了一遍......
Redis中使用哈希表作為底層實現(xiàn)的是叫做字典的數(shù)據(jù)結(jié)構(gòu)，字典又稱為符號表酿箭、關(guān)聯(lián)數(shù)組或映射(map)缭嫡。是一種保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)抬闷。
如果你對Java HashMap有所了解的話饶氏，那么Redis哈希表就是類似Java中HashMap。
由于Redis是用C語言寫的古程，所以要搞懂C的相關(guān)實現(xiàn)原理去看源碼的話就要對C語言有一定的了解挣磨。
目錄
1荤懂、哈希表結(jié)構(gòu)
哈希表例子
2节仿、字典數(shù)據(jù)結(jié)構(gòu)
字典例子
3、解決哈希沖突
4矾瘾、擴容/縮容——rehash
? ? ?4.1壕翩、對字典的哈希表rehash步驟
? ? ?4.2放妈、看一次哈希表rehash擴容過程
5、漸進式rehash
? ? ?5.1珍策、漸進式rehash步驟
? ? ?5.2、看下一次完整的漸進式rehash擴容的過程
6唉堪、總結(jié)
【彩蛋】??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?1肩民、哈希表結(jié)構(gòu)
哈希表是由dictht結(jié)構(gòu)體定義持痰，table是一個數(shù)組工窍，數(shù)組中每個元素是一個指向dictEntry結(jié)構(gòu)的指針患雏。
?dictEntry是哈希表的節(jié)點淹仑，每個節(jié)點保存著一個鍵值對key、value颜阐，value可以是一個指針凳怨、或者是一個unit64_t或int64_t整數(shù)是鬼。
next屬性則是一個指向另一個哈希表節(jié)點的指針，形成一個鏈表弊琴，主要也是為了解決哈希沖突問題敲董。
哈希表例子
索引值相同的兩個節(jié)點使用鏈表連接起來
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 2腋寨、字典數(shù)據(jù)結(jié)構(gòu)
其實說到哈希表的話順便要了解下字典這種數(shù)據(jù)結(jié)構(gòu)萄窜，畢竟它的底層就是哈希表來實現(xiàn)撒桨，可以了解下擴容縮容相關(guān)的凤类。
type：指向dictType指針谜疤，保存了操作特定類型鍵值對的函數(shù)夷磕，Redis為不同用途的字典設(shè)置不同的類型特定函數(shù)坐桩。
privdata：保存了需要傳遞給不同特定函數(shù)的可選參數(shù)。
ht[2]：兩個哈希表陡鹃，字典使用的哈希表是ht[0]萍鲸，ht[1]則是當(dāng)對ht[0]哈希表進行rehash時使用擦俐。
trehashidx：記錄當(dāng)前rehash進度，沒有進行rehash則為-1品擎。
字典例子
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3萄传、解決哈希沖突
將一個鍵值對添加到字典時秀菱，需要計算其哈希值和索引值蹭睡，接著根據(jù)索引值將新節(jié)點放到哈希表數(shù)組的指定索引上肩豁。
計算哈希值：
hash = dict->type->hashFunction(key)
計算索引值：
hash & dict->ht[x].sizemask
鍵沖突：當(dāng)兩個或以上數(shù)量的鍵進行哈希之后索引值一樣清钥，也就是說兩個節(jié)點要放在同一個同桶里循捺，這時可能就會存在覆蓋(沖突)雄人，那么就得解決這種沖突了础钠。
Redis解決鍵沖突的方法：鏈地址法(separate chaining)——拉鏈法，假設(shè)你已了解Java HashMap原理踩萎，這里鏈地址法原理就不細(xì)說了香府。
? ? ? &插入一個題外話(也是筆者遇過的一道面試題)：解決哈希沖突有什么方法企孩？答案：①再? ? ? ? ? ?哈希法勿璃；②鏈地址法；③開放地址法歧沪；④建立公共溢出區(qū)诊胞。（每種方法可以自行簡單? ? ? ? ? ? 了解下即可）
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?4胁编、擴容/縮容——rehash
首先嬉橙，我們要清楚為什么要進行擴容或縮容市框？
擴容原因：當(dāng)hashtable存儲的元素過多，可能由于碰撞也過多喻圃，導(dǎo)致其中某天鏈表很長斧拍，最后致使查找和插入時間復(fù)雜度很大肆汹。因此當(dāng)元素超多一定的時候就需要擴容予权。
縮容原因：當(dāng)元素數(shù)量比較少的時候就需要縮容以節(jié)約不必要的內(nèi)存扫腺。
為了讓哈希表的負(fù)載因子（load factor）維持在一個合理的范圍內(nèi)笆环，會使用rehash（重新散列）操作對哈希表進行相應(yīng)的擴展或收縮躁劣。
負(fù)載因子的計算公式：
哈希表已保存節(jié)點數(shù)量 / 哈希表大小?load_factor = ht[0].used / ht[0].size
擴容的條件：（滿足任一即可）
1）Redis服務(wù)器目前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令习绢，并且哈希表的負(fù)載因子
大于等于1蝙昙。
2）Redis服務(wù)器目前在執(zhí)行BGSAVE或BGREWRITEAOF命令奇颠，并且哈希表的負(fù)載因子
大于等于5烈拒。
（此處為什么負(fù)載因子不同呢荆几？）
縮容的條件：哈希表的負(fù)載因子小于0.1吨铸。
4.1祖秒、對字典的哈希表rehash步驟
1）為ht[1]分配空間
擴展操作竭缝，那么ht[1] 的大小為第一個大于等于ht[0] .used*2的2的n次冪
收縮操作抬纸，那么ht[1] 的大小為第一個大于等于ht[0].used 的2的n次冪
2）將ht[0]中的數(shù)據(jù)轉(zhuǎn)移到ht[1]中湿故，在轉(zhuǎn)移的過程中，重新計算鍵的哈希值和索引值歌焦，然后將鍵值對放置到ht[1]的指定位置。
3）當(dāng)ht[0]的所有鍵值對都遷移到了ht[1]之后（ht[0]變?yōu)榭毡恚┰晁瑢t[0]釋放战转，然后將ht[1]設(shè)置成ht[0]槐秧，最后為ht[1]分配一個空白哈希表：
4.2刁标、看一次哈希表rehash擴容過程
1）開始rehash之前
2）為ht[1]分配空間膀懈，ht[0].used當(dāng)前值為4，8恰好是第一個大于等于4的2的N次冪硼控，那么當(dāng)前就會將ht[1]哈希表大小設(shè)置為8牢撼。
3）將ht[0]的鍵值對都rehash到ht[1]
4）釋放ht[0]，將ht[1]設(shè)置為ht[0]纳决，ht[1]再設(shè)置為空的哈希表
為什么BGSAVE或BGREWRITEAOF命令是否在執(zhí)行阔加，Redis服務(wù)器哈希表執(zhí)行擴容所需的負(fù)載因子不相同（1或5）胜榔？
因為當(dāng)執(zhí)行BGSAVE或BGREWRITEAOF命令過程中，Redis需要創(chuàng)建服務(wù)器進程的子進程湃番，操作系統(tǒng)采用的是COW夭织，即寫時復(fù)制copy-on-write的技術(shù)來優(yōu)化子進程的使用效率。所以在子進程存在時吠撮，服務(wù)器會提高執(zhí)行擴容所需的負(fù)載因子尊惰，從而盡可能避免在子進程存在期間進行擴容，可以避免不必要的內(nèi)存寫入操作泥兰，最大限度節(jié)約內(nèi)存弄屡。? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 5鞋诗、漸進式rehash
為什么需要漸進式rehash呢膀捷？
在元素數(shù)量較少時，rehash會非诚鞅颍快的進行全庸，但是當(dāng)元素數(shù)量達到幾百秀仲、甚至幾個億時進行rehash將會是一個非常耗時的操作。如果一次性將成萬上億的元素的鍵值對rehash到ht[1]壶笼，龐大的計算量可能會導(dǎo)致服務(wù)器在一段時間內(nèi)停止服務(wù)啄育，這是非常危險的！所以拌消，rehash這個動作不能一次性挑豌、集中式的完成，而是分多次墩崩、漸進式地完成氓英。
5.1、漸進式rehash步驟：
1）為ht[1]分配空間鹦筹，讓字典同時持有ht[0]和ht[1]兩個哈希表铝阐。
2）在字典中維持一個索引計數(shù)器變量rehashidx，并將它的值設(shè)置為0铐拐，表示rehash工作
正式開始徘键。
3）在rehash進行期間，每次對字典執(zhí)行CRUD：添加遍蟋、刪除吹害、查找或者更新操作時，程序除了執(zhí)行指定的操作以外虚青，還會順帶將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]它呀，當(dāng)rehash工作完成之后，程序?qū)?b>rehashidx+1(表示下次將rehash下一個桶)棒厘。
4）隨著字典操作的不斷執(zhí)行纵穿，最終在某個時間點上，ht[0]的所有鍵值對都會被rehash至ht[1]奢人，這時程序?qū)ehashidx屬性的值設(shè)為-1谓媒，表示rehash完成。
漸進式rehash的好處在于它采取??分而治之??的方式何乎，將rehash鍵值對所需的計算工作均攤到對字典的每個添加句惯、刪除、查找和更新操作上宪赶，從而避免了集中式rehash 而帶來的龐大計算量宗弯。
5.2脯燃、看下一次完整的漸進式rehash擴容的過程
1）準(zhǔn)備進行漸進式rehash
2）此時rehashidx=0,也就是會將索引為0的鍵值對進行遷移
3）接著搂妻，rehashidx繼續(xù)遞增，假如到最后將索引3的進行遷移辕棚，如下：
4）漸進式rehash結(jié)束
了解了漸進式rehash的原理和過程赛蔫，那么可能會有下面這些疑問：
在遷移的過程中昔园，會不會造成讀少數(shù)據(jù)？
不會详恼，因為在遷移時，首先會從ht[0]讀取數(shù)據(jù)引几，如果ht[0]讀不到昧互，則會去ht[1]讀。
在遷移過程中伟桅，新增加的數(shù)據(jù)會存放在哪個ht敞掘？
遷移過程中，新增的數(shù)據(jù)只會存在ht[1]中楣铁，而不會存放到ht[0]玖雁，ht[0]只會減少不會新增。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?6盖腕、總結(jié)
1）字典被Redis廣泛應(yīng)用于各種功能赫冬，比如數(shù)據(jù)庫和哈希鍵。
2）Redis字典底層是有哈希表實現(xiàn)溃列，每個字典包含兩個哈希表ht[0]劲厌、ht[1]，ht[1]在rehash時才有作用听隐。
3）哈希表使用鏈地址法解決哈希沖突脊僚，被分配到同一個索引的鍵值對會連接成一個單向鏈表。
4）哈希表進行rehash不是一次性完成遵绰，而是分多次辽幌、漸進式完成的。
5）哈希表rehash的條件：
擴容：（滿足任一即可）
a）Redis服務(wù)器目前沒有在執(zhí)行BGSAVE或BGREWRITEAOF命令椿访，且哈希表負(fù)載因子
大于等于1乌企。
b）Redis服務(wù)器目前在執(zhí)行BGSAVE或BGREWRITEAOF命令，且哈希表的負(fù)載因子
大于等于5成玫。
縮容：哈希表的負(fù)載因子小于0.1加酵。
6）BGSAVE或BGREWRITEAOF命令是否在執(zhí)行，Redis服務(wù)器哈希表執(zhí)行擴容所需的負(fù)載因子不相同哭当。因為此時子進程使用寫時復(fù)制copy on write猪腕，需要占用一定的內(nèi)存，所以需要提高擴容所需的負(fù)載因子钦勘，從而盡可能避免在子進程存在期間進行擴容陋葡，可以避免不必要的內(nèi)存寫入操作，最大限度節(jié)約內(nèi)存彻采。
【彩蛋】
了解了Redis字典哈希表擴容腐缤，那么你知道與Java ConcurrentHashMap(1.8)擴容有什么不同捌归？
也就是引出這個問題：
Redis的字典漸進式擴容與ConcurrentHashMap的擴容策略比較？那么他們在擴容岭粤、CRUD時有什么區(qū)別呢惜索？
1）擴容所花費的時間對比
一個單線程漸進擴容，一個多線程協(xié)同擴容剃浇。在平均的情況下巾兆，是ConcurrentHashMap快。這也意味著虎囚，擴容時所需要
花費的空間能夠更快的進行釋放臼寄。
2）讀操作，兩者的性能相差不多溜宽。
3）寫操作吉拳，Redis的字典返回更快些，因為它不像ConcurrentHashMap那樣去幫著擴容(當(dāng)要寫的桶位已經(jīng)搬到了newTable時)适揉，等擴容完才能進行操作留攒，而redis則是直接將新加的元素添加到ht[1]。
4）刪除操作嫉嘀，與寫一樣炼邀。
最后，我們應(yīng)該選擇單線程漸進式擴容還是選擇多線程協(xié)同式擴容剪侮？具體問題具體分析：
1）如果內(nèi)存資源吃緊拭宁，希望能夠進行快速的擴容方便釋放擴容時需要的輔助空間，且那么選擇后者瓣俯。
2）如果對于寫和刪除操作要求迅速杰标，那么可以選擇前者。
原文：https://mp.weixin.qq.com/s/ngph02-IQGu2Q9GBsSNeww
參考資料：
#1《redis設(shè)計與實現(xiàn)》
#2 https://blog.csdn.net/jiji1995/article/details/64127460
#3 https://blog.csdn.net/u010710458/article/details/80604740
#4 源碼分析：http://www.reibang.com/p/a57a6e389a03
