Redis底层数据结构之字典
-
Redis 字典
本文重点:字典被广泛用来实现Redis的各种功能,其中包括数据库和哈希键。
Redis中的字典使用哈希表作为底层实现,每个字典带有两个哈希表,一个 平时使用(ht[0]),一个在rehash(重新散列)时使用(ht[1])。
当字典被当作数据库或者哈希键的底层实现时,Redis使用MurmurHash2算法 来计算键的哈希值。
哈希键使用链地址法来解决冲突,被分配到同一个索引上的多个键值会连接成 一个单向链表。
在对哈希表进行拓展或者收缩操作时,程序需要将现有哈希表包含的所有键值对 rehash到新的哈希表里面,并且这个rehash是渐进式的。rehash过程查询相关键值 时先到ht[0]中查找,没有找到则到ht[1]中查找。插入直接插入到ht[1],
字典的定义:
typedef struct dict {
//类型特定函数
dictType *type;
//私有数据
void *privdata;
//哈希表
dictht th[2];
//rehash索引
//当没有进行rehash时,trehashidx=-1
int trehashidx;
哈希算法
Redis计算哈希值和索引值的方法如下:
//使用字典设置的哈希函数,计算键key的哈希函数
hash = dict->type->hashFunction(key);//使用哈希表的sizemask属性和哈希值,计算出索引值
//根据情况不同,ht[x]可以是ht[0]或者th[1]
index = hash & dict->ht[x].sizemask
当字典被当作数据库或者哈希键的底层实现时,Redis使用MurmurHash2算法 来计算键的哈希值。rehash
随着操作的不断执行,哈希表保存的键值对会逐渐减少或增加,为了让哈希表的负载 因子(load factor)维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者 太少时,程序需要对哈希表的大小进行相应的拓展或者收缩——rehash:
为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行 的操作,以及ht[0]当前包含的键值对的数量(也即是ht[0].used属性的值):
如果执行的是拓展操作,那么ht[1]的大小为大于等于ht[0].used*2的第一个 2^n(2的n次幂)
如果执行的是收缩操作,那么ht[1]的大小为大于等于ht[0].used的第一个 2^n
将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash是指重新计算键的哈希值 和索引值,然后将键值对放置在ht[1]哈希表的制定位置上。
当ht[0]包含的所有键值对都迁移到了ht[1]之后(hto[0]变为空表),释放ht[0], 将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备。
由于是渐进式rehash,不是一时间将ht[0]rehash到ht[1],在rehash的过程中 删除,更新,查找操作都是现在ht[0]上进行,如果ht[0]无法进行操作,再到ht[1]上 进行操作。但是插入时直接再ht[1]上进行操作,保证了ht[1]包含的键值对之减不增, 最终变成空表。
ht[0]变化空表之后,释放ht[0],并将ht[1]设置为ht[0],然后为ht[1]分配一个空白 哈希表,设置为新的ht[1],用于下一次rehash
-
雷迪斯底层真奇妙,烦他斯体课彭少青太强了~
-
您对Redis的理解实在是深刻,我有个疑问,Redis和HashMap是否有设计上的互相借鉴。
-
@almoon 这你得问问FantasticPsq
-
-
-
@almoon HashMap和字典的rehash操作有相似之处,比如HashMap的容量和Redis的rehash中的ht[1]的容量选择非常类似,都是选用的2^n。
-
@fantasticpsq Java的HashMap从1.8对底层进行较大的优化,您能谈谈这样的优化和Redis的相似设计思想吗
-
@fantasticpsq 听说您一天就能上手kotlin语言,您能谈谈kotlin中的hashmap吗
-
@throwingup 您从哪听说的?
-
@fantasticpsq 小弟亲眼所见!
-
@throwingup 哪只眼睛?
-
@almoon 笔者能力有限,暂时不清楚Redis是否有用到红黑树
-
此回复已被删除!
-
@throwingup 。。
-
@fantasticpsq 没用红黑树,但肯定用了彭黑树