Redis设计与实现(整数集合)

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

整数集合的实现

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

typedef struct intset {
	//编码方式
	uint32_t encoding;

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

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

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

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

虽然 contents 类型是int8_t的数组，但是这个数组不存储任何int8_t类型的数据，这个数组的类型由 encoding 决定。

encoding 属性值为：INSET_ENC_INT16 ,那么数组中每一个元素都是 int16_t 的类型的整数值（最小值为 -32,768 ，最大值为 32,767 ）。

encoding 属性值为：INSET_ENC_INT32 ,那么数组中每一个元素都是 int32_t 的类型的整数值（最小值为-2,147,483,648 ，最大值为 2,147,483,648 ）。

encoding 属性值为：INSET_ENC_INT64 ,那么数组中每一个元素都是 int64_t 的类型的整数值（最小值为 -9,223,372,036,854,775,807 ，最大值为 9,223,372,036,854,775,807 ）。

以下是一个包含5个int16_t类型整数值的整数集合：

intset_1

其中 contents 数组的大小等于 sizeof(int16_t) * 5 = 80字节。

升级

当我们将一个新元素添加到整数集合中，并且新元素的类型比整数集合现有所有元素的长度的类型都要长时，这时要对整数集合进行升级，然后才把新元素放入集合中。

升级步骤：

根据新元素的类型，扩展整数集合底层空间的大小，并为新元素分配存储空间。
将底层数组现有所有元素类型转换成与新元素相同的类型，并将类型转换之后的元素放置到正确的位置上，在放置元素的过程中，保持底层数组的有序性不变。
最后将新元素放入底层数组中。

空间重分配过程：

现有一个 INTSET_ENC_INT16 编码的整数集合，集合中包含三个元素。

三个元素分别占用的空间是 0-15 16-31 32 -47位。
现在要新增一个 int32_t 的整数值65535，类型变大，因此需要升级，先分配空间 sizeof(int32_t) * 4 = 128 字节，新分配空间 48-127位。
把原有数组从后往前移动位置，即第三个元素从32-47位移至 64-95位，第二个从16-31移至32-63位，第一个从0-15移至0-31位。
最后把新元素放至96-127。
修改 encoding 值为 INTSET_ENC_INT32 并将 length 从 3 改为 4.

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

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

小于现有元素情况下，新元素会被放置在底层数组的最开头(索引 0)。

大于现有元素情况下，新元素被放置在底层数组的最末尾（索引 length - 1）。

升级的优点

两个优点：提升灵活性，尽可能节约内存。

提升灵活性。

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

但是，因为整数集合可以通过升级底层数组来适应新元素，所以我们可以随意的将 int16_t 、int32_t 或者 int64_t 类型的整数值添加到集合中，而不需要担心类型错误。
节约内存。

一个数组中需要放int16_t 、int32_t 或者 int64_t 类型的整数值,最好的就是直接用 int64_t作为数组类型，但是这样的话，就会出现浪费内存的情况。

现在的做法是可以保存不同类型的值，只有在需要的时候进行升级操作，这可以尽量节省内存。

降级

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

假设底层数组中只有一个 int64_t 类型的数据，现在我们把这个数据删除了，集合依然会保持 INTSET_ENC_INT64 的编码，底层数组的类型也还是 int64_t 类型的。

整数集合API

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