当前位置: 首页 > news >正文

Redis原理:IntSet

(笔记总结自b站黑马程序员课程)

一、结构

IntSet是Redis中set集合的一种实现方式,基于整数数组来实现,并且具备长度可变、有序等特征。 结构如下:

typedef struct intset {uint32_t encoding; //编码方式uint32_t length; //元素个数int8_t contents[]; //整数数组
} intset;

注意整数数组记录的是每一个数的起始地址,决定数字长度是编码方式。

其中的encoding包含三种模式,表示存储的整数大小不同:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

为了方便查找,Redis会将intset中所有的整数按照升序依次保存在contents数组中,结构如图:

现在,数组中每个数字都在int16_t的范围内,因此采用的编码方式是INTSET_ENC_INT16,每部分占用的字节大小为:

①encoding:4字节(固定)

②length:4字节(固定)

③contents:2字节 * 3 = 6字节  

二、扩展 

我们向该其中添加一个数字:50000,这个数字超出了int16_t的范围,intset会自动升级编码方式到合适的大小。 以当前案例来说流程如下:

  • 升级编码为INTSET_ENC_INT32, 每个整数占4字节,并按照新的编码方式及元素个数扩容数组

  • 倒序依次将数组中的元素拷贝到扩容后的正确位置(倒序可以规避数据覆盖问题)

  • 将待添加的元素放入数组末尾

  • 最后,将inset的encoding属性改为INTSET_ENC_INT32,将length属性改为4

三、源码

源码理解就行,注意插入数据底层用到了二分查找的算法。

插入新数据:

/* Insert an integer in the intset */
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {//获取当前值编码uint8_t valenc = _intsetValueEncoding(value);//要插入的位置uint32_t pos;if (success) *success = 1;/* Upgrade encoding if necessary. If we need to upgrade, we know that* this value should be either appended (if > 0) or prepended (if < 0),* because it lies outside the range of existing values. *///判断编码是否超过当前intset的编码if (valenc > intrev32ifbe(is->encoding)) {//超出编码,需要升级/* This always succeeds, so we don't need to curry *success. */return intsetUpgradeAndAdd(is,value);} else {//在当前intset中查找值与value一样元素的角标pos/* Abort if the value is already present in the set.* This call will populate "pos" with the right position to insert* the value when it cannot be found. */if (intsetSearch(is,value,&pos)) {if (success) *success = 0; //如果找到了,则无需插入,直接结束并返回失败return is;}//数组扩容is = intsetResize(is,intrev32ifbe(is->length)+1);//移动数组中pos之后的元素到pos+1,给新元素腾出空间if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);}//插入新元素_intsetSet(is,pos,value);//重置元素长度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

升级编码方式:

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {//获取当前inset编码uint8_t curenc = intrev32ifbe(is->encoding);//获取新编码uint8_t newenc = _intsetValueEncoding(value);int length = intrev32ifbe(is->length); //获取元素个数//判断新元素是大于0还是小于0,小于0插入队首,大于0插入队尾int prepend = value < 0 ? 1 : 0;//重置编码为新编码/* First set new encoding and resize */is->encoding = intrev32ifbe(newenc);//重置数组大小is = intsetResize(is,intrev32ifbe(is->length)+1);/* Upgrade back-to-front so we don't overwrite values.* Note that the "prepend" variable is used to make sure we have an empty* space at either the beginning or the end of the intset. *///倒序遍历,诸葛搬运元素到新的位置while(length--)_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));/* Set the value at the beginning or the end. *///插入新元素,prepend决定是队首还是队尾if (prepend)_intsetSet(is,0,value);else_intsetSet(is,intrev32ifbe(is->length),value);//修改数组长度is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}

四、总结

Intset可以看做是特殊的整数数组,具备一些特点:

  • Redis会确保Intset中的元素唯一、有序

  • 具备类型升级机制,可以节省内存空间

  • 底层采用二分查找方式来查询

注意:一般适合在数据量不是很多的情况下使用 

相关文章:

Redis原理:IntSet

&#xff08;笔记总结自b站黑马程序员课程&#xff09; 一、结构 IntSet是Redis中set集合的一种实现方式&#xff0c;基于整数数组来实现&#xff0c;并且具备长度可变、有序等特征。 结构如下&#xff1a; typedef struct intset {uint32_t encoding; //编码方式uint32_t l…...

【已解决】Splunk 8.2.X 升级ES 后红色报警

1: 背景: 由于splunk ES 占有很大的computing resource, 所以,Splunk ES 升级到7.1.1 后,有红色的alert. 2: 解决方法: 降低iowait 的 threshold: Investigation The default threshold setting for IOWait is pre-set to a low value and may not be relevant to the …...

香橙派使用外设驱动库wiringOP 配合定时器来驱动舵机

舵机认识和硬件接线 关于舵机也是使用过很多次了&#xff0c;详见&#xff1a; 使用PWM波控制开发SG90-CSDN博客 同时再次回顾香橙派的物理引脚对应&#xff1a; 所以舵机的VCC接 2&#xff0c;GND接 6&#xff0c;PWM接 7&#xff08;此处写的是物理引脚编号&#xff09; Li…...

C++学习笔记--函数重载(2)

文章目录 1.3、Function Templates Handling1.3.1、Template Argument Deduction1.3.2、Template Argument Substitution 1.4、Overload Resolution1.4.1、Candidate functions1.4.2、Viable functions1.4.3、Tiebreakers 1.5、走一遍完整的流程1.6、Name Mangling1.7、总结 1.…...

代码随想录算法训练营Day56 || ● 583. 两个字符串的删除操作 ● 72. 编辑距离

今天接触到了真正的距离&#xff0c;但可以通过增删改操作来逼近。 问题1&#xff1a;583. 两个字符串的删除操作 - 力扣&#xff08;LeetCode&#xff09; 给定两个单词 word1 和 word2 &#xff0c;返回使得 word1 和 word2 相同所需的最小步数。 每步 可以删除任意一个字…...

chrome_elf.dll丢失怎么办?修复chrome_elf.dll文件的方法

Chrome是目前最受欢迎的网络浏览器之一&#xff0c;然而有时用户可能会遇到Chrome_elf.dll丢失的问题。该DLL文件是Chrome浏览器的一个重要组成部分&#xff0c;负责启动和管理程序的各种功能。当Chrome_elf.dll丢失时&#xff0c;用户可能无法正常启动Chrome或执行某些功能。本…...

代码随想录32|738.单调递增的数字,968.监控二叉树,56. 合并区间

738.单调递增的数字 链接地址 class Solution { public:int monotoneIncreasingDigits(int n) {string str to_string(n);int flag str.size();for (int i str.size() - 1; i > 0; i--) {if (str[i] < str[i - 1]) {str[i - 1] - 1;flag i;}}for (int j flag; j <…...

BIO NIO AIO演变

Netty是一个提供异步事件驱动的网络应用框架&#xff0c;用以快速开发高性能、高可靠的网络服务器和客户端程序。Netty简化了网络程序的开发&#xff0c;是很多框架和公司都在使用的技术。 Netty并非横空出世&#xff0c;它是在BIO&#xff0c;NIO&#xff0c;AIO演变中的产物…...

JVM GC垃圾回收

一、GC垃圾回收算法 标记-清除算法 算法分为“标记”和“清除”阶段&#xff1a;标记存活的对象&#xff0c; 统一回收所有未被标记的对象(一般选择这种)&#xff1b;也可以反过来&#xff0c;标记出所有需要回收的对象&#xff0c;在标记完成后统一回收所有被标记的对象 。它…...

【数据结构】队列知识点总结--定义;基本操作;队列的顺序实现;链式存储;双端队列;循环队列

欢迎各位看官^_^ 目录 1.队列的定义 2.队列的基本操作 2.1初始化队列 2.2判断队列是否为空 2.3判断队列是否已满 2.4入队 2.5出队 2.6完整代码 3.队列的顺序实现 4.队列的链式存储 5.双端队列 6.循环队列 1.队列的定义 队列&#xff08;Queue&#xff09;是一种先…...

嵌入式学习之链表

对于链表&#xff0c;要重点掌握链表和数组区别和实现&#xff0c;链表静态添加和动态遍历&#xff0c;链表中pointpoint-next,链表节点个数的查找&#xff0c;以及链表从指定节点后方插入新节点的知识。...

静态代理和动态代理笔记

总体分为: 1.静态代理: 代理类和被代理类需要实现同一个接口.在代理类中初始化被代理类对象.在代理类的方法中调 用被代理类的方法.可以选择性的在该方法执行前后增加功能或者控制访问 2.动态代理: 在程序执行过程中,实用JDK的反射机制,创建代理对象,并动态的指定要…...

[SM6225][Android13]user版本默认允许root和remount

开发平台基本信息 芯片: 高通SM6225版本: Android 13kernel: msm-5.15 问题描述 刚刚从Framework踏入性能的小殿堂&#xff0c;User版本默认是不会开启root权限的&#xff0c;而且一般调试需要设置一下CPU GPU DDR performance模式或者修改一些schedule util等调核调频节点去…...

pyinstaller打包exe,使用wexpect的问题

参考github首先打包wexpect 1.进入wexpect目录执行 pyinstaller __main__.py -n wexpect 会生成dist文件夹 2.python代码A.py中使用wexpect&#xff0c;注意wexpect.spawn前后必须按照下面添加代码 import sys,os,wexpect #spawn前 real_executable sys.executable try:if sy…...

OpenCV(三十三):计算轮廓面积与轮廓长度

1.介绍轮廓面积与轮廓长度 轮廓面积&#xff08;Contour Area&#xff09;是指轮廓所包围的区域的总面积。通常情况下&#xff0c;轮廓面积的单位是像素的平方。 轮廓长度&#xff08;Contour Length&#xff09;又称周长&#xff08;Perimeter&#xff09;&#xff0c;表示轮廓…...

9.11作业

实现一个对数组求和的函数&#xff0c;数组通过实参传递给函数 sum0 arr(11 22 33 44 55) Sum() {for i in ${arr[*]}do$((sumi))donereturn $sum } Sum ${arr[*]} var$? echo $var写一个函数&#xff0c;输出当前用户的uid和gid&#xff0c;并使用变量接收结果 Sum() {aid -…...

AI伦理与未来社会:探讨人工智能的道德挑战与机会

引言 引出AI伦理和社会影响的主题&#xff0c;强调AI的快速发展和广泛应用。 概述博客的主要内容&#xff1a;探讨AI的伦理挑战以及它对社会的影响。 第一部分&#xff1a;AI的伦理挑战 算法偏见&#xff1a; 解释什么是算法偏见&#xff0c;以及它为何在AI中成为一个重要问题。…...

Android窗口层级(Window Type)分析

前言 Android的窗口Window分为三种类型&#xff1a; 应用Window&#xff0c;比如Activity、Dialog&#xff1b;子Window&#xff0c;比如PopupWindow&#xff1b;系统Window&#xff0c;比如Toast、系统状态栏、导航栏等等。 应用Window的Z-Ordered最低&#xff0c;就是在系…...

微信小程序基础加强总结

本篇文章给大家带来了关于微信小程序的相关问题&#xff0c;其中主要介绍了一些基础内容&#xff0c;包括了自定义组件、样式隔离、数据、方法和属性等等内容&#xff0c;下面一起来看一下&#xff0c;希望对大家有帮助。 1、自定义组件 1.1、创建组件 在项目的根目录中&…...

【JAVA - List】差集removeAll() 四种方法实现与优化

一、场景&#xff1a; 二、结论&#xff1a; 1. 四种方法耗时 三、代码&#xff1a; 一、场景&#xff1a; 求差集 List1 - Lsit2 二、结论&#xff1a; 1. 四种方法耗时 初始条件方法名方法思路耗时 List1.size319418 List2.size284900 List..removeAll(Lsit2)1036987ms…...

打工人必看!电脑突然罢工?阳光电脑维修上门服务救我于水火[特殊字符]

作为每天靠电脑办公的打工人&#xff0c;最崩溃的事情莫过于——电脑突然罢工&#xff0c;而手里还有紧急工作要赶&#xff01;前几天晚上加班&#xff0c;台式机突然黑屏&#xff0c;按开机键没反应&#xff0c;键盘鼠标也没亮&#xff0c;急得我差点哭出来&#xff0c;第二天…...

DownKyi架构深度解析:高效B站视频下载工具的技术实现与实战指南

DownKyi架构深度解析&#xff1a;高效B站视频下载工具的技术实现与实战指南 【免费下载链接】downkyi 哔哩下载姬downkyi&#xff0c;哔哩哔哩网站视频下载工具&#xff0c;支持批量下载&#xff0c;支持8K、HDR、杜比视界&#xff0c;提供工具箱&#xff08;音视频提取、去水印…...

GME-Qwen2-VL-2B效果实测:抽象文字如何匹配具体图片?

GME-Qwen2-VL-2B效果实测&#xff1a;抽象文字如何匹配具体图片&#xff1f; 1. 多模态搜索的突破性体验 想象一下&#xff0c;你脑海中浮现出一句富有哲理的句子&#xff1a;"人生不是裁决书"&#xff0c;却想找一张能表达这种意境的图片。传统搜索引擎会怎么做&a…...

LFM2.5-1.2B-Thinking-GGUF效果展示:同一Prompt下Thinking中间态与终版回答对比图

LFM2.5-1.2B-Thinking-GGUF效果展示&#xff1a;同一Prompt下Thinking中间态与终版回答对比图 1. 模型简介 LFM2.5-1.2B-Thinking-GGUF是Liquid AI推出的轻量级文本生成模型&#xff0c;特别适合在资源有限的环境中快速部署和使用。该模型采用GGUF格式存储&#xff0c;通过ll…...

科研党福音!爱毕业aibye力荐6大AI论文平台,智能改写+降重功能全解析。

工具名称 核心功能 特色优势 Aibiye 论文生成降AI率 全学科覆盖、仿写优化、自动图表生成 Aicheck AI检测文献综述辅助 精准查新、3分钟高效成文 GPT学术版 润色/翻译/代码解释 多模型协同、PDF深度解析 摆平论文 大纲生成降重改写 三步出稿、本硕博通用 QuillB…...

【英飞凌】TC3XX单片机型号解码:从命名规则看芯片选型

1. 英飞凌TC3XX单片机命名规则解析 第一次接触英飞凌TC3XX系列单片机时&#xff0c;我完全被那一长串型号搞懵了。TC387TP、TC377T、TC397QP...这些看似随机的字母数字组合&#xff0c;其实隐藏着丰富的芯片信息。经过几个项目的实战&#xff0c;我终于摸清了这套命名规则的规律…...

s2-pro效果展示:会议纪要转语音+重点语句强调式播报实录

s2-pro效果展示&#xff1a;会议纪要转语音重点语句强调式播报实录 1. 专业语音合成新体验 s2-pro作为Fish Audio开源的专业级语音合成模型镜像&#xff0c;正在重新定义文本转语音的标准。不同于常见的聊天式语音工具&#xff0c;它专注于提供高质量的语音合成服务&#xff…...

AudioLDM-S效果惊艳:科幻飞船、城市夜晚,AI生成的音效有多真实?

AudioLDM-S效果惊艳&#xff1a;科幻飞船、城市夜晚&#xff0c;AI生成的音效有多真实&#xff1f; 想象一下&#xff0c;你正在制作一个科幻短片&#xff0c;需要一个飞船引擎启动时低沉、充满能量的嗡鸣声。或者&#xff0c;你想为一段城市夜景视频配上背景音&#xff0c;需…...

OpenClaw多通道管理:GLM-4.7-Flash同时对接飞书与钉钉的配置技巧

OpenClaw多通道管理&#xff1a;GLM-4.7-Flash同时对接飞书与钉钉的配置技巧 1. 为什么需要多通道管理&#xff1f; 上周我接到一个技术咨询需求&#xff1a;一个小型内容团队需要同时在飞书和钉钉两个平台上接收AI助手服务。他们的编辑用飞书&#xff0c;运营用钉钉&#xf…...

Diagrams:轻量化且多语言支持的Visio替代方案

1. 为什么你需要一个Visio替代方案&#xff1f; 如果你经常需要画流程图、架构图或者UML图&#xff0c;肯定对Microsoft Visio不陌生。作为一款老牌绘图工具&#xff0c;Visio确实功能强大&#xff0c;但它的缺点也同样明显。首先就是价格问题&#xff0c;正版Visio的订阅费用不…...