哈希表
typedef struct dictht{
dictEntry ** table; //哈希表數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩碼，用于計(jì)算索引值，總是等于size-1
unsigned long used; //該哈希表已有節(jié)點(diǎn)的數(shù)量
}dictht;
其中主要是table用于存放數(shù)據(jù)，其是一個(gè)dictEntry指針數(shù)組
哈希表節(jié)點(diǎn)
typedef struct dictEntry{
void *key; //鍵
union{
void *val;
uint64_tu64;
int64_ts64;
}v; //值
struct dictEntry *next;
}dictEntry;
字典的實(shí)現(xiàn)
typedef struct dictEntry{
dictType *type; //類型特定函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //哈希表
int rehashidx; //rehash索引，當(dāng)rehash不在進(jìn)行時(shí)，值為-1
}dict;
- 其中的type屬性和privdata屬性是針對(duì)不同類型的鍵值對(duì)，為創(chuàng)建多態(tài)字典而設(shè)置的。
typedef struct dictEntry{
unsigned int (*hashFunction)(const void *key); //計(jì)算哈希值的函數(shù)
void *(*keyDup)(void *privdata,const void *key); //復(fù)制鍵的函數(shù)
void *(*valDup)(void *privdata,const void *obj); //復(fù)制值的函數(shù)
int (*keyCompare)(void *privdata,const void *key1,const void *key2); //對(duì)比鍵的函數(shù)
void *(*keyDestructor)(void *privdata,const void *key); //銷毀鍵的函數(shù)
void *(*valDestructor)(void *privdata,const void *obj); //銷毀值的函數(shù)
}
- ht是個(gè)長(zhǎng)度為2的數(shù)組，一般情況下，字典只使用ht[0]，ht[1]只在rehash時(shí)使用
- rehashidx也跟rehash有關(guān)，記錄了rehash的進(jìn)度。如果當(dāng)前沒有進(jìn)行rehash，則值為-1
哈希算法
當(dāng)有新的鍵值要插入字典時(shí)，程序會(huì)對(duì)鍵進(jìn)行hash值計(jì)算，然后計(jì)算其索引值，其步驟如下
- 計(jì)算hash：hash=dict->type->hashFunction(key);
- 計(jì)算索引：indix=hash & dict->ht[x].sizemask;
redis使用的是MurmurHash2來計(jì)算鍵的哈希值
解決鍵的沖突
redis采用鏈地址法來解決鍵的沖突，即每個(gè)哈希表節(jié)點(diǎn)有一個(gè)next指針，多個(gè)哈希表節(jié)點(diǎn)可以使用next指針構(gòu)成一個(gè)單鏈表，被分配到同一個(gè)索引的多個(gè)節(jié)點(diǎn)就可以使用這個(gè)單鏈表連接起來，以解決鍵的沖突。
rehash（重新散列）
rehash是對(duì)哈希表進(jìn)行相應(yīng)的擴(kuò)展和收縮，即哈希表重新分配內(nèi)存的過程，以維持哈希表的負(fù)載因子在一個(gè)合理的范圍
redis對(duì)字典的哈希表rehash步驟如下
- 為字典的ht[1]哈希表分配空間，其分配的大小取決于執(zhí)行的操作以及ht[0]當(dāng)前包含的鍵值對(duì)的數(shù)量（ht[0].used的值）
- 當(dāng)是擴(kuò)展操作，則ht[1]的大小為第一個(gè)大于等于ht[0].used*2的2^n（2的n次冪）
- 當(dāng)執(zhí)行的時(shí)收縮操作，則ht[1]的大小為第一個(gè)大于等于ht[0].used的2^n
- 將保存在ht[0]中的所有鍵值對(duì)rehash到ht[1]上面
- 當(dāng)ht[0]包含的所有鍵值對(duì)遷移到ht[1]之后（ht[0]變?yōu)榭毡恚?，釋放ht[0],將ht[1]設(shè)置為ht[0]，并在ht[1]新創(chuàng)鍵一個(gè)空哈希表，為下次rehash做準(zhǔn)備
哈希表的負(fù)載因子
負(fù)載因子=哈希表已保存節(jié)點(diǎn)數(shù)量/哈希表大小
load_factor=ht[0].used/ht[0].size
哈希表的擴(kuò)展與收縮
擴(kuò)展
- 當(dāng)服務(wù)器目前沒有執(zhí)行BGSAVE或者BGREWRITEAOF命令，且哈希表的負(fù)載因子大于等于1
- 服務(wù)器目前正在執(zhí)行BGSAVE或者BGREWRITEAOF命令,并且哈希表的負(fù)載因子大于等于5
- 在執(zhí)行BGSAVE或者BGREWRITEAOF命令過程中，redis需要?jiǎng)?chuàng)建當(dāng)前服務(wù)器進(jìn)程的子進(jìn)程，而大多數(shù)操作系統(tǒng)采用寫時(shí)復(fù)制技術(shù)來優(yōu)化子進(jìn)程的使用效率，所以在子進(jìn)程存在期間，服務(wù)器會(huì)提高執(zhí)行擴(kuò)展操作所需要的負(fù)載因子，從而避免在子進(jìn)程存在期間進(jìn)行哈希表擴(kuò)展的操作，這可以避免不必要的內(nèi)存寫入，最大限度節(jié)約內(nèi)存
收縮
- 當(dāng)負(fù)載因子小于0.1時(shí)，程序?qū)１磉M(jìn)行收縮操作
漸進(jìn)式rehash
rehash并不是由一次性，集中式完成的，而是分多次，漸進(jìn)式地完成的
步驟：
- 為ht[1]分配空間
- 在字典中維持一個(gè)索引計(jì)數(shù)器變量rehashidx，并設(shè)置為0,表示rehash正式開始
- rehash期間，每次對(duì)字典執(zhí)行添加，刪除，查找，更新操作時(shí)，程序除了執(zhí)行指定操作外，也會(huì)同時(shí)將ht[0]哈希表在rehashidx索引上的所有鍵值對(duì)rehash到ht[1]（避免集中式rehash帶來龐大的計(jì)算量），當(dāng)rehash完成，rehashidx屬性值增加一
- 最終在某個(gè)時(shí)間點(diǎn)上，ht[0]上的所有鍵值對(duì)都被rehash到ht[1]上，這時(shí)程序?qū)ehashidx設(shè)置為-1，表示rehash操作已經(jīng)完成
本文來自redis設(shè)計(jì)與實(shí)現(xiàn)
