redis源码之整数集合intset

未完待续…

整数集合intset

1.简介：

连续，无序的数据结构。整数集合（ intset ）是Redis 用于保存整数值的集合抽象数据结构，它可以保存类型为intl6_t 、int32_t 或者int64_t 的整数值，并且保证集合中不会出现重复元素。

2.intset定义

typedef struct intset {

    uint32_t encoding;// 编码方式

    uint32_t length;// 集合包含的元素数量

    int8_t contents[];// 保存元素的数组,值：小->大 并且 无重复

} intset;

注意：
（1）虽然intset 结构将contents 属性声明为int8_ t 类型的数组，但实际上contents 数组并不保存任何int8_t 类型的值， contents 数组的真正类型取决于encoding 属性的值。
（2）contents[ ]中保存的数值必须是同一类型的，并且通过encoding表示出来。
例如：[2675256175807981027 ,1 , 3 , 5 ]
只有 -2675256175807981027 是真正需要用 int64_t 类型来保存的， 而其他的 1 , 3 , 5 三个值都可以用 int16 _t 类型来保存，不过根据整数集合的升级规则， 当向一个底层为 int16_t 数组的整数集合添加一个 int64_t 类型的整数值时， 整数集合已有的所有元素都会被转换成 int64_t 类型， 所以 contents 数组保存的四个整数值都是 int64_t 类型的。

3.升级：提升灵活性节约内存

以上面两个图为例：
（1）根据新元素的类型， 扩展整数集合底层数组的空间大小， 并为新元素分配空间；
初始为16* 3 bit => 32* 4bit=128bit
（2）将底层数组现有的所有元素都转换成与新元素相同的类型， 并将类型转换后的元素放置到正确的位上， 而且在放置元素的过程中， 需要继续维持底层数组的有序性质不变。
1,2,3为16bit，先把他们从右到左转化为32bit同时放在新内存的相应位置
（3）将新元素添加到底层数组里面。
把65535放在最后位置上
（4）最后， 程序将整数集合 encoding 属性的值从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32 ， 并将 length 属性的值从 3 改为 4
需要注意的是整数集合不支持降级操作！！！！！

4.升级的好处

（1）提升灵活性：
相比于C语言，整数集合可以通过自动升级底层数组来适应新元素．所以我们可以随意地将int16_t 、int32_t 或者int64_t 类型的整数添加到集合中，而不必担心出现类型错误。
（2）节约内存：
例如，如果我们一直只向整数集合添加intl6-t 类型的值，那么整数集合的底层实现
就会一直是int16_t 类型的数组，只有在我们要将int32_t 类型或者int64_t 类型的
值添加到集合时，程序才会对数组进行升级。

5.小结：
整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型，尽可能地节约了内存。整数集合只支持升级操作， 不支持降级操作。