redis数据结构实现(三)

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

redis数据结构实现(三)

3.1 字典的实现

    • *
      字典(set)是一种保存键值对的抽象数据结构。

set key value 将存在数据库字典中,键不可重复。
哈希键的底层实现之一就是字典。

    • *

Redis的字典使用哈希表作为底层实现,一个哈希表中有多个哈希节点,而每个节点中就保存了字典的一个键值对。

哈希表结构定义:

typeof struct dictht{

    //哈希表数组
    dictEntry **table;
    
    //哈希表大小
    unsigned long size;
    
    //哈希表大小掩码,用于计算索引值
    //总是等于size-1
    unsigned long sizemask;
    
    //该哈希表已有节点数
    unsigned long used;
    
}dictht;

table属性是一个数组,数组中每一个元素都是指向dictEntry结构的指针,每个dictEntry保存着一对键值。
哈希表大小掩码sizemask和key的哈希值一起决定一个键应该放在table数组上的哪个索引上.

    • *
      Image_2_

哈希节点的结构定义:

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

v中保存着键值中的值,可以是一个指针,也可以是一个int64整数,也可以是uint64整数。
*next是用来指向另个哈希表节点的指针,用来解决键哈希值冲突问题(类似于HashMap)。

字典的结构定义:

typeof struct dict{

    //类型特定函数
    dictType *type;
    
    //私有数据
    void *privdata;
    
    //哈希表
    dictht ht[2];
    
    //rehash索引,当rehash不在进行时值为-1
    in rehashidx;
    
}dict;
  • type属性和privdata属性是为了针对不同类型的键值对,为创建多态字典而设置的。

    • [ ] type属性是一个指向dictType结构的指针,每个dictType保存了一簇用于操作特定类型键值对的函数,redis为不同用途的字典设置不同类型特定的函数。
    • [ ] privdata保存了要传给那些类型特定函数的可选参数。
    • *
  • ht属性是一个包含两个项的数组,每一项都是一个dictht哈希表,一般情况下只会用ht[0],ht[1]只会在ht[0]进行rehash的时候用。
  • rehashidx记录当前rehash的进度,如果没有rehash在进行则为-1

Image

    • *

3.2 哈希算法

添加新键值对时,先用字典设置的哈希函数根据key算出哈希值,再用哈希值和sizemask按位与运算得出包含此键值对的哈希节点在哈希数组中的索引值。

3.3 键冲突


Redis用链地址法解决键冲突,每个哈希节点都有一个next指针,发生键冲突时就用next指针构成单向链表,跟hashmap一样。

3.4 rehash

为了让加载因子 loadfactor维持在合理范围内,当保存的哈希节点过多或过少的时候,需要对哈希表进行扩展或缩容。
loadfactor = 存放节点数/哈希表大小

规定:拓展操作给ht[1]分配第一个大于等于ht[0].used*2的2的n次方幂的空间
        缩容操作给ht[1]分配第一个大于等于ht[0].used的2的n次方幂的空间
        
rehash是指重新计算ht[0]上节点的哈希值和索引值并放置到ht[1]上去
当ht[0]上所有节点都转移到ht[1]上以后,释放ht[0],并将ht[1]改为ht[0]
最后在ht[1]上创建空哈希表
  • 没有在执行BGSAVE或BGREWRITEAOF命令时,负载因子大于1进行扩容
  • 在执行BGSAVE或BGREWRITEAOF命令时,负载因子大于5进行扩容
  • 负载因子小于0.1时进行缩容

因为在BGSAVE或BGREWRITEAOF命令时,Redis会创建子进程,应避免在子进程存在期间进行扩展操作,来节约内存。

    • *
    渐进式rehash详解:

如果不采取渐进式rehash,而是一股脑全部rehash,很有可能给服务器带来巨大压力
字典结构中有一个 rehashidx 用来监控rehash进度。

  1. rehash开始,rehashidx设置为0;
  2. 期间,将ht[0]中在rehashidx索引上的节点rehash到ht[1]上,rehashidx自增
  3. 所有节点都rehash到ht[1]上后,rehashidx设置为-1,表示rehash结束

    在rehash期间如果有搜索操作,将会先搜索ht[0],找不到再去ht[1]
    如果是新增节点将直接增到ht[1]中

相关实践学习
基于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
相关文章
|
18天前
|
存储 消息中间件 缓存
Redis 5 种基础数据结构?
Redis的五种基础数据结构——字符串、哈希、列表、集合和有序集合——提供了丰富的功能来满足各种应用需求。理解并灵活运用这些数据结构,可以极大地提高应用程序的性能和可扩展性。
26 2
|
1月前
|
缓存 NoSQL PHP
Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出
本文深入探讨了Redis作为PHP缓存解决方案的优势、实现方式及注意事项。Redis凭借其高性能、丰富的数据结构、数据持久化和分布式支持等特点,在提升应用响应速度和处理能力方面表现突出。文章还介绍了Redis在页面缓存、数据缓存和会话缓存等应用场景中的使用,并强调了缓存数据一致性、过期时间设置、容量控制和安全问题的重要性。
39 5
|
1月前
|
存储 消息中间件 NoSQL
Redis数据结构:List类型全面解析
Redis数据结构——List类型全面解析:存储多个有序的字符串,列表中每个字符串成为元素 Eelement,最多可以存储 2^32-1 个元素。可对列表两端插入(push)和弹出(pop)、获取指定范围的元素列表等,常见命令。 底层数据结构:3.2版本之前,底层采用**压缩链表ZipList**和**双向链表LinkedList**;3.2版本之后,底层数据结构为**快速链表QuickList** 列表是一种比较灵活的数据结构,可以充当栈、队列、阻塞队列,在实际开发中有很多应用场景。
|
2月前
|
存储 消息中间件 NoSQL
Redis 数据结构与对象
【10月更文挑战第15天】在实际应用中,需要根据具体的业务需求和数据特点来选择合适的数据结构,并合理地设计数据模型,以充分发挥 Redis 的优势。
59 8
|
2月前
|
存储 NoSQL Java
介绍下Redis 的基础数据结构
本文介绍了Redis的基础数据结构,包括动态字符串(SDS)、链表和字典。SDS是Redis自实现的动态字符串,避免了C语言字符串的不足;链表实现了双向链表,提供了高效的操作;字典则类似于Java的HashMap,采用数组加链表的方式存储数据,并支持渐进式rehash,确保高并发下的性能。
介绍下Redis 的基础数据结构
|
1月前
|
存储 NoSQL 关系型数据库
Redis的ZSet底层数据结构,ZSet类型全面解析
Redis的ZSet底层数据结构,ZSet类型全面解析;应用场景、底层结构、常用命令;压缩列表ZipList、跳表SkipList;B+树与跳表对比,MySQL为什么使用B+树;ZSet为什么用跳表,而不是B+树、红黑树、二叉树
|
1月前
|
存储 NoSQL Redis
Redis常见面试题:ZSet底层数据结构,SDS、压缩列表ZipList、跳表SkipList
String类型底层数据结构,List类型全面解析,ZSet底层数据结构;简单动态字符串SDS、压缩列表ZipList、哈希表、跳表SkipList、整数数组IntSet
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
174 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
32 1
|
22天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
43 5
下一篇
DataWorks