文章轉(zhuǎn)載自公眾號:Java極客技術 作者:鴨血粉絲
最近,阿粉的一個朋友出去面試,回來跟阿粉抱怨,面試官不按套路出牌,直接打亂了他的節(jié)奏。
事情是這樣的,前面面試問了幾個 Java 的相關問題,我朋友回答還不錯,接下來面試官就問了一句:看來 Java 基礎還不錯,Java HashMap
你熟悉吧?
我朋友回答。工作經(jīng)常用,有看過源碼。
我朋友本來想著,你隨便來吧,這個問題之前已經(jīng)準備好了,隨便問吧。
誰知道,面試官下面一句:
「那好的,我們來聊聊 Redis 字典吧?!?/strong>
直接將他整蒙逼。
阿粉的朋友由于沒怎么研究過 Redis 字典,所以這題就直接回答不知道了。
「當然,如果面試中真不知道,那就回答不了解,直接下一題,不要亂答。」
不過這一題,阿粉覺得還是很可惜,其實 Redis 字典基本原理與 HashMap
差不多,那我們其實可以套用這其中的原理,不求回答滿分,但是怎么也可以得個及格分吧~
面試過程真要碰到這個問題,我們可以從下面三個方面回答。
- 數(shù)據(jù)結(jié)構
- 元素增加過程
- 擴容
字典數(shù)據(jù)結(jié)構
說起字典,也許大家比較陌生,但是我們都知道 Redis 本身提供 KV
查詢的方式,這個 KV
就是其實通過底層就是通過字典保存。
另外,Redis 支持多種數(shù)據(jù)類型,其中一種類型為 Hash
鍵,也可以用來存儲 KV
數(shù)據(jù)。
阿粉剛開始了解的這個數(shù)據(jù)結(jié)構的時候,本來以為這個就是使用字典實現(xiàn)。其實并不是這樣的,初始創(chuàng)建 Has
h 鍵,默認使用另外一種數(shù)據(jù)結(jié)構-「ZIPLIST」(壓縮列表),以此節(jié)省內(nèi)存空間。
不過一旦以下任何條件被滿足,Hash
鍵的數(shù)據(jù)結(jié)構將會變?yōu)樽值洌涌觳樵兯俣取?/p>
- 哈希表中某個鍵或某個值的長度大于
server.hash_max_ziplist_value
(默認值為64
)。 - 壓縮列表中的節(jié)點數(shù)量大于
server.hash_max_ziplist_entries
(默認值為512
)。
Redis 字典新建時默認將會創(chuàng)建一個哈希表數(shù)組,保存兩個哈希表。
其中 ht[0]
哈希表在第一次往字典中添加鍵值時分配內(nèi)存空間,而另一個 ht[1]
將會在下文中擴容/縮容才會進行空間分配。
字典中哈希表其實就等同于Java HashMap
,我們知道 Java 采用數(shù)組加鏈表/紅黑樹的實現(xiàn)方式,其實哈希表也是使用類似的數(shù)據(jù)結(jié)構。
哈希表結(jié)構如下所示:
其中 table
屬性是個數(shù)組, 其中數(shù)組元素保存一種 dictEntry
的結(jié)構,這個結(jié)構完全類似與 HashMap
中的 Entry
類型,這個結(jié)構存儲一個 KV 鍵值對。
同時,為了解決 hash 碰撞的問題,dictEntry
存在一個 next 指針,指向下一個dictEntry
,這樣就形成 dictEntry
的鏈表。
現(xiàn)在,我們回頭對比 Java 中 HashMap
,可以發(fā)現(xiàn)兩者數(shù)據(jù)結(jié)構基本一致。
只不過 HashMap
為了解決鏈表過長問題導致查詢變慢,JDK1.8 時在鏈表元素過多時采用紅黑樹的數(shù)據(jù)結(jié)構。
下面我們開始添加新元素,了解這其中的原理。
元素增加過程
當我們往一個新字典中添加元素,默認將會為字典中 ht[0]
哈希表分配空間,默認情況下哈希表 table 數(shù)組大小為 4(「DICT_HT_INITIAL_SIZE」)。
新添加元素的鍵值將會經(jīng)過哈希算法,確定哈希表數(shù)組的位置,然后添加到相應的位置,如圖所示:
繼續(xù)增加元素,此時如果兩個不同鍵經(jīng)過哈希算法產(chǎn)生相同的哈希值,這樣就發(fā)生了哈希碰撞。
假設現(xiàn)在我們哈希表中擁有是三個元素,:
我們再增加一個新元素,如果此時剛好在數(shù)組 3 號位置上發(fā)生碰撞,此時 Redis 將會采用鏈表的方式解決哈希碰撞。
「注意,新元素將會放在鏈表頭結(jié)點,這么做目的是因為新增加的元素,很大概率上會被再次訪問,放在頭結(jié)點增加訪問速度。」
這里我們在對比一下元素添加過程,可以發(fā)現(xiàn) Redis 流程其實與 JDK 1.7
版本的 HashMap
類似。
當我們元素增加越來越多時,哈希碰撞情況將會越來越頻繁,這就會導致鏈表長度過長,極端情況下 O(1) 查詢效率退化成 O(N) 的查詢效率。
為此,字典必須進行擴容,這樣就會使觸發(fā)字典 rehash
操作。
擴容
當 Redis 進行 Rehash 擴容操作,首先將會為字典沒有用到 ht[1]
哈希表分配更大空間。
?
畫外音:ht[1]
哈希表大小為第一個大于等于ht[0].used*2
的 2^2(2的n 次方冪)
?
然后再將 ht[0]
中所有鍵值對都遷移到 ht[1]
中。
簡單起見,忽略指向空節(jié)點
當節(jié)點全部遷移完畢,將會釋放 ht[0]
占用空間,并將 ht[1]
設置為 ht[0]
。
擴容 操作需要將 ht[0]
所有鍵值對都 Rehash
到 ht[1]
中,如果鍵值過多,假設存在十億個鍵值對,這樣一次性的遷移,勢必導致服務器會在一段時間內(nèi)停止服務。
另外如果每次 rehash
都會阻塞當前操作,這樣對于客戶端處理非常不友好。
為了避免 rehash
對服務器的影響,Redis 采用漸進式的遷移方式,慢慢將數(shù)據(jù)遷移分散到多個操作步驟。
這個操作依賴字典中一個屬性 rehashidx
,這是一個索引位置計數(shù)器,記錄下一個哈希表 table 數(shù)組上元素,默認情況為值為 「-1」。
假設此時擴容前字典如圖所示:
當開始 rehash 操作,rehashidx
將會被設置為 「0」 。
這個期間每次收到增加,刪除,查找,更新命令,除了這些命令將會被執(zhí)行以外,還會順帶將 ht[0]
哈希表在 rehashidx
位置的元素 rehash 到 ht[1]
中。
假設此時收到一個 「K3」 鍵的查詢操作,Redis 首先執(zhí)行查詢操作,接著 Redis 將會為 ht[0]
哈希表上table
數(shù)組第 rehashidx
索引上所有節(jié)點都遷移到 ht[1]
中。
當操作完成之后,再將 rehashidx
屬性值加 1。
最后當所有鍵值對都 rehash
到 ht[1]
中時,rehashidx
將會被重新設置為 -1。
雖然漸進式的 rehash 操作減少了工作量,但是卻帶來鍵值操作的復雜度。
這是因為在漸進式 rehash
操作期間,Redis 無法明確知道鍵到底在ht[0]
中,還是在 ht[1]
中,所以這個時候 Redis 不得不查找兩個哈希表。
以查找為例,Redis 首先查詢 ht[0]
,如果沒找到將會繼續(xù)查找 ht[1]
,除了查詢以外,更新,刪除也會執(zhí)行如上的操作。
添加操作其實就沒這么麻煩,因為ht[0]
不會在使用,那就統(tǒng)一都添加到 ht[1]
中就好了。
最后我們再對比一下 Java HashMap 擴容操作,它是一個一次性操作,每次擴容需要將所有鍵值對都遷移到新的數(shù)組中,所以如果數(shù)據(jù)量很大,消耗時間就會久。
總結(jié)
Redis 字典使用哈希表作為底層實現(xiàn),每個字典包含兩個哈希表,一個平時使用,一個僅在 rehash
操作中使用。
哈希表總的來說,跟 Java HashMap
真的很類似,底層實現(xiàn)也是一個數(shù)組加鏈表數(shù)據(jù)結(jié)構。
最后,當對哈希表進行擴容操作時間,將會采用漸進性 rehash
操作,慢慢將所有鍵值對遷移到新哈希表中。
其實了解 Redis 字典的其中的原理,再去比較 Java HashMap
,其實可以發(fā)現(xiàn)這兩者有如此多的相似點。
所以學習這類知識時,不要僅僅去背,我們要了解其底層原理,知其然知其所以然。
以上就是W3Cschool編程獅
關于阿里面試官:HashMap 熟悉吧?好的,那就來聊聊 Redis 字典吧!的相關介紹了,希望對大家有所幫助。