字典实现
哈希表
/*
* 哈希表
*
* 每个字典都使用两个哈希表，从而实现渐进式 rehash 。
*/
typedef struct dictht {
// 哈希表数组
dictEntry **table;
// 哈希表大小
unsigned long size;
// 哈希表大小掩码，用于计算索引值
// 总是等于 size - 1
unsigned long sizemask;
// 该哈希表已有节点的数量
unsigned long used;
} dictht;
哈希表节点
/*
* 哈希表节点
*/
typedef struct dictEntry {
// 键
void *key;
// 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下个哈希表节点，形成链表
struct dictEntry *next;
} dictEntry;
字典
/*
* 字典
*/
typedef struct dict {
// 类型特定函数
dictType *type;
// 私有数据
void *privdata;
// 哈希表
dictht ht[2];
// rehash 索引
// 当 rehash 不在进行时，值为 -1
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
// 目前正在运行的安全迭代器的数量
int iterators; /* number of iterators currently running */
} dict;
字典类型特定函数
redis会为用途不同的字典设置不同的类型特点函数
/*
* 字典类型特定函数
*/
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;
哈希算法
# 使用字典设置的哈希函数，计算key的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的sizemask属性和哈希值，计算出索引值
index = hash & dict->ht[x].sizemask;
建冲突
redis采用链地址法解决冲突，新节点添加到链表的表头位置。
rehash
- 扩展：ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂；
- 收缩：ht[1]的大小为第一个大于等于ht[0].used*2的的2^n；
- 将ht[0]上的所有键值对rehash到ht[1]上
扩展与收缩的条件：
- 没有BGSAVE或者BGREWRITEAOF命令，负载因子大于等于1；
- 有BGSAVE或者BGREWRITEAOF命令时，负载因子大于等于5；
- 负载因子= ht[0].used / ht[0].size
渐进式rehash
渐进式rehash期间，删除，查找，更新等操作会在两个哈希表执行，但是添加操作在ht[1]执行。
渐进式rehash将对转移操作平均到对字典的每个添加、删除、查找、更新操作上，避免一次集中操作。
