哈希表
typedef struct dictht{
dictEntry ** table; //哈希表數(shù)組
unsigned long size; //哈希表大小
unsigned long sizemask; //哈希表大小掩碼，用于計算索引值席里，總是等于size-1
unsigned long used; //該哈希表已有節(jié)點的數(shù)量
}dictht;
其中主要是table用于存放數(shù)據(jù)奖磁，其是一個dictEntry指針數(shù)組
哈希表節(jié)點
typedef struct dictEntry{
void *key; //鍵
union{
void *val;
uint64_tu64;
int64_ts64;
}v; //值
struct dictEntry *next;
}dictEntry;
字典的實現(xiàn)
typedef struct dictEntry{
dictType *type; //類型特定函數(shù)
void *privdata; //私有數(shù)據(jù)
dictht ht[2]; //哈希表
int rehashidx; //rehash索引咖为，當(dāng)rehash不在進行時，值為-1
}dict;
- 其中的type屬性和privdata屬性是針對不同類型的鍵值對封恰，為創(chuàng)建多態(tài)字典而設(shè)置的诺舔。
typedef struct dictEntry{
unsigned int (*hashFunction)(const void *key); //計算哈希值的函數(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); //對比鍵的函數(shù)
void *(*keyDestructor)(void *privdata,const void *key); //銷毀鍵的函數(shù)
void *(*valDestructor)(void *privdata,const void *obj); //銷毀值的函數(shù)
}
- ht是個長度為2的數(shù)組备畦，一般情況下懂盐，字典只使用ht[0]莉恼，ht[1]只在rehash時使用
- rehashidx也跟rehash有關(guān)，記錄了rehash的進度尿背。如果當(dāng)前沒有進行rehash捶惜，則值為-1
哈希算法
當(dāng)有新的鍵值要插入字典時，程序會對鍵進行hash值計算鹤竭，然后計算其索引值臀稚，其步驟如下
- 計算hash：hash=dict->type->hashFunction(key);
- 計算索引：indix=hash & dict->ht[x].sizemask;
redis使用的是MurmurHash2來計算鍵的哈希值
解決鍵的沖突
redis采用鏈地址法來解決鍵的沖突啡直，即每個哈希表節(jié)點有一個next指針酒觅，多個哈希表節(jié)點可以使用next指針構(gòu)成一個單鏈表，被分配到同一個索引的多個節(jié)點就可以使用這個單鏈表連接起來舷丹，以解決鍵的沖突颜凯。
rehash（重新散列）
rehash是對哈希表進行相應(yīng)的擴展和收縮仗扬，即哈希表重新分配內(nèi)存的過程，以維持哈希表的負(fù)載因子在一個合理的范圍
redis對字典的哈希表rehash步驟如下
- 為字典的ht[1]哈希表分配空間彼城，其分配的大小取決于執(zhí)行的操作以及ht[0]當(dāng)前包含的鍵值對的數(shù)量（ht[0].used的值）
- 當(dāng)是擴展操作募壕，則ht[1]的大小為第一個大于等于ht[0].used*2的2^n（2的n次冪）
- 當(dāng)執(zhí)行的時收縮操作舱馅，則ht[1]的大小為第一個大于等于ht[0].used的2^n
- 將保存在ht[0]中的所有鍵值對rehash到ht[1]上面
- 當(dāng)ht[0]包含的所有鍵值對遷移到ht[1]之后（ht[0]變?yōu)榭毡恚┐停尫舎t[0],將ht[1]設(shè)置為ht[0]干毅，并在ht[1]新創(chuàng)鍵一個空哈希表溶锭，為下次rehash做準(zhǔn)備
哈希表的負(fù)載因子
負(fù)載因子=哈希表已保存節(jié)點數(shù)量/哈希表大小
load_factor=ht[0].used/ht[0].size
哈希表的擴展與收縮
擴展
- 當(dāng)服務(wù)器目前沒有執(zhí)行BGSAVE或者BGREWRITEAOF命令趴捅，且哈希表的負(fù)載因子大于等于1
- 服務(wù)器目前正在執(zhí)行BGSAVE或者BGREWRITEAOF命令,并且哈希表的負(fù)載因子大于等于5
- 在執(zhí)行BGSAVE或者BGREWRITEAOF命令過程中，redis需要創(chuàng)建當(dāng)前服務(wù)器進程的子進程综芥，而大多數(shù)操作系統(tǒng)采用寫時復(fù)制技術(shù)來優(yōu)化子進程的使用效率膀藐，所以在子進程存在期間红省，服務(wù)器會提高執(zhí)行擴展操作所需要的負(fù)載因子吧恃，從而避免在子進程存在期間進行哈希表擴展的操作，這可以避免不必要的內(nèi)存寫入痕寓，最大限度節(jié)約內(nèi)存
收縮
- 當(dāng)負(fù)載因子小于0.1時呻率，程序?qū)１磉M行收縮操作
漸進式rehash
rehash并不是由一次性礼仗，集中式完成的藐守，而是分多次卢厂，漸進式地完成的
步驟：
- 為ht[1]分配空間
- 在字典中維持一個索引計數(shù)器變量rehashidx乾蓬，并設(shè)置為0,表示rehash正式開始
- rehash期間，每次對字典執(zhí)行添加慎恒，刪除任内，查找，更新操作時融柬，程序除了執(zhí)行指定操作外死嗦，也會同時將ht[0]哈希表在rehashidx索引上的所有鍵值對rehash到ht[1]（避免集中式rehash帶來龐大的計算量），當(dāng)rehash完成粒氧，rehashidx屬性值增加一
- 最終在某個時間點上越除，ht[0]上的所有鍵值對都被rehash到ht[1]上，這時程序?qū)ehashidx設(shè)置為-1，表示rehash操作已經(jīng)完成
本文來自redis設(shè)計與實現(xiàn)
