整数集合是 Redis 集合键的底层实现之一。当一个集合只包含整数值元素,并且元素数量不多时,Redis 就会使用整数集合作为集合键的底层实现。
整数集合是 Redis 用于保存整数值的集合抽象数据结构。它可以保存类型为 int16_t、int32_t、int64_t 的整数值,并且保证集合中不会出现重复元素。
每个 intset.h/intset
结构表示一个整数集合:
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
contents 数组是整数集合的底层实现:整数集合的每个元素都是 contents 数组的一个数组项,各个项在数组中按值的大小从小到大有序排列,并且数组中不包含重复项。
length 属性记录了整数集合记录的元素数量,也就是 contents 数组的长度。
虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组,但实际上 contents 数组并不保存任何 int8_t 类型的值,contents 数组的真正类型取决于 encoding 属性的值,比如:如果 encoding 属性的值为 INTSET_ENC_INT16,那么 contents 就是一个 int16_t 类型的数组,数组里的每个项都是一个 int16_t 类型的整数值,取值范围为:[-32768-32767](2^(16-1))。
与之类似,encoding 的值为 INTSET_ENC_INT32,那么数组每项的取值范围为:[-2147483648, 2147483647](2^(32-1)。
这里也引发了一个问题,当我们对一个 encoding 为 INTSET_ENC_INT8 的 intset,插入 129 时(int8_t 的取值范围是 [-128, 127]),会出现什么?
这也就引发了 intset 的升级操作。与之对应,也有降级操作。接下来,我们来详细认识下 intset 的升降级操作。
每当我们要将一个新元素添加到整数集合时,如果新元素的类型比整数集合的 encoding 类型大,整数集合就需要先进行升级操作(upgrade),然后才能将新元素添加到整数集合中。
整个升级操作源码如下:
// intset.c/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);
int prepend = value < 0 ? 1 : 0;
/* First set new encoding and resize */
is->encoding = intrev32ifbe(newenc);
is = intsetResize(is,intrev32ifbe(is->length)+1);
/* Upgrade back-to-front so we don't overwrite values.
* Note that the "prepend" variable is used to make sure we have an empty
* space at either the beginning or the end of the intset. */
while(length--)
_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
/* Set the value at the beginning or the end. */
if (prepend)
_intsetSet(is,0,value);
else
_intsetSet(is,intrev32ifbe(is->length),value);
is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
return is;
}
升级整数集合并添加新元素,共分为三步进行:
此外,一旦因插入新元素引发升级操作,就说明新插入的元素比集合中现有的所有元素的长度大,所以这个新元素的值要么大于所有现有元素(正值),要么就小于所有现有元素(负值),那么:
整数集合的升级策略主要有以下两个好处:
因为 C 语言是静态类型语言,为了避免类型错误,我们通常不会将两种不同类型的值放在同一个数据结构中。
但是,因为有了升级操作,整数集合可以通过它来自适应新元素,所以我们可以随意地将 int16_t、int32_t、和 int64_t 类型的整数添加到集合中,而不必担心出现类型错误,大大的提升了整数集合的灵活性。
当然,要让一个数组可以同时保存 int16_t、int32_t、和 int64_t 类型的整数值,我们可以粗暴的直接使用 int64_t 类型的数组作为整数集合的底层实现,来保存不同类型的值。但是,这样一来,即使添加到集合中的都是 int16_t、int32_t 类型的值,数组也都是需要使用 int64_t 类型的空间去保存,出现浪费内存的情况。
而整数集合的升级操作,既能同时保存三种不同类型的值,又可以确保升级操作只会在有需要的时候进行,达到节省内存的目的。
Redis 中的集合实现了交、并、差等操作,相关操作可参加 t_set.c
,其中
sinterGenericCommand()
实现交集,sunionDiffGenericCommand()
实现并集和差集。
它们都能同时对多个集合进行元素。当对多个集合进行差集运算时,会先计算出第一个和第二个集合的差值,然后再与第三个集合做差集,依次类推。
接下来,我们一起来认识下三个操作的实现思路。
计算交集的过程大概可以分为三部分:
需要注意的是,上述第 3 步在集合中进行查找,对于 intset 和 dict 的存储来说时间复杂度分别是 O(log n) 和 O(1)。但由于只有小集合才使用 intset,所以可以粗略地认为 intset 的查找也是常数时间复杂度的。
并集操作最简单,只要遍历所有集合,将每一个元素都添加到最后的结果集中即可。向集合中添加元素会自动去重,所以插入的时候无需检测元素是否已存在。
计算差集有两种可能的算法,它们的时间复杂度有所区别。
第一种算法
对第一个集合进行遍历,对于它的每一个元素,依次在后面的所有集合中进行查找。只有在所有集合中都找不到的元素,才加入到最后的结果集合中。
这种算法的时间复杂度为O(N*M),其中N是第一个集合的元素个数,M是集合数目。
第二种算法
在计算差集的开始部分,会先分别估算一下两种算法预期的时间复杂度,然后选择复杂度低的算法来进行运算。还有两点需要注意: