Redis设实 - 03 字典
《Redis设计与实现 黄建宏 著》第4章
该书基于Redis2.9，即Redis3.0开发版编写
字典
一种用于保存键值对（key-value pair）的抽象数据结构
键唯一
又称符号表（symbol table）、关联数组（associative array）或映射（map）
Redis数据库底层使用字典实现
字典底层使用哈希表实现，哈希表节点保存键值对
字典数据结构
typedef struct dict{
// 类型特定函数
dictType *type;
//私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash索引
// 未rehash时，值为-1
int rehashidx;
}dict;
类型特定函数数据结构
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;
哈希表数据结构
typedef struct dictht{
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于size-1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
}dictht;
哈希表节点数据结构
typedef struct dictEntry{
// 键
void *key;
// 值
// 可以是指针，或uint64_t整数，或int64_t整数
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
// 指向下个哈希表节点，形成链表，用于解决键冲突
struct dictEntry *next;
}dictEntry;
例：
哈希值和索引值的计算过程
1. 使用字典设置的哈希函数，计算键的哈希值
hash=dict->type->hashFunction(key);
2. 使用哈希表的sizemask属性和哈希值，计算索引值
3. 根据情况不同，ht[x]可以是ht[0]或者ht[1]
index=hash&dict->ht[x].sizemask;
注，Redis使用MurmurHash2算法计算键的哈希值
解决键冲突
哈希表使用链地址法（separate chaining）解决键冲突
因dictEntry组成的链表无表尾指针，故为考虑速度，程序总将新节点添加到链表的表头位置（复杂度为O(1)）
渐进式rehash过程
1. 为ht[1]分配空间，字典同时持有ht[0]、ht[1]两个哈希表
2. 将索引计数器变量rehashidx的值设置为0，表示rehash工作正式开始
3. rehash期间，每次对字典执行添加、删除、查找或更新操作时，程序除执行指定的操作外，还顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1]，然后将rehashidx的值增1
4. 随着字典操作的不断执行，最终在某个时间点，ht[0]的所有键值对都会被rehash到ht[1]，然后释放ht[0]，并将ht[1]设置为ht[0]，将rehashidx的值设为-1，表示rehash操作已完成
注，删除、查找、更新等操作在两个哈希表上进行，添加操作在ht[1]执行
触发rehash
满足以下任意条件执行扩展操作
1. 服务器目前未执行BGSAVE或BGREWRITEAOF命令，且哈希表负载因子>=1
2. 服务器目前正在执行BGSAVE或BGREWRITEAOF命令，且哈希表负载因子>=5
满足以下条件执行收缩操作
哈希表负载因子<0.1
负载因子计算公式
负载因子=哈希表已保存节点数量/哈希表大小
load_factor=ht[0].used/ht[0].size
分配空间
扩展操作，ht[1]的大小=第一个大于等于ht[0].used*2的2的n次方幂
收缩操作，ht[1]的大小=第一个大于等于ht[0].used的2的n次方幂