当前位置: 首页 > 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…...

5个高效实用的英雄联盟工具集使用指南

5个高效实用的英雄联盟工具集使用指南 【免费下载链接】League-Toolkit 兴趣使然的、简单易用的英雄联盟工具集。支持战绩查询、自动秒选等功能。基于 LCU API。 项目地址: https://gitcode.com/gh_mirrors/le/League-Toolkit League-Toolkit是一款基于LCU API开发的开源…...

Windows Defender完全卸载终极指南:彻底移除系统安全组件的完整解决方案

Windows Defender完全卸载终极指南&#xff1a;彻底移除系统安全组件的完整解决方案 【免费下载链接】windows-defender-remover A tool which is uses to remove Windows Defender in Windows 8.x, Windows 10 (every version) and Windows 11. 项目地址: https://gitcode.c…...

ARMv8、AArch64 与 arm64:命名与体系结构要点

ARMv8、AArch64 与 arm64&#xff1a;命名与体系结构要点 ARMv8 指 ARM 架构的一个主版本代际&#xff1b;AArch64 是该代际下的 64 位执行状态与 A64 指令集&#xff1b;arm64 与 aarch64 是操作系统与工具链中对 AArch64 的常用三元组/目录名&#xff0c;二进制约定一致。下…...

别再拍脑袋定权重了!多目标规划中权重和ε值确定的3种科学方法

多目标规划中权重与约束值的科学确定方法&#xff1a;从理论到实践 1. 多目标规划的核心挑战与参数确定的重要性 在现实世界的决策场景中&#xff0c;我们很少遇到仅需优化单一目标的简单问题。无论是产品设计、资源分配还是投资组合管理&#xff0c;决策者往往需要同时考虑多个…...

基于WebSocket与Protobuf协议的抖音直播间实时数据采集方案

基于WebSocket与Protobuf协议的抖音直播间实时数据采集方案 【免费下载链接】DouyinLiveWebFetcher 抖音直播间网页版的弹幕数据抓取&#xff08;2024最新版本&#xff09; 项目地址: https://gitcode.com/gh_mirrors/do/DouyinLiveWebFetcher 技术背景与挑战 在当今直…...

用极空间 NAS 搭专属博客:Typecho 部署全攻略,把创作握在自己手里

前言 作为常年折腾各类私有部署工具的科技爱好者&#xff0c;我一直觉得「真正的创作自由」&#xff0c;藏在自己能掌控的服务器里。试过不少博客程序&#xff0c;要么配置繁琐&#xff0c;要么资源占用高&#xff0c;直到把 Typecho 和极空间 NAS 结合&#xff0c;才找到最舒…...

信创实践:Nacos 2.4.1 与人大金仓 Kingbase 的深度适配与性能调优

1. 为什么需要从MySQL迁移到人大金仓Kingbase&#xff1f; 最近几年&#xff0c;国产数据库的发展速度确实让人惊喜。作为一线开发者&#xff0c;我亲身体验了从MySQL迁移到人大金仓Kingbase的全过程。说实话&#xff0c;刚开始心里也没底&#xff0c;毕竟MySQL用得太顺手了。但…...

FlowState Lab少样本学习效果:仅用10条数据生成特定波动模式

FlowState Lab少样本学习效果&#xff1a;仅用10条数据生成特定波动模式 1. 引言&#xff1a;当数据稀缺遇上智能生成 想象一下这样的场景&#xff1a;你手里只有10条设备振动波形数据&#xff0c;却需要分析上千种可能的故障模式。传统方法可能需要收集数月甚至数年的运行数…...

终极DBeaver多线程查询优先级控制:基于查询类型的动态调整指南

终极DBeaver多线程查询优先级控制&#xff1a;基于查询类型的动态调整指南 【免费下载链接】dbeaver DBeaver 是一个通用的数据库管理工具&#xff0c;支持跨平台使用。* 支持多种数据库类型&#xff0c;如 MySQL、PostgreSQL、MongoDB 等&#xff1b;提供 SQL 编辑、查询、调试…...

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

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