架構(gòu)

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

之前給大家介紹了Redis的基本數(shù)據(jù)結(jié)構(gòu)，本篇介紹一下Redis 字典的rehash 過(guò)程。并對(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)很類(lèi)似啦。

由上述結(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ì)算的書(shū)的索引為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操作：

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

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

3. 釋放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工作開(kāi)始。
• 在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ì)現(xiàn)在ht[0]中進(jìn)行查找，然后會(huì)在ht[1]中進(jìn)行查找。以上措施可以寶成ht[0]中的元素只會(huì)減少，最終變成空表。

總結(jié)

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