首页 技术文章 数据库 浅谈Redis中的字典、哈希算法和ReHash原理
正文 评论

浅谈Redis中的字典、哈希算法和ReHash原理

本篇文章带大家了解一下Redis中的字典、哈希算法和ReHash原理,希望对大家有所帮助!

浅谈Redis中的字典、哈希算法和ReHash原理

Redis 中的字典被广泛用于实现Redis的各种功能,其中包括数据库和哈希键。

字典的底层实现为哈希表,每个字典带有两个哈希表,一个平时使用,另一个在进行rehash扩充空间时才使用。【相关推荐:Redis视频教程】

字典的结构定义

typedef struct dict {
	
	// 类型特定函数
	dictType *type;
	
	// 私有数据
	void *privdata;
	
	// 哈希表,两个元素
	dictht ht[2]
	
	// rehash时记录的索引下标,当没有rehash时,值为-1
	int rehashidx;

} dict;

==在进行 rehash时,rehashidx每迁移一个索引的entry数据就会 + 1;==

其中,哈希表dictht 的结构定义为:

typedef struct dictht {
	
	// 哈希表数组
	dictEntry **table;
	
	// 哈希表大小
	unsigned long size;
	
	// 哈希表大小掩码,用于计算索引值
	unsigned long sizenask;
	
	// 该哈希表已有节点的数量
	unsigned long uesd;

} dictht;

其中,table是一个数组,数组的每一个元素指向 dictEntry 类型的指针,dictEntry 类型里保存着一个键值对。

在这里也可以看出哈希表的节点是链表相连来解决哈希冲突问题的,也就是链地址法。

哈希冲突与哈希算法

为了实现从键到值的快速访问,Redis使用了哈希表来保存所有键值对。对应Redis设置的Key,而对应的并不是值本身,而是指向具体值的指针。使用哈希表的最大好处就是可以用O(1)的时间复杂度快速找到键值对。但既然是哈希表,那么必然会有着哈希冲突的问题。

哈希冲突即指的是,当两个key的哈希值和哈希桶计算对应关系时,正好落在了同一个哈希桶上。

Redis解决哈希冲突的方式是使用链式哈希,即拉链法。当多个元素指向同一个哈希桶时,在同一个哈希桶中采用链表来保存对应的数据,它们之间依次用指针连接。

哈希算法

当要将一个新的键值对添加到字典里面时,程序需要先根据键值对计算出哈希值和索引值,然后再根据索引值,将包含新键值对的哈希表节点放到哈希表数组的指定索引上面。

reHash 过程

在哈希表中有个负载因子(load factor)来控制哈希表保存的键值对数量。而这就需要rehash(重新散列)操作来完成。其中,负载因子的计算公式为:

// 负载因子 = 哈希表已保存的节点数量 / 哈希表大小
load_factor = ht[0].used / ht[0].size

哈希表扩展与收缩的条件如下:

  • 服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于1;
  • 服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令,并且哈希表的负载因子大于等于5;

上述的条件有一个满足,就会执行rehash的过程。

如果服务器正在执行BGSAVE 或者 BGREWRITEAOF时,Redis会创建当前服务器进程的子进程

rehash的过程大概分为三步:

  • 给哈希表2分配更大的空间,例如是当前哈希表1的两倍;

  • 把哈希表1中的数据重新映射并拷贝到哈希表2中;

  • 释放哈希表1的空间;

其中,第一步分配空间的大小是由当前的rehash操作类型 以及 当前哈希表的键值对数量决定的。

  • 当执行的是扩展操作,分配的空间大小 为第一个大于等于(哈希表的键值对数量 * 2) 的2^n 值;

    假设 当前的键值对数量为4,那么 4 * 2 = 8,因为8 刚好等于2^3,即刚好等于第一个等于2^n的值,所以扩展空间就为 8;

  • 如果执行的是收缩操作,分配的空间大小 为第一个大于等于(哈希表的键值对数量 ) 的2^n 值;

渐进式reHash

当哈希表数量多时,如果一下子将数据都复制过去,那么就很有可能对服务器造成影响。所以Redis是分多次进行rehash的,也就是渐进式rehash。

简单来说就是在第二步操作时,Redis仍然正常处理客户端请求,每处理一个请求时,从哈希表1中的第一个索引位置开始,顺带着将这个索引位置上所有的entries元素拷贝到哈希表2中;等下一次请求时,再顺带拷贝下一个索引位置的entries。

这样就很巧妙地将一次性大量拷贝的开销,分摊到多次处理请求的过程中了,避免了耗时操作,保证了数据的快速访问。

rehash时期间的哈希表操作

在进行 渐进式rehash操作时,字典的删除、查找、更新等操作会在两个哈希表中执行。例如要在字典中查找一个键的话,会先去原表中进行查询,如果找不到就会去新表查询。

而字典的添加操作一律只会保存在新表中。

更多编程相关知识,请访问:编程入门!!

以上就是浅谈Redis中的字典、哈希算法和ReHash原理的详细内容,更多请关注主题君其它相关文章!

-=||=-收藏赞 (0)
更多主题
单栏极简文艺WordPress博客主题:Diaspora主题
¥ 0 关注:20,013
详情
简约黑白WordPress个人博客主题:Personal主题
¥ 0 关注:19,974
详情
v1.0.0
小程序收录免费WordPress主题:XCX主题
¥ 0 关注:19,582
详情
v1.0.0
一款简约单栏的免费WordPress博客主题:itheme主题
¥ 0 关注:18,105
详情
功能丰富切轻量的WordPress虚拟资源主题:Rizhuti主题
¥ 599 关注:17,994
详情
大气优雅免费WordPress博客主题:HONEY主题
¥ 0 关注:14,845
详情
回复
暂无评论

不要再留垃圾评论了,主题君整理资源不容易,留几句鼓励的话吧。