1. 數(shù)據(jù)結(jié)構(gòu)
1.1 哈希表
typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
-
table：存儲(chǔ)節(jié)點(diǎn)的數(shù)組 -
size：table數(shù)組的長(zhǎng)度
-sizemask：size-1，用于在添加節(jié)點(diǎn)時(shí)計(jì)算節(jié)點(diǎn)在table中的位置 -
used：節(jié)點(diǎn)數(shù)量
1.2 哈希表節(jié)點(diǎn)
typedef struct dictEntry{
void *key
union {
void *val;
unit64_t u64;
int64_t s64;
}v;
struct dictEntry *next
} dictEntry;
-
key：節(jié)點(diǎn)的key -
union：節(jié)點(diǎn)的value（可以是指針、unit64_t整數(shù)西饵、int64_t整數(shù)） -
next：下一個(gè)節(jié)點(diǎn)的地址
1.3 字典
typedef struct dict {
dictType *type
void *privdata
dictht ht[2]
} dict;
-
type：操作哈希表的各種函數(shù) -
privdata：上述函數(shù)所需的入?yún)?/li> -
ht[2]：存儲(chǔ)兩個(gè)哈希表莺治，一個(gè)正常使用伶唯，另一個(gè)在rehash時(shí)使用恤左。
2. 哈希算法
- 計(jì)算哈希值
hash = dict->type->hashFunction(key);
- 計(jì)算在table數(shù)組的位置
index = hash & dict->ht[0].sizemask;
- 插入節(jié)點(diǎn)
創(chuàng)建新節(jié)點(diǎn)蔓肯，并將其插入到table[index]的第一位遭铺。
3. rehash
3.1 何時(shí)進(jìn)行rehash丽柿？
當(dāng)加載因子（load factor）大于1或小于0.1時(shí)就要進(jìn)行rehash。
加載因子計(jì)算公式：
load_factor = ht[0].used / ht[0].size
3.2 新哈希表大小的計(jì)算公式
當(dāng)需要進(jìn)行擴(kuò)容/縮容的時(shí)候魂挂，究竟創(chuàng)建多大的哈希表呢甫题？這取決于如下公式：
- 若要進(jìn)行擴(kuò)容，則新的哈希表的大小=第一個(gè)大于等于h[0].used*2的2的n次方涂召。
- 若要進(jìn)行縮容坠非，則新的哈希表的大小=第一個(gè)大于等于h[0].used的2的n次方。
3.3 rehash過程
- 創(chuàng)建一個(gè)新的哈希表h[1]果正，大小由上述公式計(jì)算得出麻顶；
- 將字典的rehashidx值從-1改為0；
- 依次遍歷ht[0]上的所有節(jié)點(diǎn)舱卡，依次轉(zhuǎn)移到ht[1]上去辅肾；
- 釋放ht[0]的內(nèi)存空間；
3.4 漸進(jìn)式rehash
- rehash過程中需要將所有節(jié)點(diǎn)遷移到新的哈希表中轮锥，如果節(jié)點(diǎn)個(gè)數(shù)很多的情況下矫钓，遷移的過程將非常漫長(zhǎng)，那么程序?qū)⑻幱谕Ｖ沟却隣顟B(tài)舍杜。所以事實(shí)上新娜，Redis的rehash過程是分多次、分布完成的既绩。
- 在rehash過程中概龄，每次對(duì)哈希表進(jìn)行增刪改查外，還要將ht[0][rehashidx]上的所有節(jié)點(diǎn)遷移到ht[1]中饲握，并將rehashidx+1私杜。從而幾次操作后，ht[0]上的所有節(jié)點(diǎn)均被遷移至ht[1]中救欧，rehash過程完成衰粹。
- 在rehash過程中，對(duì)哈希表的添加操作均在ht[1]上完成笆怠，ht[0]只減不增铝耻。
