【Redi设计与实现】第六章：整数集合-图灵课堂

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

文章目录

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显示了一个例子：

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

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 升级

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

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