字典，又稱符號表，是保存鍵值對的抽象數(shù)據(jù)結(jié)構(gòu)。很多語言都內(nèi)置字典這種常用的數(shù)據(jù)結(jié)構(gòu)，但是C語言沒有內(nèi)置，所以redis自己來實(shí)現(xiàn)了字典。
redis中的字典由dict.h/dict結(jié)構(gòu)來定義：
typedef struct dict {
dictType *type; //類型特定函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //哈希表
int rehashdx; //rehash 索引,當(dāng) rehash 不在進(jìn)行時(shí),值為-1
} dict;
type和privdata是針對不同類型的鍵值對，為創(chuàng)建多態(tài)字典而設(shè)置的
type是指向dictType結(jié)構(gòu)的指針，每個(gè)dictType結(jié)構(gòu)保存了一簇操作特定類型鍵值對的函數(shù)，redis會(huì)為用途不同的字典設(shè)置不同的特定處理函數(shù)。
privdata則保存了傳給那些特定處理函數(shù)的可選參數(shù)的信息。ht屬性包含兩個(gè)數(shù)組，這兩個(gè)數(shù)組都是一個(gè)dictht哈希表，一般情況下字典只使用ht[0]這個(gè)哈希表，ht[1]只會(huì)在對哈希表進(jìn)行rehash時(shí)才會(huì)使用。
rehashdx記錄了rehash當(dāng)前的進(jìn)度，如果沒有進(jìn)行rehash，則 rehashdx值為-1
可以看到，字典dict結(jié)構(gòu)中，最重要的就是dictht 這種類型的ht哈希表(平時(shí)都是ht[0]在起作用)，哈希表的數(shù)據(jù)結(jié)構(gòu)dictht定義為：
typedef struct dictht {
dictEntry **table; //哈希表數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //用于計(jì)算索引值,
//總是等于 size - 1
unsigned long used; //哈希表已有節(jié)點(diǎn)數(shù)量
} dictht;
- table屬性是一個(gè)數(shù)組，數(shù)組中每個(gè)元素都是指向一個(gè)dictEntry結(jié)構(gòu)的指針，每個(gè)dictEntry結(jié)構(gòu)保存著一個(gè)鍵值對。
- size屬性記錄了hash表的大小，也就是table這個(gè)數(shù)組的大小。
- sizemask屬性和哈希值共同決定了一個(gè)鍵應(yīng)該被放到數(shù)組的哪個(gè)索引上。
可以看到，哈希表結(jié)構(gòu)dictht中，最重要的就是table中元素指向的哈希表節(jié)點(diǎn)dictEntry這種鍵值對結(jié)構(gòu)，hash表節(jié)點(diǎn)dictEntry的結(jié)構(gòu)定義為：
typedef struct dictEntry {
void *key; //鍵
union { //值
void *val;
uint_64 u64;
int64_t s64;
} v;
sturct dictEntry *next; //指向下個(gè)哈希表節(jié)點(diǎn),形成鏈表
} dictEntry;
- v屬性保存著鍵值對的值，其中的鍵值可以是指針，或者是uint_64 類型，也可能是int64_t 類型。
- next屬性是指向另一個(gè)哈希表節(jié)點(diǎn)的指針，這個(gè)指針把多個(gè)哈希值相同的節(jié)點(diǎn)連接在一起，來解決hash碰撞問題。
下圖是普通狀態(tài)(不是在rehash狀態(tài))下的字典：
在這個(gè)字典中，ht[0]這個(gè)hashtable中，table數(shù)組中有4個(gè)哈希節(jié)點(diǎn)(ditcEntry)，其中哈希值為0和3的節(jié)點(diǎn)無鍵值對，哈希值為1的節(jié)點(diǎn)有兩個(gè)鍵值對，用next指針相連，哈希值為2的節(jié)點(diǎn)有一個(gè)鍵值對。
還可以看到，字典在普通狀態(tài)下，ht[1]這個(gè)hashtable里面，table這個(gè)數(shù)組沒有元素，為空。
哈希算法
當(dāng)要將一個(gè)新的鍵值對添加到字典里面時(shí)，程序會(huì)根據(jù)鍵計(jì)算出哈希值和索引值，然后再根據(jù)索引值將新鍵值對放到哈希表數(shù)組指定的索引上。
解決鍵沖突
可能存在這樣一種情況：兩個(gè)不同的鍵值對，計(jì)算出的哈希值和索引值是一樣的。這就叫hash碰撞。怎么解決hash碰撞的問題呢？？我們想到了每個(gè)hash節(jié)點(diǎn)都有一個(gè)next指針，借助于這個(gè)next指針，我們可以將哈希值一樣的節(jié)點(diǎn)串起來，形成一個(gè)單鏈表。
rehash
隨著鍵值對的逐漸增多或減少，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍之內(nèi)，當(dāng)哈希表保存的鍵值對太多或者太少時(shí)，程序需要對哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮，這個(gè)過程叫做rehash。
Redis 對字典的哈希表執(zhí)行 rehash 的步驟如下:
- 為字典的 ht[1] 哈希表分配空間,空間的大小取決于要執(zhí)行的操作,以及ht[0]當(dāng)前包含的鍵值對數(shù)量( used 屬性值):
如果執(zhí)行的是擴(kuò)展操作,那么 ht[1] 的大小為第一個(gè)大于等于ht[0].used*2的 $2^n$ .
如果執(zhí)行的是收縮操作,那么ht[1]的大小為打一個(gè)大于等于ht[0].used 的$2^n$. - 將保存在 ht[0] 中所有鍵值對 rehash 到 ht[1] 上面: 任何事指的是重新計(jì)算鍵的哈希值和索引值,然后將鍵值對放到 ht[1] 哈希表的指定位置.
- 當(dāng) ht[0] 包含的所有鍵值對都遷移到了ht[1]之后, 釋放 ht[0], 再將 ht[1] 設(shè)置為 ht[0],并在 ht[1] 后面創(chuàng)建一個(gè)空白的哈希表.
舉個(gè)例子,假設(shè)程序要對下圖的 `ht[0] 進(jìn)行擴(kuò)展操作
ht[0].used 當(dāng)前值為4 , $2^3$ 恰好是第一個(gè)大于等于 4*2 的值,所以 ht1 哈希表的大小設(shè)置為8,下圖展示了 ht1 分配了空間之后字典的樣子.
將 ht[0] 包含的四個(gè)鍵值對 rehash 到 ht1, 圖下圖所示:
釋放 ht[0], 將 ht1 設(shè)置為 ht[0]. 再分配一個(gè)空哈希表. 哈希表的大小由原來的4 擴(kuò)展至8.
漸進(jìn)式rehash
拓展或者收縮哈希表需要將ht[0]里所有的鍵值對重新hash到ht[1]中，但是這個(gè)rehash動(dòng)作并不是一次性集中式完成的。而是分多次漸進(jìn)式完成的。原因也很清楚，就是鍵值對過多時(shí)，一次性rehash肯定會(huì)消耗服務(wù)器大量的計(jì)算資源，可能會(huì)對服務(wù)器的性能造成影響。
以下是漸進(jìn)式rehash的步驟：
- 為ht[1]分配空間
- 在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx，將它的值設(shè)置為0，表示rehash正式開始。
- 在rehash進(jìn)行期間，每次對字典進(jìn)行增刪改查時(shí)，順帶將ht[0]在rehashidx索引上的所有鍵值對rehash到ht[1]中，同時(shí)將rehashidx增加1
- 隨著rehash的不斷進(jìn)行，最終在某個(gè)時(shí)間點(diǎn)上，ht[0]上的所有鍵值對都rehash到ht[1]上了，這時(shí)將rehashidx屬性置為-1，表示rehash操作完成。
