redis数据结构—哈希表

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
云原生内存数据库 Tair,内存型 2GB
云数据库 Redis 版,经济版 1GB 1个月
简介: redis数据结构—哈希表

我在“redis存储结构”这篇文章中介绍了redis存储数据的方式——字典,redis的字典使用高效的hash table实现,这里详细介绍redis中哈希表的实现和工作原理

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

可以看到,redis的哈希表只是比我们常用的哈希表多了size、sizemask、used这三个额外字段,这三个字段是用来支持其它功能的,本文不详细介绍

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

1.next指针是用来解决哈希冲突的,没错,redis解决哈希冲突的方案是链地址法,也就是将哈希值相同的节点用链表组织起来,而redis使用rehash保证了这个链表的长度的不会太长,后面会详细介绍

2.key指向固定的对象string,这一点在“redis存储结构”文章中已经解释过

3.value使用union来实现保存不同类型值的功能,提供了较强的灵活性,且避免了全部使用指针的情况,节约了内存

哈希表的添加过程不再赘述,属于基础数据结构的范畴

解决哈希冲突

一、rehash

上文提到,redis使用链地址法解决哈希冲突,由于哈希表的数组长度在创建时就固定了,当节点数量过多时会造成链表长度过长,导致查询的时间复杂度降为O(N),导致性能降低的一个原因是数组长度,另一个是hash算法

redis的做法是,使用两个哈希表,一个为目前使用的,另一个为空,在当前使用的哈希表节点数等于数组长度时,即将发生哈希冲突,此时将另一个哈希表数组长度设置为当前的2倍,并将旧数组中的节点迁移到新数组中,这样一来,新的哈希表成为当前所使用的,并且数组的长度得到了增长,缓解了数组空间不足造成的哈希冲突

所以redis在使用哈希表时,实际上有两个哈希表,一个供当前使用,另一个供rehash使用

typedef struct dict {
    //两个Hash表,交替使用,用于rehash操作
    dictht ht[2]; 
} dict;

当旧哈希表的数据全部迁移到新哈希表后,旧哈希表的空间会被释放

rehash的过程可以进行多次,基于两个哈希表的交替使用来实现

一次性rehash的缺陷

按照我们的想法,当旧哈希表的节点数等于数组长度时,考虑进行rehash

1.rehash是一次性进行的吗?

2.rehash的过程中如果有新的数据添加进来,该怎么处理?

3.rehash的过程中如果要进行数据查找,去哪找?

当旧哈希表中的节点数量比较庞大时,一次性rehash会造成redis阻塞较长时间,无法响应其他请求,这显然不是redis的风格

渐进式rehash

既然一次性rehash会造成性能下降,那么分批次进行不就好了,

redis的方案是在 rehash 进行期间,每次哈希表元素进行新增、删除、查找或者更新操作时,Redis 除了会执行对应的操作之外,还会顺序将「旧哈希表」中索引位置上的所有 key-value 迁移到「新哈希表」 上

回到上面的问题

分次rehash的过程中会出现数据分布的情况,也就是一些数据在新哈希表中,另一些数据在旧哈希表中:

Q:

1.rehash的过程中如果有新的数据添加进来,该怎么处理?

2.rehash的过程中如果要进行数据查找,去哪找?

A:

1.如果有新的数据添加进来,将添加到新哈希表中,保证了旧哈希表的节点数只会减少,最终为空

2.先查找旧哈希表,如果没有,再查找新哈希表

rehash触发条件

在上文简单提到,当哈希节点数等于数组长度时,我们认为即将发生哈希冲突(实际上有可能已经发生),那么rehash的具体时机是怎么确定的?

触发 rehash 操作的条件,主要有两个:

  • 当负载因子大于等于 1 ,并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令,也就是没有执行 RDB 快照或没有进行 AOF 重写的时候,就会进行 rehash 操作。
  • 当负载因子大于等于 5 时,此时说明哈希冲突非常严重了,不管有没有有在执行 RDB 快照或 AOF 重写,都会强制进行 rehash 操作。
  • 当负载因子小于0.1时,程序自动进行缩容操作

负载因子 = 哈希表中当前节点数 / 哈希表数组大小

推荐学习 https://xxetb.xetslk.com/s/p5Ibb

相关实践学习
基于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
目录
相关文章
|
26天前
|
存储 NoSQL Redis
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
Redis系列学习文章分享---第十六篇(Redis原理1篇--Redis数据结构-动态字符串,insert,Dict,ZipList,QuickList,SkipList,RedisObject)
46 1
|
26天前
|
存储 消息中间件 缓存
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
Redis系列学习文章分享---第十七篇(Redis原理篇--数据结构,网络模型)
38 0
|
26天前
|
存储 NoSQL 安全
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
Redis系列学习文章分享---第十五篇(Redis最佳实践--设计优雅的key+合适的数据结构+持久化如何配置+慢查询问题解决)
34 1
|
12天前
|
消息中间件 存储 NoSQL
Redis数据结构—跳跃表 skiplist 实现源码分析
Redis 是一个内存中的数据结构服务器,使用跳跃表(skiplist)来实现有序集合。跳跃表是一种概率型数据结构,支持平均 O(logN) 查找复杂度,它通过多层链表加速查找,同时保持有序性。节点高度随机生成,最大为 32 层,以平衡查找速度和空间效率。跳跃表在 Redis 中用于插入、删除和按范围查询元素,其内部节点包含对象、分值、后退指针和多个前向指针。Redis 源码中的 `t_zset.c` 文件包含了跳跃表的具体实现细节。
|
14天前
|
存储 NoSQL Redis
Redis数据结构—跳跃表 skiplist
Redis数据结构—跳跃表 skiplist
|
20天前
|
NoSQL Redis
Redis05数据结构介绍,数据结构介绍,官方网站中看到
Redis05数据结构介绍,数据结构介绍,官方网站中看到
|
28天前
|
存储 缓存 NoSQL
Redis为什么速度快:数据结构、存储及IO网络原理总结
Redis为什么速度快:数据结构、存储及IO网络原理总结
|
存储 NoSQL 算法
「Redis」数据结构与对象
Redis数据结构与对象介绍
|
NoSQL 算法 Java
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析
我们在前文已经阐述了Redis 5种基础数据类型详解,分别是字符串(string)、列表(list)、哈希(hash)、集合(set)、有序集合(zset),以及5.0版本中Redis Stream结构详解;那么这些基础类型的底层是如何实现的呢?Redis的每种对象其实都由对象结构(redisObject) 与 对应编码的数据结构组合而成, 本文主要介绍对象结构(redisObject) 部分。
Redis进阶 - 数据结构:对象机制详解,一文深入底层分析