1.前言

我們回顧一下之前講到的Redis的字典結(jié)構(gòu)，示意圖如下：

Redis的字典本質(zhì)上來說也是數(shù)組+鏈表的數(shù)據(jù)結(jié)構(gòu)，這與Java中HashMap的數(shù)據(jù)結(jié)構(gòu)很類似。

由上述結(jié)構(gòu)示意圖也能看出，字典dict中維護(hù)了一個ht數(shù)組，而且只有兩個元素，這兩個元素是其擴(kuò)容的關(guān)鍵點，這個我們后面會講到。

Redis中的哈希對象在以下條件時，使用ziplist編碼，

• 哈希對象保存的所有鍵值的字符串長度都小于64字節(jié)
• 哈希對象保存的鍵值對數(shù)量小于512個。

否則哈希對象會使用hashtable編碼， 而hashtable則時使用了字典作為底層實現(xiàn)的。

如下redis 哈希對象編碼由ziplist 變成hashtable

2.增加元素與鍵沖突

當(dāng)不同的鍵值經(jīng)過哈希算法與散列算法之后被分配到了同一個哈希表數(shù)組的同一個索引上，那么這之后就會有鍵沖突。

Redis 哈希表解決哈希沖突同樣是使用了鏈表地址法。使用哈希節(jié)點的next指針來鏈接同一個哈希表數(shù)組索引上的元素。不過Redis會將新添加的哈希節(jié)點加入到鏈表的表頭位置。

如下所示：如果程序要將鍵值對 （k2 , v2 ） 添加到如下的哈希表中，而且計算的書的索引為1，那么和 （k1 v1） 將產(chǎn)生沖突。解決沖突時，會將兩個節(jié)點使用next指針鏈接起來。而且會將新節(jié)點添加到鏈表表頭的位置。

哈希表1

鏈表解決hash沖突之后的哈希表

3.rehash 擴(kuò)容過程

哈希表不斷的增加元素，其元素數(shù)量達(dá)到一定的比例之后，程序會對哈希表進(jìn)行相應(yīng)的擴(kuò)展。通過執(zhí)行rehash （重新散列）操作完成操作。其步驟如下：

• 執(zhí)行擴(kuò)展操作時會將字典中的ht[1] 哈希表大小設(shè)置成 第一個大于等于 ht[0] 的 ht[0].used * 2 的 2^n (2的n次冪)
• 將保存早ht[0] 中的所有的鍵值對 rehash到ht[1] 上， rehash過程中會重新計算哈希值和索引值。
• 當(dāng)ht[0]中所有的鍵值對都遷移到ht[1]上時，釋放ht[0], 并將ht[1] 設(shè)置成 ht[0]， 并在ht[1]上建一個空的哈希表。

將下圖中的字典做rehash操作：

1. ht[0].used 是4，4*2 = 8 ，2的3次方8 是第一個大于4 的 2的n次冪。即程序會將ht[1] 的大小設(shè)置成8 ，并分配空間，結(jié)構(gòu)示意如下：

2. 將ht[0] 上的幾個鍵值對全部都rehash到ht[1] 上面，如下圖：

3. 釋放ht[0]，并將ht[1] 設(shè)置成 ht[0] , 然后為ht[1]分配一個空白的哈希表 如下圖：

以上是一個rehash的過程示意。

4.漸進(jìn)式rehash

上面講的是一個rehash的理論過程，redis實際操作時并不會一次將所有的遷移一次性完成。

如果鍵值對數(shù)量非常龐大，那么遷移過程必然需要花費一點時間。由此可知，服務(wù)器也不可能一次將所有的鍵值對遷移，需要分多次，逐漸將ht[0] 里面的鍵值對遷移到ht[1]中，

其步驟如下：

• 首先會給ht[1]分配內(nèi)存空間，此時redis字典擁有兩個哈希表
• 字典中維護(hù)一個rehashidx的計數(shù)器，將其值設(shè)置為0，表示rehash工作開始
• 在rehash期間，程序依然可以進(jìn)行增刪改查的操作，除此之外還會順帶將ht[0]上 rehashidx索引上所有的鍵值對rehash到ht[1]上，rehash的工作完成后會將rehashidx的值加1
• 隨著字典的操作，ht[0]上的所有鍵值全部都rehash到ht[1]上時，程序會將rehashidx的值設(shè)為-1 ，表示rehash操作已經(jīng)完成

在漸進(jìn)式rehash的過程中，redis字典依然是可以進(jìn)行增刪改查的操作， 其中增加元素的時候會將元素直接保存到ht[1]中， 而刪除，查找，更新的操作會在兩個哈希表中進(jìn)行， 查找時會先在ht[0]中進(jìn)行查找，然后會在ht[1]中進(jìn)行查找。以上措施可以保證ht[0]中的元素只會減少，最終變成空表。

總結(jié)

Redis字典和Java中的HashMap的相似點和不同。

相似之處：

1. 鍵值對存儲：Redis 字典和 Java 的 HashMap 都是鍵值對存儲的數(shù)據(jù)結(jié)構(gòu)，它們可以通過鍵來快速查找對應(yīng)的值。
2. 高效的查找：Redis 字典和 Java 的 HashMap 都使用了哈希表來實現(xiàn)，因此在查找操作上具有高效性能。
3. Redis 字典使用的時哈希表作為底層，并且每個字典維護(hù)了兩個哈希表，ht[0] 時主要使用的哈希表，而ht[1] 是在rehash過程是才會使用到的表。
4. 哈希表的底層同樣是使用了數(shù)組 + 鏈表的結(jié)構(gòu)， 與Java 中HashMap 相似，只不過Java8 以后增加了紅黑樹，在特定情況下會替換鏈表。

不同之處：

1. 哈希表增加元素遇到哈希沖突是會將新添加的元素放到鏈表頭，而Java HashMap會將其放到鏈表尾，
2. 擴(kuò)容過程中redis的字典是漸進(jìn)式擴(kuò)容，擴(kuò)容期間還是可以進(jìn)行操作的，而Java的HashMap擴(kuò)容需要一次性完成。
3. 存儲方式：Redis 字典是一種基于內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，用于在內(nèi)存中存儲鍵值對。而 Java 的 HashMap 可以在內(nèi)存中存儲，也可以持久化到磁盤上。
4. 分布式支持：Redis 是一種分布式數(shù)據(jù)庫，可以在多臺服務(wù)器上進(jìn)行數(shù)據(jù)共享和存儲。而 Java 的 HashMap 只能在單個 JVM 中使用。
5. 數(shù)據(jù)類型：Redis 字典可以存儲多種數(shù)據(jù)類型，如字符串、列表、集合等，而 Java 的 HashMap 只能存儲對象類型。
6. 持久化：Redis 字典可以將數(shù)據(jù)持久化到磁盤上，以便在重啟后恢復(fù)數(shù)據(jù)。而 Java 的 HashMap 需要自己實現(xiàn)數(shù)據(jù)的序列化和反序列化來實現(xiàn)持久化。
7. 并發(fā)性：Redis 字典是線程安全的，可以支持多個客戶端并發(fā)訪問。而 Java 的 HashMap 在多線程環(huán)境下需要進(jìn)行額外的同步處理才能保證線程安全。