1. 数据结构
1.1 哈希表
typedef struct dictht{
dictEntry **table;
unsigned long size;
unsigned long sizemask;
unsigned long used;
} dictht;
-
table：存储节点的数组 -
size：table数组的长度
-sizemask：size-1，用于在添加节点时计算节点在table中的位置 -
used：节点数量
1.2 哈希表节点
typedef struct dictEntry{
void *key
union {
void *val;
unit64_t u64;
int64_t s64;
}v;
struct dictEntry *next
} dictEntry;
-
key：节点的key -
union：节点的value（可以是指针、unit64_t整数、int64_t整数） -
next：下一个节点的地址
1.3 字典
typedef struct dict {
dictType *type
void *privdata
dictht ht[2]
} dict;
-
type：操作哈希表的各种函数 -
privdata：上述函数所需的入参 -
ht[2]：存储两个哈希表，一个正常使用，另一个在rehash时使用。
2. 哈希算法
- 计算哈希值
hash = dict->type->hashFunction(key);
- 计算在table数组的位置
index = hash & dict->ht[0].sizemask;
- 插入节点
创建新节点，并将其插入到table[index]的第一位。
3. rehash
3.1 何时进行rehash？
当加载因子（load factor）大于1或小于0.1时就要进行rehash。
加载因子计算公式：
load_factor = ht[0].used / ht[0].size
3.2 新哈希表大小的计算公式
当需要进行扩容/缩容的时候，究竟创建多大的哈希表呢？这取决于如下公式：
- 若要进行扩容，则新的哈希表的大小=第一个大于等于h[0].used*2的2的n次方。
- 若要进行缩容，则新的哈希表的大小=第一个大于等于h[0].used的2的n次方。
3.3 rehash过程
- 创建一个新的哈希表h[1]，大小由上述公式计算得出；
- 将字典的rehashidx值从-1改为0；
- 依次遍历ht[0]上的所有节点，依次转移到ht[1]上去；
- 释放ht[0]的内存空间；
3.4 渐进式rehash
- rehash过程中需要将所有节点迁移到新的哈希表中，如果节点个数很多的情况下，迁移的过程将非常漫长，那么程序将处于停止等待状态。所以事实上，Redis的rehash过程是分多次、分布完成的。
- 在rehash过程中，每次对哈希表进行增删改查外，还要将ht[0][rehashidx]上的所有节点迁移到ht[1]中，并将rehashidx+1。从而几次操作后，ht[0]上的所有节点均被迁移至ht[1]中，rehash过程完成。
- 在rehash过程中，对哈希表的添加操作均在ht[1]上完成，ht[0]只减不增。
