Redis一共支持5種資料結構，hash是其中的一種，在hash擴容的時候采用的是漸進式rehash的方式，要想深入理解漸進式rehash，首先要了解以下Redis中hash的資料結構，
哈希表節點
typedef struct dictEntry {
void *key; // 鍵
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v; // 值
struct dictEntry *next; // 下一個節點
} dictEntry;
哈希表
/* This is our hash table structure. Every dictionary has two of this as we
* implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
dictEntry **table; // 哈希表陣列
unsigned long size; // 哈希表大小
unsigned long sizemask; // 掩碼，計算索引值，size-1
unsigned long used; // 哈希表已有節點的數量
} dictht;
字典
typedef struct dict {
dictType *type; // 型別特定函式
void *privdata; // 私有資料
dictht ht[2]; // 哈希表
// rehash索引
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
特定函式
typedef struct dictType {
// 計算哈希值的函式
uint64_t (*hashFunction)(const void *key);
// 復制鍵的函式
void *(*keyDup)(void *privdata, const void *key);
// 復制值的函式
void *(*valDup)(void *privdata, const void *obj);
// 對比鍵的函式
int (*keyCompare)(void *privdata, const void *key1, const void *key2);
// 銷毀鍵的函式
void (*keyDestructor)(void *privdata, void *key);
// 銷毀值的函式
void (*valDestructor)(void *privdata, void *obj);
} dictType;
字典中包含一個資料結構dictht的ht陣列，一般情況下字典只是用ht[0]用來存盤資料，ht[1]在rehash時使用，
哈希演算法原理
當向字典中添加一個元素時（假設此時 rehashidx = -1，也就是沒有進行rehash），首先通過dict->type->hashFunction計算該元素的hash值，然后通過hash & dict->ht[x].sizemask計算哈希地址index，如果該元素對應的下標沒有資料，則直接添加，否則采用鏈地址法添加到hash對應index元素的鏈表尾部，
rehash原理
隨著操作的不斷執行，哈希表中的元素會逐漸增加或者減少，為了讓哈希表的負載因子維持在一個合理的范圍內，程式需要對哈希表的大小進行相應的擴容和收縮，步驟如下：
-
為
ht[1]哈希表分配空間，如果是擴容操作，ht[1]的大小為第一個大于等于ht[0].used*2的2的n次方冪，如果是收縮操作，ht[1]的大小為第一個大于等于ht[0].used的2的n次方冪 -
將保存在
ht[0]中的所有鍵值對rehash到ht[1]：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放到ht[1]對應位置上 -
當
ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]，將ht[1]設定為ht[0]，并在ht[1]新創建一個空白哈希表，為下一次rehash做準備
漸進式rehash原理
在擴容和收縮的時候，如果哈希字典中有很多元素，一次性將這些鍵全部rehash到ht[1]的話，可能會導致服務器在一段時間內停止服務，所以，采用漸進式rehash的方式，詳細步驟如下：
-
為
ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表 -
將
rehashindex的值設定為0，表示rehash作業正式開始 -
在rehash期間，每次對字典執行增刪改查操作是，程式除了執行指定的操作以外，還會順帶將
ht[0]哈希表在rehashindex索引上的所有鍵值對rehash到ht[1]，當rehash作業完成以后，rehashindex的值+1 -
隨著字典操作的不斷執行，最侄訓在某一時間段上
ht[0]的所有鍵值對都會被rehash到ht[1]，這時將rehashindex的值設定為-1，表示rehash操作結束
漸進式rehash采用的是一種分而治之的方式，將rehash的操作分攤在每一個的訪問中，避免集中式rehash而帶來的龐大計算量，
需要注意的是在漸進式rehash的程序，如果有增刪改查操作時，如果index大于rehashindex，訪問ht[0]，否則訪問ht[1]
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/145066.html
標籤：Java