• 售前

  • 售后

热门帖子
入门百科

通俗易懂redis数据结构之链表+字典

[复制链接]
是鹅好甜 显示全部楼层 发表于 2022-1-12 12:14:18 |阅读模式 打印 上一主题 下一主题
通俗易懂redis数据结构之链表+字典



数据结构之链表

上次写了SDS的内容,很荣幸上了CSDN热榜,距离今天已经过了好久了,因为最近在看一些其他的东西,加上工作有点忙,所以就停止了,这次主要写下链表和字典。
链表定义

链表在redis中使用也是比较多的,比如key对应的元素比较多或者元素包含字符串比较长、发布与订阅、监视器等都会用到链表。
每个链表节点使用一个adlist.h/listNode结构表示,如下:
  1. typedef struct listNode {
  2.         // 前置节点
  3.         typedef listNode *prev;
  4.         // 后置节点
  5.         typedef listNode *next;
  6.         // 节点的值
  7.         void *value;
  8. } listNode
  9. // 这里其实不用多解释的,双端链表嘛,有前驱节点和有后继节点,next指向下一个节点指针,pre指向前一个节点指针
复制代码
最经典的比如使用list类型时,l/rpush元素,使用llen获取元素个数等这些操作,在一开始接触时,就想获取元素个数应该不是通过遍历O(n)复杂度来获取长度吧?其实还有使用adlist.h/list来持有的链表,如下:
  1. typedef struct list {
  2.         // 表头节点
  3.         listNode *head;
  4.         // 表尾节点
  5.         listNode *tail;
  6.         // 链表长度
  7.         unsigned long len;
  8.         // 节点值复制函数
  9.         void *(*dup)(void *ptr);
  10.         // 节点值释放函数
  11.         void *(*free)(void *ptr);
  12.         // 节点值对比函数
  13.         int (*match)(void *ptr,void *key);
  14. } list;
复制代码
以上的dup、free、match是实现多态链表所需的类型特定函数,所以可以保存不同类型的值:


  • dup函数用于复制链表节点所保存的值
  • free函数用于释放链表节点所保存的值
  • match函数用于对比链表节点所保存的值和另一个输入值是否相等
    一个list结构和三个listNode结构如下:

    通过上面方式实现redis链表就有了如下特性:
  • 双端:节点都有pre和next,获取前驱和后继节点复杂度O(1)
  • 链表无环:表头的前驱结点以及表尾的后继节点都指向null
  • 获取表头和表尾节点复杂度O(1)
  • 获取链表长度复杂度O(1)
  • void *指针保存节点值,通过list结构的dup、free、match三属性为节点值设置类型特定函数,所以链表可以用于保存不同类型的值。
数据结构之字典

字典嘛,我首先会想到的就是map这种东西,其实就是一个key和value的映射,在字典里,每个键都是唯一的,可以根据键来进行查找、删除、更新操作等。这种字典在java中很多数据结构使用,但是redis构建了自己的字典。
字典使用

比如如下代码块set一个值,就会将键值对保存在字典里,除了数据库,字典还是哈希键的实现之一,当哈希键键值对比较多或者键值对中元素都是比较长的字符串时,就会使用字典作为其实现。
  1. set name dtxld // 简单的string类型
复制代码
下面主要是由字典来进行的一些延伸:字典的数据结构如下:
  1. typedef struct dict {
  2.         // 类型特定函数
  3.         dictType *type;
  4.         // 私有数据
  5.         void *privdata;
  6.         // hash表(这里可以对比下hashMap)
  7.         dicht ht[2];
  8.         // rehash索引,rehash不进行时,值为-1
  9.         int rehashidx;
  10. } dict
复制代码
上面的参数其实都好理解,对于我这个新手来说主要陌生的就是type、privdata、ht,下面分析下:
type属性指向了dictType结构的指针,每个dictType保存了一簇用于操作特定类型键值对的函数,redis为用途不同的字典设置不同的类型特定函数(可以参考下双端链表),privdata属性保存了需要传给类型特定函数的可选参数,dictType结构如下:
  1. typedef struct dictType {
  2.         // 计算哈希值函数
  3.         unsigned int (*hashFunction)(const void *key);
  4.         // 复制键的函数
  5.         void *(*keyDup)(void *privdata, const void *key);
  6.         // 复制值的函数
  7.         void *(*valDup)(void *privdata, const void *obj);
  8.         // 对比键的函数
  9.         int (*keyCompare)(void *privdata, const void *key1, const void *ke2);
  10.         // 销毁键的函数
  11.         void (*keyDestructor)(void *privdata, void *key);
  12.         // 销毁值的函数
  13.         void (*valDestructor)(void *privdata, void *obj);
  14. } dictType
复制代码
接着看下ht,塔是包含了两个项的数组,数组中的每一项都是dictht哈希表,一般情况,只使用ht[0],ht[1]只是对ht[0]进行rehash时使用,dictht结构如下dict.h/dictht:
  1. typedef struct dictht {
  2.         // 哈希表数组
  3.         dictEntry **table;
  4.         // 哈希表大小
  5.         unsigned long size;
  6.         // 总是等于size - 1,用于计算哈希索引值
  7.         unsigned long sizeMask;
  8.         // 该哈希表已有节点数量
  9.         unsigned long used;
  10. } dictht
复制代码
table属性是数组,数组里每个元素指向dictEntry,dictEntry结构如下dict.h/dictEntry:
  1. typedef struct dictEntry {
  2.         // 兼
  3.         void *key;
  4.         // 值--可以指针/uint64_t整数/int64_t整数
  5.         union {
  6.                 void *val;
  7.                 uint64_tu64;
  8.                 int64_ts64;
  9.         } v;
  10.         // next指针指向另一个哈希表节点的指针,形成链表--hash冲突,形成链表的时候
  11.         // 使用的头插法,因为链表没有指向表尾的指针,redis毕竟性能优先嘛
  12.         // 也是为了性能
  13.         struct dictEntry *next;
  14. } dictEntry
复制代码
rehash之前整个字典结构合起来如下:

知道上面的这些东西之后,我首先会去想怎么把一个键值对放进去这个哈希表中,所以redis会有hash算法来计算索引值:
  1. // 计算hash值,字典被用作数据库底层实现或者hash键底层实现,redis使用的Murmurhash算法来计算键的hash值
  2. hash = dict->type->hashFunction(key);
  3. // 计算索引值,为什么是ht[x]因为ht[0]和ht[1]会换的,后面会说
  4. index = hash & dict->ht[x].sizeMask;
复制代码
rehash

随着业务的变化,键值对太多或者太少,这时肯定会有相应的扩展和收缩的操作,这个操作通过执行rehash(重新散列函数)来完成,主要步骤如下:


  • 为字典的ht[1]分配空间(这个在上面画到过,一开始是0),这个空间的大小会取决于要执行的操作以及ht[0]当前包含的键值对数量,也就是ht[0].used的值
    如果执行的是扩展操作:ht[1]大小是第一个大于等于ht[0].used * 2的2 ^ n(2的n次幂)。
    如果执行的是收缩操作:ht[1]大小是第一个大于等于ht[0].used 的2n。
  • 将保存的ht[0]里的元素rehash到ht[1],rehash就是重新计算hash值和index索引
  • 当ht[0]都迁移到ht[1]以后(ht[0变成了空表]),这时释放掉ht[0],将ht[1]设置成ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash做准备
在这里我一开始就联想到了hashMap,就会去想那什么时候去扩展呢?
redis是根据服务器有没有在执行bgsave或者bgrewriteaof来进行扩展,当正在进行时,并且hash表的load_factor(负载因子)大于等于5会去扩展;
当没有进行时,hash表的load_factor(负载因子)大于等于1会去扩展。
  1. // 负载因子 = 哈希表已保存节点数量 / 哈希表的大小
  2. load_factor = ht[0].used / ht[0].size
复制代码
这里会想到为什么和是否执行bgsave或者bgrewriteaof,他的负载因子不同呢?当然了,redis也是出于避免rehash和他们一同执行,毕竟他们执行时候会去创建子进程,这样可以避免不必要的内存写入,减少内存。
这里当load_factor小于0.1时,会自动进行收缩操作。
这里还有一个问题,既然是rehash,那到底是怎么执行的呢?键值对如果就4、5个,那一会的事情就搞定,如果数量很大,500多万,5亿个呢?一次性rehash完,肯定会导致服务器一段时间停止服务,这估计就完了吧…
所以redis采用的渐进式rehash,什么是渐进式rehash,其实就是分多次进行。具体步骤如下:


  • 为ht[1] 分配空间,让字典同时持有ht[0]和ht[1]两个哈希表
  • 在字典里维护一个索引计数器变量rehashidx,将它的值设为0,表示rehash工作正式开始
  • 在rehash期间,每次对字典进行curd操作时,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],rehash完成之后,程序将其rehashidx值+1
  • 随着程序的执行,最终ht[0]上的键值对全部rehash到ht[1],将rehashidx设置为-1,rehash结束。
当然在字典同时持有ht[0]和ht[1]的时候,并且在rehash期间,ht[0]不在进行任何添加操作,都会添加到ht[1],这时候你在添加到ht[0]那真是没意义,因为这样可以保证ht[0]只会减少不会增加,随着rehash最后变为空表。当查找一个键的时候,程序会先在ht[0]查找,若没有才会去ht[1]查找。
上面是我对这两个的理解,若有不对欢迎指出评论,顺便给个赞,年后马上金三银四,祝福大家跳槽愉快,薪资翻倍,下一篇跳表、整数集合、压缩列表一起整了,加油吧年轻人!


来源:https://blog.caogenba.net/SSDNSJT/article/details/122413566
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作