App下載

阿里面試官:HashMap 熟悉吧?好的,那就來(lái)聊聊 Redis 字典吧!

猿友 2020-09-04 10:29:57 瀏覽數(shù) (4194)
反饋

文章轉(zhuǎn)載自公眾號(hào):Java極客技術(shù) 作者:鴨血粉絲

最近,阿粉的一個(gè)朋友出去面試,回來(lái)跟阿粉抱怨,面試官不按套路出牌,直接打亂了他的節(jié)奏。

事情是這樣的,前面面試問(wèn)了幾個(gè) Java 的相關(guān)問(wèn)題,我朋友回答還不錯(cuò),接下來(lái)面試官就問(wèn)了一句:看來(lái) Java 基礎(chǔ)還不錯(cuò),Java HashMap 你熟悉吧?

我朋友回答。工作經(jīng)常用,有看過(guò)源碼。

我朋友本來(lái)想著,你隨便來(lái)吧,這個(gè)問(wèn)題之前已經(jīng)準(zhǔn)備好了,隨便問(wèn)吧。

誰(shuí)知道,面試官下面一句:

「那好的,我們來(lái)聊聊 Redis 字典吧?!?/strong>

直接將他整蒙逼。

阿粉的朋友由于沒(méi)怎么研究過(guò) Redis 字典,所以這題就直接回答不知道了。

「當(dāng)然,如果面試中真不知道,那就回答不了解,直接下一題,不要亂答?!?/strong>

不過(guò)這一題,阿粉覺(jué)得還是很可惜,其實(shí) Redis 字典基本原理與 HashMap 差不多,那我們其實(shí)可以套用這其中的原理,不求回答滿分,但是怎么也可以得個(gè)及格分吧~

面試過(guò)程真要碰到這個(gè)問(wèn)題,我們可以從下面三個(gè)方面回答。

  • 數(shù)據(jù)結(jié)構(gòu)
  • 元素增加過(guò)程
  • 擴(kuò)容

字典數(shù)據(jù)結(jié)構(gòu)

說(shuō)起字典,也許大家比較陌生,但是我們都知道 Redis 本身提供 KV 查詢的方式,這個(gè) KV 就是其實(shí)通過(guò)底層就是通過(guò)字典保存。

另外,Redis 支持多種數(shù)據(jù)類型,其中一種類型為 Hash 鍵,也可以用來(lái)存儲(chǔ) KV 數(shù)據(jù)。

阿粉剛開(kāi)始了解的這個(gè)數(shù)據(jù)結(jié)構(gòu)的時(shí)候,本來(lái)以為這個(gè)就是使用字典實(shí)現(xiàn)。其實(shí)并不是這樣的,初始創(chuàng)建 Hash 鍵,默認(rèn)使用另外一種數(shù)據(jù)結(jié)構(gòu)-「ZIPLIST」(壓縮列表),以此節(jié)省內(nèi)存空間。

不過(guò)一旦以下任何條件被滿足,Hash 鍵的數(shù)據(jù)結(jié)構(gòu)將會(huì)變?yōu)樽值?,加快查詢速度?/p>

  • 哈希表中某個(gè)鍵或某個(gè)值的長(zhǎng)度大于 server.hash_max_ziplist_value (默認(rèn)值為 64 )。
  • 壓縮列表中的節(jié)點(diǎn)數(shù)量大于 server.hash_max_ziplist_entries (默認(rèn)值為 512 )。

Redis 字典新建時(shí)默認(rèn)將會(huì)創(chuàng)建一個(gè)哈希表數(shù)組,保存兩個(gè)哈希表。

其中 ht[0] 哈希表在第一次往字典中添加鍵值時(shí)分配內(nèi)存空間,而另一個(gè) ht[1] 將會(huì)在下文中擴(kuò)容/縮容才會(huì)進(jìn)行空間分配。

空間分配

字典中哈希表其實(shí)就等同于Java HashMap,我們知道 Java 采用數(shù)組加鏈表/紅黑樹(shù)的實(shí)現(xiàn)方式,其實(shí)哈希表也是使用類似的數(shù)據(jù)結(jié)構(gòu)。

哈希表結(jié)構(gòu)如下所示:

哈希表結(jié)構(gòu)

其中 table 屬性是個(gè)數(shù)組, 其中數(shù)組元素保存一種 dictEntry的結(jié)構(gòu),這個(gè)結(jié)構(gòu)完全類似與 HashMap 中的 Entry 類型,這個(gè)結(jié)構(gòu)存儲(chǔ)一個(gè) KV 鍵值對(duì)。

同時(shí),為了解決 hash 碰撞的問(wèn)題,dictEntry 存在一個(gè) next 指針,指向下一個(gè)dictEntry ,這樣就形成 dictEntry 的鏈表。

HashMap

現(xiàn)在,我們回頭對(duì)比 JavaHashMap,可以發(fā)現(xiàn)兩者數(shù)據(jù)結(jié)構(gòu)基本一致。

只不過(guò) HashMap 為了解決鏈表過(guò)長(zhǎng)問(wèn)題導(dǎo)致查詢變慢,JDK1.8 時(shí)在鏈表元素過(guò)多時(shí)采用紅黑樹(shù)的數(shù)據(jù)結(jié)構(gòu)。

下面我們開(kāi)始添加新元素,了解這其中的原理。

元素增加過(guò)程

當(dāng)我們往一個(gè)新字典中添加元素,默認(rèn)將會(huì)為字典中 ht[0] 哈希表分配空間,默認(rèn)情況下哈希表 table 數(shù)組大小為 4(「DICT_HT_INITIAL_SIZE」)。

新添加元素的鍵值將會(huì)經(jīng)過(guò)哈希算法,確定哈希表數(shù)組的位置,然后添加到相應(yīng)的位置,如圖所示:

新添加元素的鍵值

繼續(xù)增加元素,此時(shí)如果兩個(gè)不同鍵經(jīng)過(guò)哈希算法產(chǎn)生相同的哈希值,這樣就發(fā)生了哈希碰撞。

假設(shè)現(xiàn)在我們哈希表中擁有是三個(gè)元素,:

哈希表中擁有三個(gè)元素

我們?cè)僭黾右粋€(gè)新元素,如果此時(shí)剛好在數(shù)組 3 號(hào)位置上發(fā)生碰撞,此時(shí) Redis 將會(huì)采用鏈表的方式解決哈希碰撞。

解決哈希碰撞

「注意,新元素將會(huì)放在鏈表頭結(jié)點(diǎn),這么做目的是因?yàn)樾略黾拥脑兀艽蟾怕噬蠒?huì)被再次訪問(wèn),放在頭結(jié)點(diǎn)增加訪問(wèn)速度?!?/strong>

這里我們?cè)趯?duì)比一下元素添加過(guò)程,可以發(fā)現(xiàn) Redis 流程其實(shí)與 JDK 1.7 版本的 HashMap 類似。

當(dāng)我們?cè)卦黾釉絹?lái)越多時(shí),哈希碰撞情況將會(huì)越來(lái)越頻繁,這就會(huì)導(dǎo)致鏈表長(zhǎng)度過(guò)長(zhǎng),極端情況下 O(1) 查詢效率退化成 O(N) 的查詢效率。

為此,字典必須進(jìn)行擴(kuò)容,這樣就會(huì)使觸發(fā)字典 rehash 操作。

擴(kuò)容

當(dāng) Redis 進(jìn)行 Rehash 擴(kuò)容操作,首先將會(huì)為字典沒(méi)有用到 ht[1]哈希表分配更大空間。

哈希表分配更大空間

?

畫(huà)外音:ht[1] 哈希表大小為第一個(gè)大于等于ht[0].used*2 的 2^2(2的n 次方冪)

?

然后再將 ht[0] 中所有鍵值對(duì)都遷移到 ht[1] 中。

簡(jiǎn)單起見(jiàn),忽略指向空節(jié)點(diǎn)

簡(jiǎn)單起見(jiàn),忽略指向空節(jié)點(diǎn)

當(dāng)節(jié)點(diǎn)全部遷移完畢,將會(huì)釋放 ht[0]占用空間,并將 ht[1] 設(shè)置為 ht[0]。

擴(kuò)容 操作

擴(kuò)容 操作需要將 ht[0]所有鍵值對(duì)都 Rehashht[1] 中,如果鍵值過(guò)多,假設(shè)存在十億個(gè)鍵值對(duì),這樣一次性的遷移,勢(shì)必導(dǎo)致服務(wù)器會(huì)在一段時(shí)間內(nèi)停止服務(wù)。

另外如果每次 rehash 都會(huì)阻塞當(dāng)前操作,這樣對(duì)于客戶端處理非常不友好。

為了避免 rehash對(duì)服務(wù)器的影響,Redis 采用漸進(jìn)式的遷移方式,慢慢將數(shù)據(jù)遷移分散到多個(gè)操作步驟。

這個(gè)操作依賴字典中一個(gè)屬性 rehashidx,這是一個(gè)索引位置計(jì)數(shù)器,記錄下一個(gè)哈希表 table 數(shù)組上元素,默認(rèn)情況為值為 「-1」。

假設(shè)此時(shí)擴(kuò)容前字典如圖所示:

擴(kuò)容前字典

當(dāng)開(kāi)始 rehash 操作,rehashidx將會(huì)被設(shè)置為 「0」 。

這個(gè)期間每次收到增加,刪除,查找,更新命令,除了這些命令將會(huì)被執(zhí)行以外,還會(huì)順帶將 ht[0]哈希表在 rehashidx 位置的元素 rehash 到 ht[1] 中。

假設(shè)此時(shí)收到一個(gè) 「K3」 鍵的查詢操作,Redis 首先執(zhí)行查詢操作,接著 Redis 將會(huì)為 ht[0]哈希表上table 數(shù)組第 rehashidx索引上所有節(jié)點(diǎn)都遷移到 ht[1] 中。

索引節(jié)點(diǎn)遷移

當(dāng)操作完成之后,再將 rehashidx 屬性值加 1。

最后當(dāng)所有鍵值對(duì)都 rehashht[1]中時(shí),rehashidx將會(huì)被重新設(shè)置為 -1。

雖然漸進(jìn)式的 rehash 操作減少了工作量,但是卻帶來(lái)鍵值操作的復(fù)雜度。

這是因?yàn)樵跐u進(jìn)式 rehash 操作期間,Redis 無(wú)法明確知道鍵到底在ht[0]中,還是在 ht[1] 中,所以這個(gè)時(shí)候 Redis 不得不查找兩個(gè)哈希表。

以查找為例,Redis 首先查詢 ht[0] ,如果沒(méi)找到將會(huì)繼續(xù)查找 ht[1],除了查詢以外,更新,刪除也會(huì)執(zhí)行如上的操作。

添加操作其實(shí)就沒(méi)這么麻煩,因?yàn)?code>ht[0]不會(huì)在使用,那就統(tǒng)一都添加到 ht[1] 中就好了。

最后我們?cè)賹?duì)比一下 Java HashMap 擴(kuò)容操作,它是一個(gè)一次性操作,每次擴(kuò)容需要將所有鍵值對(duì)都遷移到新的數(shù)組中,所以如果數(shù)據(jù)量很大,消耗時(shí)間就會(huì)久。

總結(jié)

Redis 字典使用哈希表作為底層實(shí)現(xiàn),每個(gè)字典包含兩個(gè)哈希表,一個(gè)平時(shí)使用,一個(gè)僅在 rehash 操作中使用。

哈希表總的來(lái)說(shuō),跟 Java HashMap 真的很類似,底層實(shí)現(xiàn)也是一個(gè)數(shù)組加鏈表數(shù)據(jù)結(jié)構(gòu)。

最后,當(dāng)對(duì)哈希表進(jìn)行擴(kuò)容操作時(shí)間,將會(huì)采用漸進(jìn)性 rehash 操作,慢慢將所有鍵值對(duì)遷移到新哈希表中。

其實(shí)了解 Redis 字典的其中的原理,再去比較 Java HashMap ,其實(shí)可以發(fā)現(xiàn)這兩者有如此多的相似點(diǎn)。

所以學(xué)習(xí)這類知識(shí)時(shí),不要僅僅去背,我們要了解其底層原理,知其然知其所以然。

以上就是W3Cschool編程獅關(guān)于阿里面試官:HashMap 熟悉吧?好的,那就來(lái)聊聊 Redis 字典吧!的相關(guān)介紹了,希望對(duì)大家有所幫助。

0 人點(diǎn)贊