写点什么

Redis(四):整数集合

作者:Java高工P7
  • 2021 年 11 月 11 日
  • 本文字数:1555 字

    阅读完需:约 5 分钟

每个 intset.h/intset 结构表示一个整数集合(是整个 set 集合)


typedef struct intset{


//编码方式


uint32_t encoding;


//集合包含的元素数量


uint32_t length;


//保存元素的数组


int8_t contents[];


}intset;


  1. contents 数组是整数集合的底层实现,存储的就是集合里面的元素,而且是按从小到大有序地排列,并且数组中是不包含任何重复项的。

  2. length 属性记录了整数集合包含的元素数量,即 contents 数组的长度


注意


contents 属性声明为 int8_t(8 位),但实际上 contents 数组可能并不保存任何 int8_t 类型的值,contents 数组的真正类型取决于 encoding 属性的值。


  • 如果 encoding 属性的值为 INTSET_ENC_INT16,那么 contents 就是一个 int16_t 类型的数组,里面的元素都是一个 16 位数组( ? 2 15 ? 2 15 -2^{15}~2^{15} ?215?215)

  • 同理,如果为 INTSET_ENC_INT32 和 INTSET_ENC_INT64,就对应为 32 位和 64 位

  • 整个数组的字节大小,要通过 length 属性和 encoding 属性来计算,比如 length 值为 5,encoding 值为 int16_t,那么总的字节大小为 5*16=80。


下面看一种特殊情况



这是一个 encoding 属性为 INTSET_ENC_INT64 的,所以数组是储存 64 位的元素的数组,但里面除了第一个元素外,其他都不需要这么大的位数,不过根据整数集合的升级规则,当向一个底层位 int16_t 数组的整数集合中添加一个 int64_t 类型的整数值时,整数集合已有的所有元素都会被转换成 int64_t 类型。

升级

当我们要将一个新元素添加到底层数组时,会先比较新元素的位数是否满足,如果新元素的类型比整数集合现有所有的元素都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面。


升级步骤总共有 3 个步骤


  • 根据新元素的类型,将整数集合的底层数组进行扩展,并为新元素分配空间

  • 将整数集合的底层数组里面的所有元素类型都变为新类型,并将类型转换后的元素放置到正确的位上(要按从小到大的顺序),而且在放置过程中,要维持有序性

  • 将新元素添加到底层数组里(也要维持有序性),一般这个放在最后,因为新元素是高位,所以都会比原有的低位元素要大


举个栗子来表示一下



比如这个集合里面有 3 个元素,是一个 int16_t 的数组,现在要添加一个 2 31 2^{31} 231 的数据,因为这个是一个 31 位的数据,所以要对数据进行升级


首先第一步,根据新类型,对底层数组进行扩展,并为新元素分配空间,即为数组进行空间重分配,这里插入的是 31 位数据,然后分配后的空间为 32 ? ( l e n g t h + 1 ) = 32 ? 4 = 127 32*(length+1)=32*4=127 32?(length+1)=32?4=127,重新分配后的数组如下



此时,改变旧元素的类型,变成 32 位,旧元素有 3 个,即是 32*3=96 位(此时不管后面的新分配空间),此时一个索引位置所占的空间大小也要从 16 变成 32 位,然后进行对旧数据转移,比如旧数据 3 排第三位,应该放在索引 2 的位置上,也就是 64~95 位处



同理旧元素 2 的索引位置为 1,在 32 位~63 位的空间内,旧元素 1 的索引位置为 0,在 0 ~ 31 位上


完成这些后,才会对新插入的数据进行空间分配,分配到 96~127 位处



【一线大厂Java面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


最后,程序将整数集合的 encoding 属性从 INTSET_ENC_INT16 改为 INTSET_ENC_LNT32,并将 length 属性的值从 3 改为 4,至此,升级完成。

关于时间复杂度

是要遍历整数集合将元素进行升级,所以向集合中添加元素的时间复杂度为 O ( N ) O(N) O(N)。

关于元素摆放位置

引发升级的元素都是比所有元素长度大的,因为高位,所以要就大于所有元素,要么小于所有元素(针对插入的是负数情况),所以就分为下面两种情况进行


  • 在新元素小于所有元素的情况下,新元素会被放置在底层数组的最开头处(索引 0)

  • 在新元素大于所有现有元素的情况下,新元素会被放置在底层数组的最末尾处,索引值为 length-1

升级的好处

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

用户头像

Java高工P7

关注

还未添加个人签名 2021.11.08 加入

还未添加个人简介

评论

发布
暂无评论
Redis(四):整数集合