五、Redis-整数集合

在 Redis 中，当集合只包含整数值元素，并且集合的元素数量不多时，Redis 就会使用整数集合作为集合键的底层实现。

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

整数集合的结构

struct intset{
    //编码方式
    uint32_t encoding;
    
    //集合包含的元素数量
    uint32_t length;
    
    //保存元素的数组(不含重复项)
    int8_t conmtents[];
}

contents数组：整数集合的底层实现，整数集合的每个元素都是 contents 数组的一个数组项，各个项在数组中按值的大小从小到大有序的排列，并且数组中不包含任何重复项
length：contents数组的长度
encoding：contents数组的真正类型（虽然contents数组被声明为 int8_t 类型）

看一个例子

上图为一个编码为 int64_t类的数组，包含四个元素。因为contents数组中每个元素都是 int64_t 类型的，所以数组大小为 64*4 = 256；

上图可知，显然 contents 数组中只有第一个元素需要 int64_t 类型来保存，其他的 1,3,5 都可以使用 int16_t 类型保存。这里就有一个整数集合的升级规则

当向整数集合中添加一个比原有整数集合编码类型大的数据时，整数集合会将已有的元素全部转换成大的编码

升级整数集合并添加新元素的步骤

因为每次升级都需要对底层数组所有的元素进行类型转换，所以向整数集合添加新元素的时间复杂度为O(N)