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的内存管理函数，我打算后面单独拿出来说一下。