hash位址_redis中的hash擴容、漸進式rehash過程

背景： redis字典（hash表）當資料越來越多的時候，就會發生擴容，也就是rehash 對比：java中的hashmap，當資料數量達到門檻值的時候(0.75)，就會發生rehash，hash表長度變為原來的二倍，将原hash表資料全部重新計算hash位址，重新配置設定位置，達到rehash目的

redis中的hash表采用的是漸進式hash的方式：

1、redis字典（hash表）底層有兩個數組，還有一個rehashidx用來控制rehash

2、初始預設hash長度為4，當元素個數與hash表長度一緻時，就發生擴容，hash長度變為原來的二倍

3、redis中的hash則是執行的單步rehash的過程：

每次的增删改查，rehashidx+1，然後執行對應原hash表rehashidx索引位置的rehash

總結：

在擴容和收縮的時候，如果哈希字典中有很多元素，一次性将這些鍵全部rehash到

ht[1]

的話，可能會導緻伺服器在一段時間内停止服務。是以，采用漸進式rehash的方式，詳細步驟如下：

1. 為

   ht[1]

   配置設定空間，讓字典同時持有

   ht[0]

   和

   ht[1]

   兩個哈希表
2. 将

   rehashindex

   的值設定為 ，表示rehash工作正式開始
3. 在rehash期間，每次對字典執行增删改查操作是，程式除了執行指定的操作以外，還會順帶将

   ht[0]

   哈希表在

   rehashindex

   索引上的所有鍵值對rehash到

   ht[1]

   ，當rehash工作完成以後，

   rehashindex

   的值

   +1

4. 随着字典操作的不斷執行，最終會在某一時間段上

   ht[0]

   的所有鍵值對都會被rehash到

   ht[1]

   ，這時将

   rehashindex

   的值設定為

   -1

   ，表示rehash操作結束

漸進式rehash采用的是一種分而治之的方式，将rehash的操作分攤在每一個的通路中，避免集中式rehash而帶來的龐大計算量。 需要注意的是在漸進式rehash的過程，如果有增删改查操作時，如果

index

大于

rehashindex

，通路

ht[0]

，否則通路

ht[1]。