面試官：HaspMap很熟了么，講講Redis字典吧！
哈嘍，大家好，我是了不起。
之前給大家介紹了Redis的基本數(shù)據(jù)結(jié)構(gòu)，
后來(lái)聽說(shuō)了一個(gè)故事：
一個(gè)Java程序員去面試，前面面試問了幾個(gè) Java 的相關(guān)問題，回答還不錯(cuò)，接下來(lái)面試官就問了一句：看來(lái) Java 基礎(chǔ)還不錯(cuò)，Java HashMap 你熟悉吧？
回答：那家伙老熟了，工作經(jīng)常用，有看過(guò)源碼。紅黑樹鏈表都能給你整明白了！（心里默念：隨便問吧，八股文和源碼早都爛熟于心）
接著面試官說(shuō)了這么一段話：
那好的，我們來(lái)聊聊 Redis 字典吧。
------------------------------------------
借著這個(gè)故事，我們聊一下Redis 字典，并對(duì)比Java中HashMap的一些異同。
1.前言
我們回顧一下之前講到的Redis的字典結(jié)構(gòu)，示意圖如下：
圖片
Redis的字典本質(zhì)上來(lái)說(shuō)也是數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，這與Java中HashMap的數(shù)據(jù)結(jié)構(gòu)很類似。
由上述結(jié)構(gòu)示意圖也能看出，字典dict中維護(hù)了一個(gè)ht數(shù)組，而且只有兩個(gè)元素，這兩個(gè)元素是其擴(kuò)容的關(guān)鍵點(diǎn)，這個(gè)我們后面會(huì)講到。
Redis中的哈希對(duì)象在以下條件時(shí)，使用ziplist編碼，
- 哈希對(duì)象保存的所有鍵值的字符串長(zhǎng)度都小于64字節(jié)
- 哈希對(duì)象保存的鍵值對(duì)數(shù)量小于512個(gè)。
否則哈希對(duì)象會(huì)使用hashtable編碼， 而hashtable則時(shí)使用了字典作為底層實(shí)現(xiàn)的。
如下redis 哈希對(duì)象編碼由ziplist 變成hashtable
圖片
2.增加元素與鍵沖突
當(dāng)不同的鍵值經(jīng)過(guò)哈希算法與散列算法之后被分配到了同一個(gè)哈希表數(shù)組的同一個(gè)索引上，那么這之后就會(huì)有鍵沖突。
Redis 哈希表解決哈希沖突同樣是使用了鏈表地址法。使用哈希節(jié)點(diǎn)的next指針來(lái)鏈接同一個(gè)哈希表數(shù)組索引上的元素。不過(guò)Redis會(huì)將新添加的哈希節(jié)點(diǎn)加入到鏈表的表頭位置。
如下所示：如果程序要將鍵值對(duì) （k2 , v2 ） 添加到如下的哈希表中，而且計(jì)算的書的索引為1，那么和 （k1 v1） 將產(chǎn)生沖突。解決沖突時(shí)，會(huì)將兩個(gè)節(jié)點(diǎn)使用next指針鏈接起來(lái)。而且會(huì)將新節(jié)點(diǎn)添加到鏈表表頭的位置。
圖片
哈希表1
圖片
鏈表解決hash沖突之后的哈希表
3.rehash 擴(kuò)容過(guò)程
哈希表不斷的增加元素，其元素?cái)?shù)量達(dá)到一定的比例之后，程序會(huì)對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)展。通過(guò)執(zhí)行rehash （重新散列）操作完成操作。其步驟如下：
- 執(zhí)行擴(kuò)展操作時(shí)會(huì)將字典中的ht[1] 哈希表大小設(shè)置成 第一個(gè)大于等于 ht[0] 的 ht[0].used * 2 的 2^n (2的n次冪)
- 將保存早ht[0] 中的所有的鍵值對(duì) rehash到ht[1] 上， rehash過(guò)程中會(huì)重新計(jì)算哈希值和索引值。
- 當(dāng)ht[0]中所有的鍵值對(duì)都遷移到ht[1]上時(shí)，釋放ht[0], 并將ht[1] 設(shè)置成 ht[0]， 并在ht[1]上建一個(gè)空的哈希表。
將下圖中的字典做rehash操作：
圖片
- ht[0].used 是4，4*2 = 8 ，2的3次方8 是第一個(gè)大于4 的 2的n次冪。即程序會(huì)將ht[1] 的大小設(shè)置成8 ，并分配空間，結(jié)構(gòu)示意如下：
圖片
- 將ht[0] 上的幾個(gè)鍵值對(duì)全部都rehash到ht[1] 上面，如下圖：
圖片
- 釋放ht[0]，并將ht[1] 設(shè)置成 ht[0] , 然后為ht[1]分配一個(gè)空白的哈希表 如下圖：
圖片
以上是一個(gè)rehash的過(guò)程示意。
4.漸進(jìn)式rehash
上面講的是一個(gè)rehash的理論過(guò)程，redis實(shí)際操作時(shí)并不會(huì)一次將所有的遷移一次性完成。
如果鍵值對(duì)數(shù)量非常龐大，那么遷移過(guò)程必然需要花費(fèi)一點(diǎn)時(shí)間。由此可知，服務(wù)器也不可能一次將所有的鍵值對(duì)遷移，需要分多次，逐漸將ht[0] 里面的鍵值對(duì)遷移到ht[1]中，
其步驟如下：
- 首先會(huì)給ht[1]分配內(nèi)存空間，此時(shí)redis字典擁有兩個(gè)哈希表
- 字典中維護(hù)一個(gè)rehashidx的計(jì)數(shù)器，將其值設(shè)置為0，表示rehash工作開始
- 在rehash期間，程序依然可以進(jìn)行增刪改查的操作，除此之外還會(huì)順帶將ht[0]上 rehashidx索引上所有的鍵值對(duì)rehash到ht[1]上，rehash的工作完成后會(huì)將rehashidx的值加1
- 隨著字典的操作，ht[0]上的所有鍵值全部都rehash到ht[1]上時(shí)，程序會(huì)將rehashidx的值設(shè)為-1 ，表示rehash操作已經(jīng)完成
在漸進(jìn)式rehash的過(guò)程中，redis字典依然是可以進(jìn)行增刪改查的操作， 其中增加元素的時(shí)候會(huì)將元素直接保存到ht[1]中， 而刪除，查找，更新的操作會(huì)在兩個(gè)哈希表中進(jìn)行， 查找時(shí)會(huì)先在ht[0]中進(jìn)行查找，然后會(huì)在ht[1]中進(jìn)行查找。以上措施可以保證ht[0]中的元素只會(huì)減少，最終變成空表。
總結(jié)
Redis字典和Java中的HashMap的相似點(diǎn)和不同。
相似之處：
- 鍵值對(duì)存儲(chǔ)：Redis 字典和 Java 的 HashMap 都是鍵值對(duì)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，它們可以通過(guò)鍵來(lái)快速查找對(duì)應(yīng)的值。
- 高效的查找：Redis 字典和 Java 的 HashMap 都使用了哈希表來(lái)實(shí)現(xiàn)，因此在查找操作上具有高效性能。
- Redis 字典使用的時(shí)哈希表作為底層，并且每個(gè)字典維護(hù)了兩個(gè)哈希表，ht[0] 時(shí)主要使用的哈希表，而ht[1] 是在rehash過(guò)程是才會(huì)使用到的表。
- 哈希表的底層同樣是使用了數(shù)組 + 鏈表的結(jié)構(gòu)， 與Java 中HashMap 相似，只不過(guò)Java8 以后增加了紅黑樹，在特定情況下會(huì)替換鏈表。
不同之處：
- 哈希表增加元素遇到哈希沖突是會(huì)將新添加的元素放到鏈表頭，而Java HashMap會(huì)將其放到鏈表尾，
- 擴(kuò)容過(guò)程中redis的字典是漸進(jìn)式擴(kuò)容，擴(kuò)容期間還是可以進(jìn)行操作的，而Java的HashMap擴(kuò)容需要一次性完成。
- 存儲(chǔ)方式：Redis 字典是一種基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，用于在內(nèi)存中存儲(chǔ)鍵值對(duì)。而 Java 的 HashMap 可以在內(nèi)存中存儲(chǔ)，也可以持久化到磁盤上。
- 分布式支持：Redis 是一種分布式數(shù)據(jù)庫(kù)，可以在多臺(tái)服務(wù)器上進(jìn)行數(shù)據(jù)共享和存儲(chǔ)。而 Java 的 HashMap 只能在單個(gè) JVM 中使用。
- 數(shù)據(jù)類型：Redis 字典可以存儲(chǔ)多種數(shù)據(jù)類型，如字符串、列表、集合等，而 Java 的 HashMap 只能存儲(chǔ)對(duì)象類型。
- 持久化：Redis 字典可以將數(shù)據(jù)持久化到磁盤上，以便在重啟后恢復(fù)數(shù)據(jù)。而 Java 的 HashMap 需要自己實(shí)現(xiàn)數(shù)據(jù)的序列化和反序列化來(lái)實(shí)現(xiàn)持久化。
- 并發(fā)性：Redis 字典是線程安全的，可以支持多個(gè)客戶端并發(fā)訪問。而 Java 的 HashMap 在多線程環(huán)境下需要進(jìn)行額外的同步處理才能保證線程安全。
