redis数据结构—哈希表

本文涉及的产品
云数据库 Tair(兼容Redis),内存型 2GB
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
简介: 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
目录
相关文章
|
1月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
52 0
数据结构与算法学习十五:哈希表
|
18天前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
22天前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
54 8
|
22天前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
1月前
|
消息中间件 存储 缓存
redis支持的数据结构
redis支持的数据结构
29 2
|
18天前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
18天前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
1月前
|
存储 缓存 Java
【数据结构】哈希表
【数据结构】哈希表
27 1
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1