Redis字典

Redis字典

一种用于保存键值对的抽象数据结构,Redis的数据库就是使用字典来作为底层实现的,字典还是哈希键的底层实现之一.

字典的实现

Redis中字典使用哈dictht表作为底层,一个哈希表里面可以有多个哈希表结点,而每个哈希表结点就保存了字典中的一个键值对.

哈希表

typedef struct dictht{
	//哈希表数据
	dictEntry **table;
	//哈希表大小
	unsigned long size;
	//哈希表大小掩码,用于计算索引值
	//总是等于size - 1
	unsigned long sizemask;
	//该哈希表已有结点数量
	unsigned long used;
}dictht;

table是一个数组,数组中每一个元素指向dictEntry结构的指针

size是哈希表的大小也就是数组的大小

used是哈希表中键值对的数量

sizemask用来确定一个键应该被放到table数组的哪一个索引里面

哈希表结点

typedef struct dictEntry{
	//键
	void *key;
	//值
	union{
		void *val;
		uint64_t u64;
		int64_t s64;
	}v;
	//指向下一个哈希表结点,形成链表
	struct dictEntry *next;
}dictEntry;

key保存键 v 保存值 next是使用链地址法来解决哈希冲突

字典

typedef struct dict{
	//类型特定函数
	dictType *type;
	//私有属性
	void *privdata;
	//哈希表
	dictht ht[2];
	//rehash 索引
	//当rehash不在进行时值为-1
	int rehashidx;
}dict;

ht属性

是一个包含两个项的数组,数组中每个项都是一个哈希表,ht[1]会在rehash时候使用,正常情况下只使用ht[0].

rehashidx

它记录了rehash目前的进度,如果目前没有在进行rehash,那么他的值为-1。

哈希算法

使用字典设置的哈希函数计算键key的哈希值

hash = dict->type->hashFunction(key);

使用哈希表的sizemsk属性和哈希值计算出索引值

index = hash & dict->ht[x].sizemask;

计算到索引之后表示此k-v键值对应该被放到哈希表对应索引中

解决键冲突

Redis使用链地址法来解决键冲突

特点:因为dictEntry结点组成的链表没有指向链表表尾的指针,也就是没有像Redis链表一样的指向头和尾的指针,所以为了速度考虑,当出现哈希冲突时Redis总是使用头插法,将新结点插到最前面。

rehash(重新散列)

为了让哈希表的负载因子维持在一个合理的范围之内,程序会对哈希表进行扩展或者收缩。可以通过rehash完成。

rehash步骤

1.为ht[1]分配空间

​ 扩展操作:ht[1]的大小为2^n (2^n >= ht[0].used*2 )n取最小值 键值对数量的二倍

​ 收缩操作: ht[1]的大小为2^n (2^n >= ht[0].used)n取最小值 键值对数量

2.将ht[0]中的所有键值对执行rehash到ht[1] 重新计算哈希值与索引
3.迁移完毕后,释放ht[0] 将ht[1]设置为ht[0] 并在ht[1]创建一个空的哈希表

渐进式rehash

这个动作分多次的渐进式的完成

1.为ht[1]分配空间,让字典同时存在两个哈希表ht[0]和ht[1]
2.字典dict中的rehashidx(索引计数器)将其设置为0,表示rehash开始
3.在rehash期间对字典执行添加、删除、查找、或者更新操作程序除了执行操作还会顺带将ht[0]在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作结束后rehashidx+1
4.当ht[0]上的所有键值都被rehash到ht[1]上时,将rehashidx设置为-1,表示rehash操作完成。

渐进式rehash的好处在于它采取分而治之的方式,将rehash的操作分解到对字典的增删改查上,避免了集中式rehash带来的大计算量

渐进式rehash执行期间的哈希表操作

再次过程中字典会同时使用ht[0]和ht[1]两个哈希表,字典的个助攻操作都会在两个哈希表上进行,eg查找一个键会先查找ht[0]然后查找ht[1],另外在rehash执行期间,新添加的键值对会被保存到ht[1]里面,而ht[0]不会在进行添加操作。

上一篇:2021-09-04


下一篇:Talib技术因子详解(六)