【Redi设计与实现】第六章：整数集合

集合键的底层实现之一。当集合只包含整数值元素，且集合元素数量较少时，Redis将使用整数集合作为集合键的底层实现。

文章目录

• 6.1 实现整数集合
• 6.2 升级
• 6.3 升级的好处

• 6.3.1 提升灵活性
• 6.3.2 节约内存

• 6.4 降级
• 6.5 API整数集合
• 6.6 重点回顾

6.1 实现整数集合

整数集合（intset）Redis是一种集合抽象数据结构，用于保存整数值，它能保存int16_t、int32_t或int64_t的整数值，并保证集合中不会出现重复元素。

每个intset都表示一个整数集合：

typedef struct intset {// uint32_t encoding;// uint32________t length;// 保存元素的数组int8_t contents[];} intset;

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

length 属性记录 contents 数组中整数的数量。

虽然 intset 结构将 contents 属性声明为int8_t类型数组，但实际上contents数组并不保存任何int8_t类型的值，contents数组的真实类型取决于encoding属性的值：

• 如果encoding属性值为INTSET_ENC_INT16，那么cintents就是一个 int16_t 数组中的每个项目都是一个类型的数组 int16_t 类型的整数值(-32768 ~ 32767）
• 如果encoding属性值为INTSET_ENC_INT32，那么cintents就是一个 int32_t 数组中的每个项目都是一个类型的数组 int32_t 类型的整数值(-2147483648 ~ 2147483647）
• 如果encoding属性值为INTSET_ENC_INT64，那么cintents就是一个 int64_t 数组中的每个项目都是一个类型的数组 int64_t 类型的整数值(-9223720368775808 ~ 9223372036854775807）

简单来说，就是 encoding 是什么类型，数组会保存什么类型。

图6-1显示了一个例子：

• encoding 属性的值为 INTSET_ENC_INT16，表示整数集合 contents 底层实现为 int16_t 数组类型，集合保存 int16_t 类型的整数值。
• length 属性值为5，表示整数集合包含5个元素。
• contents 这一集中的五个元素按从小到大的顺序保存。
• 因为每个集合元素都是int16__t 因此，类型的整数值 contents 数组的大小等于 size(int16_t) * 5 = 80位。

让我们来看看另一个整数集：

intset 每个属性的含义与上述相同。这里有一点区别：

• 我们发现，对 1、3、就5而言，我们只需要使用int16位进行存储，对于-2675256175807981027 我们只需要使用它 存储int64。
• 为什么最后都用？ int64 存储呢？原因是，contents 添加整数集时，会自动升级。
• 比如一开始就是 int16 当我们添加一个位置时，当我们添加一个位置 int32 当位置升级到32位，再加64位时，将再次升级到32位 int64 位。

6.2 升级

每次我们想在整数集合中添加一个新元素，新元素的类型比所有现有元素的类型都要长，整数集合需要升级，然后才能添加到集合中。

升级集合并加分三个步骤：

• 扩大整数集合底层数组的空间大小，并根据新元素的类型为新元素分配空间。
• 将底层数组的所有现有元素转换为与新元素相同的类型，并将转换后的元素放置在正确的位置。在放置元素的过程中，需要保持底层数组的有序性质不变。
• 将新元素添加到底层数组中

例如：假设现在有一个例子： INTSET_ENC_INT16 编码的整数集合包括三个集合 int16_t 类型元素如图所示 6-3 所示：

 

由于每个元素占据16个空间，整数集合底层数组的大小为 3*16 = 图6-4显示了整数集合在这48位置的三个元素。

假设我们应该把类型作为假设 int32_t 65535的整数值添加到整数集合中，因为65535的int32_t比当前整数集合中所有元素的类型都要长，所以在将65535添加到整数集合中之前，程序需要升级整数集合。

升级要做的第一件事就是根据我们新类型的长度重新分配我们数组的空间。

目前整数集合有三个元素，加上新元素65535，整数集合需要分配四个元素的空间，因为每个元素都有三个元素 int32_t 需要占用32个空间，所以空间重新分配后，底层数组的大小是:32*4 = 128位。

虽然我们重新分配了底层数组的空间，但数组的原始三个元素1、2、3仍然是 int16_t 类型，这些元素仍然保存在数组的前48位，因此程序的下一个操作是将这三个元素转换为 int32_t 类型，并将转换后的元素放置在正确的位置，在放置元素的过程中，保持数组的有序性。

首先，因为元素3在1、2、3、在65535四个元素中排名第三，因此它被移动到 contents 在数组的索引2位置，即数组64位至95位的空间，如图6-6所示：

其它值也是如此，可以填充。

因为每次向集合中添加新元素都可能导致升级，每次升级都需要转换数组底部现有元素的类型，所以在集合中添加新元素的时间复杂性是O (N)。

升级编码的其他操作也与上述操作相似。

6.3 升级的好处

整数集合的升级策略有两个优点，一是提高整数集合的灵活性，二是尽可能节省内存。

6.3.1 提升灵活性

因为C语言是静态语言，为了避免类型错误，我们通常不把两种不同类型的值放在同一数据结构中。

例如：我们通常只有 int16_t 保存类型的数组 int16_t 值，类似的。

由于整数集合可以自动升级，所以我们不必担心类型错误，这种做法非常灵活。

6.3.2 节约内存

我们可能会说，直接使用 int64_t 保存三个值的类型是不够的，所以不需要升级整数操作。

如果当前添加的所有整数都是 int16_t 类型，会导致大量的内存被浪费，为了避免这种浪费，我们进行升级操作。

6.4 降级

整数集合不支持降级操作。一旦数组升级，编码将保持升级状态。

6.5 API整数集合

6.6 重点回顾

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组，以有序、无重复的方式保存集合元素。如有必要，程序将根据新添加元素的类型改变数组的类型。
• 升级操作为整数集合带来了操作灵活性，并尽可能节省内存。
• 整数集合只支持升级操作，不支持降级操作。