Redis数据结构(五) —整数集合

我就是我 2022-01-30 11:37 193阅读 0赞

## 整数集合 ##

整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素, 并且这个集合元素数量不多时, Redis就会使用整数集合作为集合键的底层实现.

### 1.整数集合的实现 ###

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构, 它可以保存类型为int16\_t, int32\_t, int\_64\_t的整数值, 并且保证集合中不会出现重复元素

inset.h/intset结构 :

typedef struct intset {
        
        
        //编码方式
        unit32_t encoding;
        
        //集合包含的元素数量
        uint32_t length;
        
        //保存元素的数组
        int8_t contents[];
    } intset;

contents数组是整数集合的底层实现 : 整数集合的每个元素都是contents数组的一个数组项(item), 各个项在数组中按值的大小从小到大有序地排列, 并且数组中不包含任何重复项

length属性记录了整数集合包含的元素的数量

虽然inset结构将contents属性声明为int8\_t类型数组, 但实际上contents数组并不保存任何int8\_t类型的值, contents数组的真正类型取决于encoding属性的值

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]

图中是一个整数集合实例, encoding属性的值为INTSET\_ENC\_INT16, 表示整数集合的底层实现为int16\_t类型的数组, 而集合保存的都是int16\_t类型的整数值

length属性的值为5, 表示整数集合包含五个元素

contents数组按从小到大的顺序保存着集合中的五个元素

因为每个集合元素都是int16\_t类型的整数值 , 所以contents数组的大小等于sizeof(int16\_t) \*5=80位

但如果向底层为int16\_t数组的整数集合中添加一个int64\_t类型的整数值时, 整数集合已有的所有元素都会被转换成int64\_t类型, 这成为整数集合的升级

### 2.升级 ###

当我们要将一个新元素添加到整数集合里面, 并且新元素的类型比整数集合现有元素的类型都要长时, 整数集合需要先进行升级(upgrade), 然后才能将新元素添加到整数集合里面

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

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

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

另外,关于升级后新元素的摆放位置, 因为引发升级的新元素的长度总是比整数集合现有元素的长度都大, 所以这个元素要么就大于所有现有元素, 要么小于所有现有元素; 若小于所有元素,则新元素放在底层数组的开头处; 若大于所有元素, 则新元素放在底层数组的末尾处.

#### 升级的好处: ####

*  1.提升灵活性 : 因为整数集合可以通过升级底层数组来适应新元素, 所以我们可以随意地将int16\_t, int32\_t或者int64\_t类型的整数添加到集合中, 而不必担心类型错误
 *  2.节约内存 : 整数集合的做法既可以让集合能同时保存三种不同类型的值, 又可以确保升级操作只会在有需要的时候进行, 这可以尽量节省内存

### 3.降级 ###

整数集合不支持降级操作, 一旦对数组进行了升级, 编码就会一直保持升级后的状态.

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dpbnRlcnNoaWk_size_16_color_FFFFFF_t_70]: /images/20220130/6b322809775b455aa4748c81b3f93f2c.png