redis哈希的底层实现

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 本文将介绍redis哈希的底层实现

字典中,一个键可以和一个值进行关联,这些关联的键和值就成为键值对。字典中的每个键都是独一无二的,程序可以在字典中根据键找到与之关联的值。字典常作为一种数据结构内置在高级编程语言中,但Redis所使用的c语言没有内置这种数据结构,因此Redis构建了自己的字典实现


1.字典的实现

Redis的字典使用哈希表作为底层实现,一个哈希表里可以有多个哈希表节点,而每个哈希表节点就保存了字典中的一个键值对。接下来将分别介绍Redis的哈希表、哈希表节点和字典的实现。

1.1哈希表的实现

Redis字典使用的哈希表由dict.h/dictht结构定义:

typedefstructdictht//哈希表数组dictEntry*table;
//哈希表大小unsignedlongsize;
// 哈希表大小掩码,用于计算索引值//总是等于 size-1unsignedlongsizemask;
//该哈希表已有节点的数量unsignedlongused;
} dictht:

image.png

  • table属性是一个数组,数组的每个元素都是一个指向dictEntry结构的指针,每个dictEntry结构保存这一个键值对。
  • size记录table数组的大小。
  • used记录当前已有节点的数量,即该字典的元素数量
  • sizemask的属性总是size - 1,这个属性和哈希值一起决定一个键放在table数组的哪个索引上


1.2哈希表节点的实现

哈希表节点使用dictEntry结构实现,每个dictEntry结构保存着一个键值对。

typedefstructdictEntry {
//键void*key:
//值union{
void*val;
uint64_tu64;
int64_ts64;
    } v:
//指向下个哈希表节点,形成链表structdictEntry*next;
} dictEntry;

image.png

  • key表示键
  • v表示对应的值,其中键值对中的值可以是一个指针、uint64位整数或者int64位整数
  • next属性是指向另外一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接起来,从而解决键冲突的问题。


1.3字典的实现

Redis中的字典由dict.h/dict结构表示:

typedefstructdict {
//类型特定函数dictType*type;
//私有数据voidsprivdata;
//哈希表dicththt[2]:
//rehash 索引// 当rehash 不在进行时,值为一1intrehashidx; /*rehashing not in progress if rehashidx */} dict:

type属性和privdate属性是针对不同类型的键值对,为创建多态字典而设置的:

  • type属性是一个指向dictType结构的指针,每个底朝天Type结构保存了一簇用于操作特定类型键值对的函数,Redis会为用途不同的字典设置不同的类型特定函数。
typedefstructdictType{
//计算哈希值的西数unsignedint (*hashFunction) (constvoid*key) ;
//复制键的函数voida(*keyDup) (void*privdata, constvoid*key);
//复制值的函数void (evalDup) (voideprivdata, constvoid*obj;
//对比键的函数int (*keyCompare) (void*privdata, constvoid*key1, constvoid*key2);
//销毁键的函数void (*keyDestructor) (voidaprivdata, voidkey);
// 销毁值的函数void (*valDestructor) (voidprivdata, void :obi);
}dictType;
  • privdata保存了需要传给那些类型特定函数的可选参数
  • ht是一个包含两个项的数组,每个项都是有一个dictht哈希表。一般情况下,字典只使用ht[0]哈希表,ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。
  • rehashidx记录了rehash目前的进度,如果没有rehash,那么它的值为-1

image.png


2.哈希算法

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

Redis计算哈希值和索引值的方法:

  • 使用字典设置的哈希函数,计算key的哈希值
  • 使用哈希表的sizemask属性和哈希值,计算索引值


3.解决哈希冲突

Redis的哈希表使用链地址法来解决哈希冲突,每个哈希表节点都有一个next指针,多个哈希表节点使用next指针连接起来构成单向链表,被分配到同一个索引上的多个节点可以用这个链表连接起来。因为dictEntry节点组成的链表没有执行链表表尾的指针,为了速度考虑,程序总是将新节点添加到链表的表头位置(复杂度为O(1))。


4.rehash

随着操作的不断执行,哈希表保存的键值对会逐渐地增多或者减少,为了让哈希表的负载因子维持在一个合理的范围之内,程序需要对哈希表的大小进行相应的拓展或者收缩,拓展和收缩哈希表的工作通过执行rehash(重新散列)操作来完成,步骤如下:

1)为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作,以及ht[0]当前包含键值对数量(及ht[0].used属性值):

  • 如果执行的是拓展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方幂
  • 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2的n次方幂。

2)将保存在ht[0]中的所有键值对rehash到ht[1]上面:rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。

3)迁移之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新建一个空白哈希表,为下一次rehash做准备。

注意:rehash并不是一次性的,而是根据ht[0]的键值对大小分几次、渐进式rehash。

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
6月前
|
存储 缓存 NoSQL
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(一)
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)
108 0
|
6月前
|
NoSQL Redis
Redis的常用数据结构之哈希类型
Redis的常用数据结构之哈希类型
32 0
|
14天前
|
存储 NoSQL Redis
Redis 哈希(Hash)
10月更文挑战第16天
30 1
|
2月前
|
存储 NoSQL 算法
5)深度解密 Redis 的哈希(Hash)
5)深度解密 Redis 的哈希(Hash)
26 0
|
3月前
|
存储 NoSQL 算法
Redis6入门到实战------ 三、常用五大数据类型(列表(List)、集合(Set)、哈希(Hash)、Zset(sorted set))
这是关于Redis 6入门到实战的文章,具体内容涉及Redis的五大数据类型:列表(List)、集合(Set)、哈希(Hash)、有序集合(Zset(sorted set))。文章详细介绍了这些数据类型的特点、常用命令以及它们背后的数据结构。如果您有任何关于Redis的具体问题或需要进一步的帮助,请随时告诉我。
|
4月前
|
存储 缓存 NoSQL
Redis问题之一致性Hash是如何解决哈希+取余方法中的稳定性问题的
Redis问题之一致性Hash是如何解决哈希+取余方法中的稳定性问题的
65 10
|
6月前
|
存储 NoSQL 算法
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)(二)
【Redis技术进阶之路】「底层源码解析」揭秘高效存储模型与数据结构底层实现(字典)
114 0
|
5月前
|
存储 JSON NoSQL
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
|
5月前
|
存储 NoSQL 算法
Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
Redis集群,集群的概念 三种主流分片方式1.哈希求余 一致性哈希算法:方案三:哈希槽分区算法问题一Redis集群是最多有16384个分片吗问题二:为什么是16384个,集群扩容:1.新的主节点
|
5月前
|
NoSQL Java Redis
【Redis】 Java操作客户端命令——列表操作与哈希操作
【Redis】 Java操作客户端命令——列表操作与哈希操作