整数集合

1. 整数集合的实现

整数集合是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t、int32_t、int64_t的整数值，并且保证集合中不会出现重复元素。

每个intset.h/intset表示一个整数集合：

typedef struct intset{

    // 编码方式
    uint32_t encoding;

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

    // 保存元素的数组
    int8_t contents[];
}intset;

contents数组是整数集合的底层实现，各个项在数组中按值的大小从小到大有序排列，并且数组中不包含任何重复项。

length记录整数集合包含的元素数量，是contents数组的长度。

contents数组的真正类型取决于encoding的值：

1. 如果encoding值为INTSET_ENC_INT16，那么contents是一个int16_t类型的值，数组中的每个项都是一个int16_t类型的整数值。
2. 如果encoding值为INTSET_ENC_INT32，那么contents是一个int32_t类型的值。
3. 如果encoding值为INTSET_ENC_INT64，那么contents是一个int64_t类型的值。

一个包含5个int16_t类型整数值的整数集合

2. 升级

当将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先升级，然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面。

引发升级的新元素的长度总是比整数集合现有所有元素的长度要大，所以这个新元素的值要么就大于所有现有元素，要么就小于所有现有元素。

3. 升级的好处

整数集合升级策略有两个好处：提升整数集合的灵活性；尽可能地节约内存。

3.1 提升灵活性

C语言是静态类型语言，为了避免类型错误，通常不会将两种不同类型的值放到同一个数据结构里面。

整数集合可以通过自动升级底层数组来适应新元素，所以可以随意将int16_t、int32_t、int64_t类型的值添加到集合中，不必担心出现类型错误，这种做法非常灵活。

3.2 节约内存

最简单的做法是直接使用int64_t类型的数组作为整数集合的底层实现，不过这样一来，即使添加到整数集合里的都是int16_t、int32_t类型的值，数组都需要用int64_t保存，从而浪费内存。

整数集合现在做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只在有需要的时候进行，尽可能节省内存。

4. 降级

整数集合不支持降级操作。

一旦对数组进行了升级，编码就会一直维持在升级后的状态，如，即使将数组中仅有的int32_t的值删掉，剩下全是int16_t值，那么整数集合的编码仍然是INTSET_ENC_INT32。

5. 整数集合API

函数	作用	时间复杂度
intsetNew	创建一个新的压缩列表	O(1)
intsetAdd	将给定元素添加到整数集合里面	O(N)
intsetRemove	从整数集合中移除给定元素	O(N)
intsetFind	检查给定值是否存在于集合	因为底层数组有序，查找可以通过二分查找进行，所以复杂度为O(logN)
intsetRandom	从整数集合中随机返回一个元素	O(1)
intsetGet	取出底层数组在给定索引上的元素	O(1)
intsetLen	返回整数集合包含的元素个数	O(1)
intsetrawLen	返回整数集合占用的内存字节数	O(1)