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