哈希表
结构定义dict.h/dictht
/* * 哈希表 * * 每个字典都使用两个哈希表，从而实现渐进式 rehash 。 */ typedef struct dictht { // 哈希表数组 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩码，用于计算索引值 // 总是等于 size - 1 unsigned long sizemask; // 该哈希表已有节点的数量 unsigned long used; } dictht;
table是一个数组, 每个元素是一个指向dict.h/dictEntry 结构的指针.
哈希表节点
/*哈希表节点*/ typedef struct dictEntry { // 键 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下个哈希表节点，形成链表 struct dictEntry *next; } dictEntry;
next属性指向下一个节点, 形成链表, 解决哈希冲突.
字典
/* * 字典 */ 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;
type 和 privdata属性都是针对不同类型的键值对, 为创建多态字典设置.
/* * 字典类型特定函数 */ 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;
ht数组包含两个哈希表, 一般情况下操作ht[0], ht[1] 只有在ht[0]哈希表进行rehash时使用. rehashidx, 记录了rehash的进度, 没有则为 -1 ;
哈希算法
Redis 使用MurmurHash2算法计算哈希值
解决键冲突
链地址法, 采用头插法, 时间复杂度为O(1).
rehash
1. 为 ht[1] 分配空间 : 如果是扩容, 分配大小为 第一个大于等于 ht[0] .used * 2 的 2的n次幂; 如果是收缩, 分配空间大小为 第一个大于等于 ht[0] .used 的 2的n次幂.
2. 将ht[0] 上的键值对 通过重新计算键的哈希值和索引重新分配到ht[1] 上.
3. 这时ht[0] 将变为空表, 释放ht[0], 将ht[1] 设置为ht[0], 并在ht[1]创建一个空表, 为下次rehash做准备.
渐进式rehash
在字典维持一个索引计数器 rehashidx, 设置为0, 表示正式工作.
在对字典执行添加, 删除, 查找或修改时, 将 rehashidx 索引上的所有键值对 rehash 到 hd[1], 完成后 rehashidx++;
当ht[0] 上的所有键值对被 rehash到 ht[ 1 ], 设置 rehashidx = - 1, 表示操作已经完成了.
在此期间操作数据, 会使用ht[0] 和 ht[1]两个hash表, 例如要找某个键值, 会先在ht[0] 找, 没有就去ht[ 1 ] 找. 新增操作都保存到ht[ 1 ] 中. 保证了ht[0] 只减不增, 最终为空.