字典(dict.h/dict.c)¶
Redis字典具有以下特点:
- Redis字典的底层实现为哈希表,
- 每个字典使用两个哈希表, 一般情况下只使用 0 号哈希表, 只有在 rehash 进行时, 才会同时使用 0 号和 1 号哈希表。
- 哈希表使用链地址法来解决键冲突的问题。
- 自动 Rehash 扩展或收缩哈希表。
- 对哈希表的 rehash 是分多次、渐进式地进行的。
数据结构¶
/*
* hash节点
*/
typedef struct dictEntry {
//键
void *key;
//值
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
//指向下一个节点
struct dictEntry *next;
} dictEntry;
typedef struct dictht {
//桶
dictEntry **table;
//指针数组大小
unsigned long size;
//指针数组掩码,用于计算索引值
unsigned long sizemask;
//hash表现有节点数量
unsigned long used;
} dictht;
typedef struct dict {
//类型处理函数
dictType *type;
//类型处理函数私有值
void *privdata;
//两个hash表
dictht ht[2];
//rehash标示,为-1表示不在rehash,不为0表示正在rehash的桶
int rehashidx; /* rehashing not in progress if rehashidx == -1 */
//当前正在运行的安全迭代器数量
int iterators; /* number of iterators currently running */
} dict;
dict的结构如下:
字典中添加元素的过程¶
rehash介绍¶
字典的 rehash 操作实际上就是执行以下任务:
创建一个比 ht[0]->table 更大的 ht[1]->table , size为大于used*2的2的指数, 开始值为4;
将 ht[0]->table 中的所有键值对迁移到 ht[1]->table ;
将原有 ht[0] 的数据清空,并将 ht[1] 替换为新的 ht[0] ;
进行rehash的条件:
自然 rehash : ratio >= 1 ,且变量 dict_can_resize 为真。
强制 rehash : ratio 大于变量 dict_force_resize_ratio (目前版本中, dict_force_resize_ratio 的值为 5 )。
阶进rehash:
主动方式:databaseCron中调用dictRehashMilliseconds执行一毫秒。
被动方式:调用dictAdd,dicFind,dictDelete,dictGetRandomKey时,调用_dictRehashStep,迁移一个非空桶。