专栏首页Redis源码学习系列Redis源码学习之整数集合
原创

Redis源码学习之整数集合

​整数集合

整数集合有以下几个特点:

1.局限性:只存储整数类型数据

2.有序性:以从小到大的顺序存储

3.唯一性:存储的数据不会重复

整数集合在Redis中是集合对象的底层存储之一,当一个集合对象的元素都是整数类型且元素数量不多(不超过512个)时,就会使用整数集合。

整数集合在Redis中的实现

1.数据结构

整数集合结构体有3个属性:

  1. encoding:代表整数集合的编码类型,可以存储int16、int32和int64三种类型的数据
  2. length:整数集合中的元素个数
  3. contents:整数集合中的元素数组,以字节数组的形式保存

举个例子,一个长度为3,编码为int16(两个字节)的整数集合如下图所示:

由图可见,整数集合中存了3个编码为int16的元素,分别是-2、255、32767,以从小到大的顺序排列。更底层一些,我们定义contents的时候使用的是字节数组,在小端系统中-2对应的16位为11111110 11111111,即低位字节为254,高位字节为255,同理,255对应的低位字节为255、高位字节为0,32767对应的低位字节位255,高位字节为127,所以最终contents字段为[254,255,255,0,255,127],看到这里你可能已经有所感觉了,其实int16代表的就是双字节对齐的底层存储。那么int32就是四字节对齐,int64是八字节对齐。此外,Redis源码中是会对系统进行大小端判断,我这里为了简化问题,只展示小端系统的情况,大端系统大家有兴趣的话可以尝试画一画。

2.插入元素

对于刚才的整数集合,这时候如果我要插入一个新值:1,这个值明显还在int16编码类型的范围内,所以我们不需要改变编码类型(什么时候需要改变?请往下看),那么我们只需要保证集合的有序性,应该怎么做呢?首先需要明确一点,整数集合实现的是非常紧凑的内存规划,我们目前的整数集合占用的内存空间只有2字节(int16所占空间)乘以3(集合长度)——即6个字节,这时候需要插入一个值,就需要再多分配两个字节的空间给contents字段,达到8个字节的空间,Redis源码中使用realloc函数进行内存的resize,当新申请的内存较大时,会保留原来内存中的数据,以刚才图中的整数集合为例,当申请了2个字节之后,结构如图所示:

最右边的两个字节就是新分配的,前面的6个字节原封不动的保存着。接着,为了有序性,我们需要在-2和255之间插入两个字节表示新值1,要怎么做呢?很简单,只需要将插入位置之后的32767和255底层存储的4个字节向后移动2个字节位置,需要注意的是,这里是从最右边字节开始依次移动,否则会出现字节被覆盖丢失的问题,我用下图中的箭头旁边的序号来表示顺序:

移动之后,我们只需要最后一步,用新值1的两个字节即低位字节1和高位字节0覆盖掉原来该位置上的两个字节即可,最终的contents数组如下图所示:

3.删除元素

有了插入元素的讲解,我相信你已经知道删除元素的实现方式了。是的,反着就行了,找到删除的位置,依次左移元素,最后resize释放掉空间,如下图所示,我们再把刚才插入的1删掉:

这里最后一个字节的删除还是通过realloc函数操作,直接把contents的内存缩小为6个字节即可。

4.查找元素

由于整数集合的有序性,所以查找某个元素是非常容易的,且其底层是以数组形式存储,所以很自然的想到二分,比较简单,流程如下图所示:

5.升级插入

好了,终于到整数集合最关键的操作了。首先,什么叫升级——升级针对的是整数集合的编码类型,比如我们刚才一直举得例子中,编码类型始终是int16,新增的数值也是在int16范围内的,即区间[-32768,32767]。那么,加入我插入一个不在这个范围内,比如32768,如果还用int16存储的话肯定要溢出了,所以就需要对编码类型进行升级操作,判断出32768在int32范围内,需要占用4个字节的空间。但与此同时,整数集合中的另外3个元素仍然是占用2个字节,为了保持整体编码一致,需要对其他元素的存储空间也拓展到4个字节,这就是整数集合的升级了。

这里只给出了插入正数的情况,其实需要升级的时候还有可能是插入负数,比如-32769,也需要升级成int32类型的编码。所以升级的时候,正数肯定是向后插入,而负数是向前插入。负数的插入大家可以自行尝试一下。

6.降级

由于前面提到了升级,所以你可能自然而然就想到了降级,但不好意思,Redis的整数集合并不支持降级操作,换句话说,一旦升级到int64编码类型,即使整数集合最后只保存1,2,3这样的数,也不会再变回到int16了。

总结

整数集合虽然不如其他数据结构操作那么复杂,但里面涉及的基础知识还是很多的(我在读的时候就又重新翻了一遍CSAPP的虚拟存储器),比如字节对齐、大小端、堆分配策略,结合应用再重新复习一遍也是很好的。另外,这一张涉及了很多Redis的内存管理函数,我打算后面单独拿出来说一下。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Redis源码学习之字典

    在字典结构体中,包含了一组字典函数(dictType),通过封装的方法处理对应的操作,通常在字典初始化的时候对其进行配置。

    里奥搬砖
  • Redis源码学习之对象系统

    在前面的文章中,我介绍了Redis的底层数据结构,但Redis对外提供的命令并没有直接使用它们,而是基于它们构建更高级的数据对象,总共包括5中对象类型,分别为【...

    里奥搬砖
  • Redis源码学习之跳表

    跳跃链表简称为跳表(SkipList),它维护了一个多层级的链表,且第i+1层链表中的节点是第i层链表中的节点的子集。跳表作为一种平衡数据结构,经常和平衡树进行...

    里奥搬砖
  • How many integers can you find(容斥原理) - HDU 1796

    看这题之前先复习一下容斥原理,不然肯定看不懂,呃,如果第一次接触容斥原理的题,可能弄懂了容斥原理你还是看不懂代码,是的,等会你就知道了。

    ACM算法日常
  • protocol buffers的编码原理

    protocol buffers使用二进制传输格式传递消息,因此相比于xml,json来说要轻便很多。

    charlieroro
  • 数据类型(基本数据类型和引用数据类型)范围与字符转换,代码示例+个位十位百位相加面试题

  • 你所能用到的BMP格式介绍(二)

    一、可能你忽视的基础         在正式开始之前,我不得不从最基本的地方开始,因为这些地方大多数人会忽视的一干二净,如果不在开始进行说明,那么在后面一定会有...

    一心一怿
  • Python中的bytes

    py3study
  • Mybatis-Plus代码生成器

    乐心湖
  • 蓝牙芯片----BK3431开发笔记------注意事项(1)

    erase的操作是按照sector为单位来操作的,一个sector为4kb(每4k地址增加0x1000),

    心跳包

扫码关注云+社区

领取腾讯云代金券