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 条评论
登录 后参与评论

相关文章

来自专栏一枝花算不算浪漫

[Java面试二]Java基础知识精华部分.

42490
来自专栏Create Sun

python 3.x 爬虫基础---正则表达式(案例:爬取猫眼信息,写入txt,csv,下载图片)

  正则表达式是对字符串的一种逻辑公式,用事先定义好的一些特定字符、及这些特定字符的组合,组成一个“规则的字符串”,此字符串用来表示对字符串的一种“过滤”逻辑。...

58340
来自专栏用户2442861的专栏

深入 char * ,char ** ,char a[ ] ,char *a[] 内核

http://blog.csdn.net/daiyutage/article/details/8604720

20120
来自专栏余生开发

EditorConfig 的配置

# EditorConfig文件使用INI格式。斜杠(/)作为路径分隔符,#或者;作为注释。路径支持通配符:

25240
来自专栏尚国

PHP反序列化漏洞

这里你可以看到, 我代码里的类定义为: class F, 这个序列化就是 F, 我定义变量名字是filename, 它这里也是 filename, 我们可以修改...

12320
来自专栏Phoenix的Android之旅

动态代理-进阶高级开发必学技能

关于代理模式的话题有很多, 在开发中经常用到的应该是静态代理模式,能很好的去耦合。 动态代理是代理模式的另外一种实现。

9630
来自专栏python3

python3--中一些常见的坑(机制上的问题)

重点:在循环一个列表时,最好不要进行删除的动作(一旦删除,索引会随之改变),容易错误。

8210
来自专栏python3

python3--函数初识

函数能提高应用的模块性,和代码的重复利用率。已经知道python提高了许多内建函数,比如print(),len()等。但你也可以自己创建函数,这被叫做用户自定义...

13710
来自专栏GreenLeaves

C# this关键字(给底层类库扩展成员方法)

本文参考自唔愛吃蘋果的C#原始类型扩展方法—this参数修饰符,并在其基础上做了一些细节上的解释 1、this作为参数关键字的作用 使用this关键字,可以向t...

25270
来自专栏公众号_薛勤的博客

Java多线程编程核心技术(二)对象及变量的并发访问

本文主要介绍Java多线程中的同步,也就是如何在Java语言中写出线程安全的程序,如何在Java语言中解决非线程安全的相关问题。阅读本文应该着重掌握如下技术点:

12730

扫码关注云+社区

领取腾讯云代金券