← 返回学习路线

SYSTEM

整数集合

Java基础整数集合system
src/content/notes/system/整数集合.md

整数集合

底层结构

整数集合(intset)是用于保存整数值的集合数据结构,是 Redis 集合键的底层实现之一

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

encoding 取值为三种:INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_INT64

整数集合的每个元素都是 contents 数组的一个数组项(item),在数组中按值的大小从小到大有序排列,并且数组中不包含任何重复项。虽然 contents 属性声明为 int8_t 类型,但实际上数组并不保存任何 int8_t 类型的值, 真正类型取决于 encoding 属性

说明:底层存储结构是数组,所以为了保证有序性和不重复性,每次添加一个元素的时间复杂度是 O(N)


类型升级

整数集合添加的新元素的类型比集合现有所有元素的类型都要长时,需要先进行升级(upgrade),升级流程:

  • 根据新元素的类型长度以及集合元素的数量(包括新元素在内),扩展整数集合底层数组的空间大小

  • 将底层数组现有的所有元素都转换成与新元素相同的类型,并将转换后的元素放入正确的位置,放置过程保证数组的有序性

    图示 32 * 4 = 128 位,首先将 3 放入索引 2(64 位 - 95 位),然后将 2 放置索引 1,将 1 放置在索引 0,从后向前依次放置在对应的区间,最后放置 65535 元素到索引 3(96 位- 127 位),修改 length 属性为 4

  • 将新元素添加到底层数组里

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

引发升级的新元素的长度总是比整数集合现有所有元素的长度都大,所以这个新元素的值要么就大于所有现有元素,要么就小于所有现有元素,升级之后新元素的摆放位置:

  • 在新元素小于所有现有元素的情况下,新元素会被放置在底层数组的最开头(索引 0)
  • 在新元素大于所有现有元素的情况下,新元素会被放置在底层数组的最末尾(索引 length-1)

整数集合升级策略的优点:

  • 提升整数集合的灵活性:C 语言是静态类型语言,为了避免类型错误通常不会将两种不同类型的值放在同一个数据结构里面,整数集合可以自动升级底层数组来适应新元素,所以可以随意的添加整数

  • 节约内存:要让数组可以同时保存 int16、int32、int64 三种类型的值,可以直接使用 int64_t 类型的数组作为整数集合的底层实现,但是会造成内存浪费,整数集合可以确保升级操作只会在有需要的时候进行,尽量节省内存

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