字典怀偷，又稱符號(hào)表宠叼，是保存鍵值對(duì)的抽象數(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是針對(duì)不同類型的鍵值對(duì)缠沈，為創(chuàng)建多態(tài)字典而設(shè)置的
type是指向dictType結(jié)構(gòu)的指針，每個(gè)dictType結(jié)構(gòu)保存了一簇操作特定類型鍵值對(duì)的函數(shù)错蝴，redis會(huì)為用途不同的字典設(shè)置不同的特定處理函數(shù)洲愤。
privdata則保存了傳給那些特定處理函數(shù)的可選參數(shù)的信息。ht屬性包含兩個(gè)數(shù)組顷锰，這兩個(gè)數(shù)組都是一個(gè)dictht哈希表柬赐，一般情況下字典只使用ht[0]這個(gè)哈希表，ht[1]只會(huì)在對(duì)哈希表進(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è)鍵值對(duì)笨枯。
- size屬性記錄了hash表的大小薪丁，也就是table這個(gè)數(shù)組的大小遇西。
- sizemask屬性和哈希值共同決定了一個(gè)鍵應(yīng)該被放到數(shù)組的哪個(gè)索引上。
可以看到严嗜，哈希表結(jié)構(gòu)dictht中粱檀，最重要的就是table中元素指向的哈希表節(jié)點(diǎn)dictEntry這種鍵值對(duì)結(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屬性保存著鍵值對(duì)的值漫玄，其中的鍵值可以是指針茄蚯，或者是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)無鍵值對(duì)癌椿，哈希值為1的節(jié)點(diǎn)有兩個(gè)鍵值對(duì)，用next指針相連菱阵，哈希值為2的節(jié)點(diǎn)有一個(gè)鍵值對(duì)踢俄。
還可以看到，字典在普通狀態(tài)下晴及，ht[1]這個(gè)hashtable里面都办，table這個(gè)數(shù)組沒有元素，為空抗俄。
哈希算法
當(dāng)要將一個(gè)新的鍵值對(duì)添加到字典里面時(shí)脆丁，程序會(huì)根據(jù)鍵計(jì)算出哈希值和索引值，然后再根據(jù)索引值將新鍵值對(duì)放到哈希表數(shù)組指定的索引上动雹。
解決鍵沖突
可能存在這樣一種情況：兩個(gè)不同的鍵值對(duì)槽卫，計(jì)算出的哈希值和索引值是一樣的。這就叫hash碰撞胰蝠。怎么解決hash碰撞的問題呢歼培？？我們想到了每個(gè)hash節(jié)點(diǎn)都有一個(gè)next指針茸塞，借助于這個(gè)next指針躲庄，我們可以將哈希值一樣的節(jié)點(diǎn)串起來，形成一個(gè)單鏈表钾虐。
rehash
隨著鍵值對(duì)的逐漸增多或減少噪窘，為了讓哈希表的負(fù)載因子維持在一個(gè)合理的范圍之內(nèi)，當(dāng)哈希表保存的鍵值對(duì)太多或者太少時(shí)效扫，程序需要對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)展或者收縮倔监，這個(gè)過程叫做rehash直砂。
Redis 對(duì)字典的哈希表執(zhí)行 rehash 的步驟如下:
- 為字典的 ht[1] 哈希表分配空間,空間的大小取決于要執(zhí)行的操作,以及ht[0]當(dāng)前包含的鍵值對(duì)數(shù)量( used 屬性值):
如果執(zhí)行的是擴(kuò)展操作,那么 ht[1] 的大小為第一個(gè)大于等于ht[0].used*2的 $2^n$ .
如果執(zhí)行的是收縮操作,那么ht[1]的大小為打一個(gè)大于等于ht[0].used 的$2^n$. - 將保存在 ht[0] 中所有鍵值對(duì) rehash 到 ht[1] 上面: 任何事指的是重新計(jì)算鍵的哈希值和索引值,然后將鍵值對(duì)放到 ht[1] 哈希表的指定位置.
- 當(dāng) ht[0] 包含的所有鍵值對(duì)都遷移到了ht[1]之后, 釋放 ht[0], 再將 ht[1] 設(shè)置為 ht[0],并在 ht[1] 后面創(chuàng)建一個(gè)空白的哈希表.
舉個(gè)例子,假設(shè)程序要對(duì)下圖的 `ht[0] 進(jìn)行擴(kuò)展操作
ht[0].used 當(dāng)前值為4 , $2^3$ 恰好是第一個(gè)大于等于 4*2 的值,所以 ht1 哈希表的大小設(shè)置為8,下圖展示了 ht1 分配了空間之后字典的樣子.
將 ht[0] 包含的四個(gè)鍵值對(duì) rehash 到 ht1, 圖下圖所示:
釋放 ht[0], 將 ht1 設(shè)置為 ht[0]. 再分配一個(gè)空哈希表. 哈希表的大小由原來的4 擴(kuò)展至8.
漸進(jìn)式rehash
拓展或者收縮哈希表需要將ht[0]里所有的鍵值對(duì)重新hash到ht[1]中，但是這個(gè)rehash動(dòng)作并不是一次性集中式完成的浩习。而是分多次漸進(jìn)式完成的静暂。原因也很清楚，就是鍵值對(duì)過多時(shí)谱秽，一次性rehash肯定會(huì)消耗服務(wù)器大量的計(jì)算資源洽蛀，可能會(huì)對(duì)服務(wù)器的性能造成影響。
以下是漸進(jìn)式rehash的步驟：
- 為ht[1]分配空間
- 在字典中維持一個(gè)索引計(jì)數(shù)器變量 rehashidx疟赊，將它的值設(shè)置為0郊供，表示rehash正式開始。
- 在rehash進(jìn)行期間听绳，每次對(duì)字典進(jìn)行增刪改查時(shí)颂碘，順帶將ht[0]在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]中，同時(shí)將rehashidx增加1
- 隨著rehash的不斷進(jìn)行椅挣，最終在某個(gè)時(shí)間點(diǎn)上头岔，ht[0]上的所有鍵值對(duì)都rehash到ht[1]上了，這時(shí)將rehashidx屬性置為-1鼠证，表示rehash操作完成峡竣。
