架構

哈嘍，大家好，我是指北君。

之前給大家介紹了Redis的基本數據結構，本篇介紹一下Redis 字典的rehash 過程。并對比Java中HashMap的一些異同。

1.前言

我們回顧一下之前講到的Redis的字典結構，示意圖如下：

Redis的字典本質上來說也是數組+鏈表的數據結構，這與Java中HashMap的數據結構很類似啦。

由上述結構示意圖也能看出，字典dict中維護了一個ht數組，而且只有兩個元素，這兩個元素是其擴容的關鍵點，這個我們后面會講到。

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

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

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

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

2.增加元素與鍵沖突

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

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

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

哈希表1

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

3.rehash 擴容過程

哈希表不斷的增加元素，其元素數量達到一定的比例之后，程序會對哈希表進行相應的擴展。通過執行rehash （重新散列）操作完成操作。其步驟如下：

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

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

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

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

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

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

4.漸進式rehash

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

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

其步驟如下：

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

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

總結

• Redis 字典使用的時哈希表作為底層，并且每個字典維護了兩個哈希表，ht[0] 時主要使用的哈希表，而ht[1] 是在rehash過程是才會使用到的表。
• 哈希表的底層同樣是使用了數組 + 鏈表的結構， 與Java 中HashMap 相似，只不過Java8 以后增加了紅黑樹，在特定情況下會替換鏈表。
• 哈希表增加元素遇到哈希沖突是會將新添加的元素放到鏈表頭，而Java HashMap會將其放到鏈表尾，
• 擴容過程中redis的字典是漸進式擴容，擴容期間還是可以進行操作的，而Java的HashMap擴容需要一次性完成。