dictEntry，node of a map
typedef struct dictEntry{
void *key;
union{
void *val;
uint64_t u64;
int64_t s64;
}v;
struct dictEntry *next;
} dictEntry;
其中键值对的值可以是一个指针，或者是一个 uint64_t 整数，又或者是一个 int64_t 整数。
next 属性是指向另一个哈希节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决键冲突的问题。也就是说，Redis 的哈希表使用了链地址法来解决键冲突。
dictht(dict hash table)
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总等于 size - 1
unsigned long sizemask;
// 哈希表已有节点的数量
unsigned long used;
} dictht;
map
typedef struct dict{
dictType *type;
void *privdata;
dictht ht[2];
int trehashidx;
} dict;
ht 属性是一个包含两个项的数组，数组中的每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0] 哈希表，ht[1] 哈希表只会在对 ht[0] 哈希进行 rehash 时使用。
除了 ht[1] 之外，另一个与 rehash 有关的属性就是 rehashidx，它记录了 rehash 目前的进度，如果目前没有在进行 rehash，那么它的值为 -1.
typedef struct dictType{
unsigned int (*hashFunction) (const void *key);
void *(*keyDup) (void *privdata, const void *key);
void *(*valDup) (void *privdata,const void *obj);
int (*keyCompare) (void *privdata, const void *key1, const void *key2);
void (*keyDestructor) (void *privdata, void *key);
void (*valDestructor) (void *privdata,void *obj);
} dictType;
每个 dictType 结构保存了一簇用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同的类型特定函数。
hashFunction
Redis 计算哈希值和索引值的方法如下：
int hash = dict->type->hashFunction(key);
int index = hash & dict->ht[x].sizemask;
Redis 使用 MurmurHash2 算法来计算键的哈希值。
rehash
为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或者收缩。
Redis 对字典的哈希表执行 rehash 的步骤如下：
计算哈希表的负载因子公式：
load_factor = ht[0].used / ht[0].size
- 为字典的
ht[1]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作，以及ht[0]当前包含的键值对数量（ht[0].usedsize):
- 如果执行的是扩展操作，那么
ht[1]的大小为第一个大于等于ht[0].used*2的 2^n. - 如果执行的是收缩操作，那么
ht[1]的大小为第一个大于等于ht[0].used的 2^n.
int getRehashSize(){
int tag = 0;
if(扩展){
tag = ht[1].used * 2;
}else{
tag = ht[1].used;
}
int size = 1;
while(size < tag){
size *= 2;
}
return size;
}
- 将保存在
ht[0]中的所有键值对 rehash 到ht[1]上面。 - 当
ht[0]包含的所有键值对都迁移到了ht[1]之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次 rehash 做准备。
When will rehash happen?
扩容
- 服务器目前没有执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1.
- 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈系表的负载因子大于等于 5.
收缩
哈希表的负载因子小于 0.1 时，进行收缩操作。
渐进式 rehash
- 每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作意外，还会顺带将
ht[0]哈希表在rehashidx索引上的所有键值对 rehash 到ht[1] -
rehashidx为 0，表示开始 rehash；每完成一次对rehashidx的 rehash 操作，rehashidx增加1； rehash 完成，rehashidx为 -1.
渐进式 rehash 执行期间的哈希表操作
- rehash 期间的查询操作：先在
ht[0]表上查找，如果未找到，会去ht[1]表里查找； - rehash 期间的新增键值对操作，会直接新增到
ht[1]表中，不会新增到ht[0]中。
