Redis源码阅读笔记(2)——字典(Map)实现原理

因为redis是用c写的,c中没有自带的map,所以redis自己实现了map,来看一下redis是怎么实现的。

1、redis字典基本数据类型

redis是用哈希表作为字典的底层实现,dictht是哈希表的定义:

typedef struct dictht {

    // 哈希表节点指针数组(俗称桶,bucket)
dictEntry **table; // 指针数组的大小
unsigned long size; // 指针数组的长度掩码,用于计算索引值
unsigned long sizemask; // 哈希表现有的节点数量
unsigned long used; } dictht;

table是一个数组,数组中的元素都是一个指向dictEntry结构的指针,每个dictEntry结构保存着一个键值对。

dictEntry的结构如下:

typedef struct dictEntry {

    // 键
void *key; // 值
union {
void *val;
uint64_t u64;
int64_t s64;
} v; // 链往后继节点
struct dictEntry *next; } dictEntry;

可以看到有个next指针,是用链表法来解决hash冲突的;v保存值,可以是一个指针,uint64_t整数,或者int64_t整数。

Redis中字典的结构如下:

typedef struct dict {

    // 特定于类型的处理函数
dictType *type; // 类型处理函数的私有数据
void *privdata; // 哈希表(2个)
dictht ht[]; // 记录 rehash 进度的标志,值为-1 表示 rehash 未进行
int rehashidx; // 当前正在运作的安全迭代器数量
int iterators; } dict;

这里需要解释一下dictType和privdata,前者是一组用于操作键值对的函数,redis会对不同用途的字典使用不同的函数,后者是这些函数需要用的可选参数。

ht[2]就是两个哈希表,一般情况下只会ht[0],ht[1]会在对ht[0]进行rehash时使用。rehashidx记录了rehash目前的进度,如果目前没有进行rehash那么rehashidx=-1。

2、哈希算法以及解决哈希冲突

redis使用MurmurHash2算法,哈希冲突使用链地址法,redis总是将新节点添加到链表头部。

3、rehash和渐进式rehash

redis的哈希表会随着对其操作而增大或减小,那么为了让负载因子保持合理,也保持字典的高效,需要在哈希表中数量太多或太少时进行扩展或收缩。

redis最小哈希表大小为DICT_HT_INITIAL_SIZE=4,扩展操作的话ht[1]的大小为第一个大于等于ht[0].used*2的2^n;收缩操作ht[1]的大小为第一个大于等于ht[0].used的2^n。然后将ht[0]中的所有键值对rehash到ht[1]上,当全部rehash之后,把ht[1]置为ht[0],并为ht[1]新创建一个空白哈希表,为下次rehash做准备。

渐进式rehash,让字典同时持有ht[0]和ht[1],将rehashidx设为0,表示rehash开始;在rehash期间,每次对字典进行增删查改操作时,redis除了执行指定的操作以外,还会顺带把ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash完成,rehashidx++;随着时间及操作的执行,最终ht[0]的所有键值对会rehash到ht[1]上,然后把rehashidx置为-1;表示rehash结束。

在渐进式rehash的过程中,字典的删除,查找,更新等操作会在两个哈希表上进行,新增的键值对会保存到ht[1]里面,这样保证了ht[0]里的键值对只增不减,最终变为空表。

上一篇:【转】统计模型-n元文法


下一篇:Luogu2183 礼物 ExLucas、CRT