Redis中整数小集合

来源：动视网责编：小采时间：2020-11-09 08:48:51

Redis中整数小集合

Redis中整数小集合:整数集合（intset）是集合键的底层实现之一：当一个集合只包含整数值元素，并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。127.0.0.1:6379> sadd numbers 1 2 3 4 5 (integer) 5 127.0.0.1:63

推荐度：

点击下载本文 文档为doc格式

导读Redis中整数小集合:整数集合（intset）是集合键的底层实现之一：当一个集合只包含整数值元素，并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。127.0.0.1:6379> sadd numbers 1 2 3 4 5 (integer) 5 127.0.0.1:63

整数集合（intset）是集合键的底层实现之一：当一个集合只包含整数值元素，并且这个集合的元素数量不多时， Redis 就会使用整数集合作为集合键的底层实现。

127.0.0.1:6379> sadd numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"

这么做的好处是当集合中只有少量的整数元素的时候，采用之前介绍的其他数据结构，比如sds，都会占用比较大的内存，但如果仅保存为整数集合的话，则会更加经济。

整数数组数据结构

整数数组的定义位于intset.h中，具体如下：

typedef struct intset {
 uint32_t encoding; // 编码方式
 uint32_t length; // 保存的元素个数
 int8_t contents[]; // 保存元素的数组
 } 
 intset;

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

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

/* Return the required encoding for the provided value. */
static uint8_t _intsetValueEncoding(int64_t v) { 
 if (v < INT32_MIN || v > INT32_MAX) 
 return INTSET_ENC_INT64; 
 else if (v < INT16_MIN || v > INT16_MAX) 
 return INTSET_ENC_INT32; 
 else
 return INTSET_ENC_INT16;
}

可以看到一共会有三种类型，分别对应int_16, int_32, int_64。

整数数组中所有的元素在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

整数集合操作

创建整数集合

// 初始化空的整数集合intset *intsetNew(void) {
 intset *is = zmalloc(sizeof(intset)); 
 is->encoding = intrev32ifbe(INTSET_ENC_INT16); // 默认创建int_16的编码格式
 is->length = 0; 
 return is;
}

插入一个元素

/* Insert an integer in the intset */intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
 uint8_t valenc = _intsetValueEncoding(value);
 uint32_t pos; 
 if (success) *success = 1; // 如果超出了当前编码格式所能表示的范围，则升级整数集合并添加元素
 if (valenc > intrev32ifbe(is->encoding)) { 
 /* This always succeeds, so we don't need to curry *success. */
 return intsetUpgradeAndAdd(is,value);
 } else { // 如果元素已经存在于集合，success返回0
 // 如果不存在的话， 这个函数会返回元素应该插入的位置pos
 if (intsetSearch(is,value,&pos)) { 
 if (success) *success = 0; 
 return is;
 } // 否则，需要重新调整集合的大小
 is = intsetResize(is,intrev32ifbe(is->length)+1); // 将pos之后的数据全都向后挪动一个位子
 if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
 }

 _intsetSet(is,pos,value); // 添加数据到第pos位
 is->length = intrev32ifbe(intrev32ifbe(is->length)+1); // 调整元素个数
 return is;
}

在插入元素的时候，需要根据新元素的大小来重新确定所采用的编码。如果新元素超出了原有编码的表示范围，就需要调整编码，同时调整集合中所有其他元素的编码格式。调整编码是一个不可逆的过程，就是说只能从小的编码调整到大的编码，只能升级不能降级。

升级过程

升级整数集合并添加新元素调用的是intsetUpgradeAndAdd函数，共分为三步进行：

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。

将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。

将新元素添加到底层数组里面。

/* Upgrades the intset to a larger encoding and inserts the given integer. */static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { // 当前的编码
 uint8_t curenc = intrev32ifbe(is->encoding); // 根据新元素的值获得新的编码
 uint8_t newenc = _intsetValueEncoding(value); 
 int length = intrev32ifbe(is->length); 
 // 由于整数集合是一个有序集合，所以新的这个超出范围的元素，要不插入头部，要不插入尾部
 // 当value大于0的时候，就是插入到尾部，否则插入到头部，用参数prepend来标记
 int prepend = value < 0 ? 1 : 0; 
 
 /* First set new encoding and resize */
 // 重新设置整数集合的编码
 is->encoding = intrev32ifbe(newenc); // 根据新编码调整整数集合的大小
 is = intsetResize(is,intrev32ifbe(is->length)+1); // 从尾部向头部进行升级，这样在挪动其中的元素的时候，不会覆盖原来的值
 while(length--) 
 // 如果新元素是插入到尾部，prepend==0， 所以原来最后的元素是挪动到length位置
 // 如果新元素是插入到头部，prepend==1，所有的元素都要向后挪动一个位置，将头部空出来
 _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc)); 
 
 /* Set the value at the beginning or the end. */
 if (prepend) 
 // 如果prepend==1， 插入到头部
 _intsetSet(is,0,value); 
 else
 // 否则，设置最后一个位置的元素为value
 _intsetSet(is,intrev32ifbe(is->length),value); // 元素个数加1
 is->length = intrev32ifbe(intrev32ifbe(is->length)+1); 
 return is;
}

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。

查找元素

查找的时候，需要先判断要查找的元素是否在当前编码的有效范围内，如果不在当前范围内，可以直接返回。

另外因为整数集合是一个有序集合，可以采用二分查找的办法，

uint8_t intsetFind(intset *is, int64_t value) { // 获得目标值的编码
 uint8_t valenc = _intsetValueEncoding(value); // 只有目标值的编码比当前编码小，才继续执行查找过程
 return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}// 如果找到这个元素，返回1，同时pos表示这个值在整数集合里边的位置
// 如果没有找到这个元素，返回0， 同时pos表示这个值可以插入的位置
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) { 
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
 int64_t cur = -1; 
 
 /* The value can never be found when the set is empty */
 // 如果集合的长度为0， 直接返回0
 if (intrev32ifbe(is->length) == 0) { 
 if (pos) *pos = 0; 
 return 0;
 } else { 
 /* Check for the case where we know we cannot find the value,
 * but do know the insert position. */
 // 如果目标值大于当前最大值，肯定找不到，返回0， 同时待插入的位置pos为length
 if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) { 
 if (pos) *pos = intrev32ifbe(is->length); 
 return 0;
 } else if (value < _intsetGet(is,0)) { 
 // 如果目标址小于当前最小值，返回0， 同时待插入的位置pos为0
 if (pos) *pos = 0; 
 return 0;
 }
 } // 二分查找
 while(max >= min) { // 得到中间位置
 mid = ((unsigned int)min + (unsigned int)max) >> 1; // 得到中间位置的值
 cur = _intsetGet(is,mid); 
 if (value > cur) {
 min = mid+1;
 } else if (value < cur) {
 max = mid-1;
 } else { 
 break;
 }
 } if (value == cur) { 
 if (pos) *pos = mid; 
 return 1;
 } else { 
 if (pos) *pos = min; 
 return 0;
 }
}