redis 系列8 数据结构之整数集合
一.概述
整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素，并且这个集合元素数量不多时, redis就会使用整数集合作为集合键的底层实现。下面创建一个只包含5个元素的集合键，并且集合中所有元素都是整数值，那么这个集合键的底层实现就会是整数集合。 接着添加非整数值，集合键的底层实现就会是hashtable。
127.0.0.1:6379> sadd numbers 1 3 5 7 9 (integer) 5 127.0.0.1:6379> object encoding numbers "intset" 127.0.0.1:6379> sadd numbers 'one' (integer) 1 127.0.0.1:6379> object encoding numbers "hashtable"
二. 整数集合实现
整数集合是redis用于保存整数值的集合抽象数据结构，它可以保存类型为int16_t, int32_t, int64_t的整数值，并且保证集合中不会出现重复元素。数据集合定义如下：
// 每个intset.h/intset结构表示一个整数集合
typedef struct intset
{
//编码方式
uint32_t encoding;
//集合包含的元素数量
uint32_t length;
//保存元素的数组
int8_t contents[];
}intset;
(1) contents数组是整数集合的底层实现,整数集合的每个元素都是contents数组的一个数组项(item),各个项在数组中按值从小到大有序排列,并且数组中不包含重复项。如下面脚本：
127.0.0.1:6379> sadd record 5 3 4 5 6 0 (integer) 5 127.0.0.1:6379> smembers record 1) "0" 2) "3" 3) "4" 4) "5" 5) "6"
(2) length属性记录了整数集合包含的元素数量,也即是contents数组的长度。虽然contents属性声明为int8_t类型的数组,但实现上contents数组并不保存任何int8_t类型的值，contents数组的真正类型取决于encoding属性的值。
a. 如果encoding 属性的值为intset_enc_int16，那么contents就是一个int16_t类型的数组，数组里的每个项都是一个int16_t类型的整数值(范围在 -32768 ~ 32767)。如下图encoding属性的值有5个整数型，根据这些整数值得出encoding为int16_t类型。
b. 如果encoding属性的值为intset_enc_int32, 那么数组里每个项就是一个int32_t类型的整数值(范围在 -2147483648 ~ 2147483647)。还有encoding属性的值为intset_enc_int64类型的，数组里每个项取取值范围更大。
需要注意的是：假设contents数组保存的值为2147483647, 1,2,3 四个整数值。 但只有第一个整数值需要用int32_t类型来保存，而其它三个值可以用int16_t类型来保存。不过根据整数集合的升级规则，当一个底层的int16_t数组的整数集合添加一个int64_t类型的整数值时，整数集合中所有元素都会被转换成int64_t类型。 所以contents数组保存的整数值都是int64_t类型的。
三. 升级
当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级,然后才能将新元素添加到整数集合中。假设：集合中包含三个int16_t类型的元素，值分别是1,2,3 。因为每个元素都占用16位空间，所以整数集合底层数组的大小 为3 * 16 =48位。现将int32_t的数值65535添加进去，这里程序需要对整数集合进行升级。
升级整数集合并添加新元素共分三步进行：
(1) 根据新元素的类型，扩展整数集合底层数组的空间大小 ，并为新元素分配空间。分配空间后，现在整数集合4个元素的底层数组大小为4 *32 =128位, 此时前三位还是48位空间，如下图所示：
(2) 将底层数组现有的所有元素都转换成与新元素相同的类型(需要从int16_t 转成int32_t所需的空间) ，转换后元素位置有序不变,如下图所示：
(3) 将新元素添加到底层数组里面,如下图所示：
四. 升级的好处
4.1 提升灵活性
为了避免类型错误，通常不会将两种不同类型的值放在同一个数据结构里面，通过升级处理可以随意地将int16_t, int32_t, , int64_t 类型的整数添加到集合中，而不必担心出现类型错误。
4.2 节约内存
要让一个数组可以同时保存int16_t,int32_t, , int64_t三种类型的值，最简单的做法就是直接使用int64_t类型的数组作为整数集合的底层实现，不过这样浪费内存空间。
五. 降级
整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。即使集合里只有一个需要使用int64_t类型的元素被删除了，整数集合的编码仍然会维持intset_enc_int64, 底层数组也仍然会是int64_t类型,如下图所示：
六. 整数集合api
|
函数 |
作用 |
|
intsetnew |
创建一个新的压缩列表 |
|
intsetadd |
将给定元素添加到整数集合里面 |
|
intsetremove |
从整数集合中移除给定元素 |
|
intsetfind |
检查给定值是否存在于集合 |
|
intsetrandom |
从整数集合中随机返回一个元素 |
|
intsetget |
取出底层数组在给定索引上的元素 |
|
intsetlen |
返回整数集合包含的元素个数 |
|
intsetbloblen |
返回整数集合占用的内存字节数 |