整数集合是Redis集合键的底层实现之一。当一个集合只包含整型值元素，且元素个数不大时，Redis会使用整型集合作为集合键的底层实现。1IntegerSet的实现Integerset是Redis用来存储整数值的集合抽象数据结构。它可以保存int16_t、int32_t、int64_t类型的整数值，并保证集合中不会出现重复的元素。每个intset.h/intset结构代表一个整数集：typedefstructintset{uint32_tencoding;uint32_t长度；int8_tcontents[];}intset;encding:encodinglength:集合包含的元素个数contents[]:元素数组contents数组是整数集合的底层实现：整数集合的每个元素都是一个数组contents数组的item，每一项在数组中按照值的大小从小到大有序排列，数组中不包含重复项。length属性记录了整数集合中记录的元素个数，即contents数组的长度。虽然intset结构将contents属性声明为一个int8_t类型的数组，但实际上contents数组并没有保存任何int8_t类型的值。内容数组的实际类型取决于编码属性的值。例如：如果encoding属性的值为INTSET_ENC_INT16，那么contents就是一个int16_t类型的数组，数组中的每一项都是一个int16_t类型的整数值，取值范围为：[-32768-32767](2^(16-1))。同样，如果encoding的值为INTSET_ENC_INT32，那么数组中每一项的取值范围为：[-2147483648,2147483647](2^(32-1)。这里也引出了一个问题，当我们使用INTSET_ENC_INT8的编码时intset，当插入129时（int8_t的取值范围是[-128,127]），会发生什么情况呢，这也触发了intset的upgrade操作，相应的，还有一个downgrade操作。接下来我们详细了解一下intset的降级降级操作。2升级操作每当我们要向整数集合中添加一个新元素时，如果新元素的类型大于整数集合的编码类型，则需要先升级整数集合，然后才能对新元素进行升级添加到整数集。整个升级操作源代码如下：//intset.c/intsetUpgradeAndAdd()/*将intset升级为更大的编码并插入给定的整数。*/staticintset*intsetUpgradeAndAdd(intset*is,int64_tvalue){uint8_tcurenc=intrev32ifbe(is->encoding);uint8_tnewenc=_intsetValueEncoding(值);intlength=intrev32ifbe(is->length);intprepend=value<0?1:0;/*首先设置新的编码并调整大小*/is->encoding=intrev32ifbe(newenc);is=intsetResize(is,intrev32ifbe(is->length)+1);/*从后向前升级，这样我们就不会覆盖值。*请注意，“prepend”变量用于确保我们在intset的开头或结尾处有一个空*空格。*/while(length--)_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));/*设置开始或结束的值。*/if(prepend)_intsetSet(is,0,value);否则_intsetSet（是，intrev32ifbe（是->长度），价值）;is->length=intrev32ifbe(intrev32ifbe(is->length)+1);returnis;}升级整型集合并添加新元素分为三步：根据新元素的类型扩展底层数组的大小，扩展整型集合底层数组的大小并为新元素分配空间.元素被转换并保持其原始顺序。将底层数组的所有现有元素转换为与新元素相同的类型，并将转换后的元素放在正确的位置，以确保原始顺序不变。向底层数组添加新元素。另外，一旦插入新元素触发升级操作，就意味着新插入的元素大于集合中所有已有元素的长度，所以这个新元素的值要么大于所有已有元素（正值）或小于所有现有元素。已有元素（负值），则：当新元素小于所有已有元素时，新元素将放在底层数组的开头，即索引为0的位置；当新元素大于所有现有元素时，新元素将被放置在底层数组的末尾；3、升级优势整数集的升级策略有以下两个优点：促进了整数集的灵活性；尽可能节省内存；3.1提示灵活性因为C语言是静态类型语言，为了避免类型错误，我们通常不会把两个不同类型的值放在同一个数据结构中。但是，由于升级操作，整数集合可以适应新的元素，所以我们可以随意将int16_t、int32_t、int64_t类型的整数添加到集合中，而不用担心类型错误，这大大提高了整数集合的灵活性。3.2节省内存当然，要让数组同时存储int16_t、int32_t、int64_t类型的整数值，我们可以直接使用int64_t类型的数组作为整数集合存储值的底层实现不同类型的。但是这样一来，即使加入集合的值都是int16_t和int32_t类型的值，数组还是需要使用int64_t类型的空间来保存，造成了内存的浪费。整数集的升级操作不仅可以同时保存三种不同类型的值，还可以保证只在需要的时候才执行升级操作，从而达到节省内存的目的。4交、并、差算法Redis中的集合实现了交、并、差等运算。相关操作可以在t_set.c中找到，其中sinterGenericCommand()实现交集，sunionDiffGenericCommand()实现并集和差集。它们都可以同时对多个集合执行元素。当对多个集合进行减法运算时，会先计算第一个集合和第二个集合的差值，然后计算与第三个集合的差值，以此类推。下面我们来了解下三个操作的实现思路。4.1交集计算交集的过程大致可以分为三个部分：检查每个集合，将不存在的集合视为空集。一旦出现空集，就不需要继续计算了，最后的交集就是空集。按元素数量的降序对每个集合进行排序。这种排序有利于后面计算时从最小的集合开始，需要处理的元素个数少。遍历第一个排好序的集合（也就是最小的集合），对于其中的每一个元素，依次在后面的所有集合中查找。只有在所有集合中都可以找到的元素才会添加到最终结果集中。需要注意的是，上述第3步在set中查找，intset和dict存储的时间复杂度分别为O(logn)和O(1)。但是由于intset只用于小集合，所以可以粗略地认为对intset的查找也是常数时间复杂度。4.2并集并集操作最简单，只要遍历所有集合，将每个元素加入到最终的结果集中即可。向集合中添加元素会自动去重，插入时无需检查元素是否已经存在。4.3差分计算差分有两种可能的算法，它们的时间复杂度不同。第一种算法遍历第一个集合，对于其中的每个元素，依次在所有后续集合中查找。只有在所有集合中都找不到的元素才会添加到最终结果集中。该算法的时间复杂度为O(N*M)，其中N是第一个集合中的元素数，M是集合数。第二种算法将第一个集合的所有元素加入一个中间集合。遍历所有后续集合，对于遇到的每个元素，将其从中间集合中删除。最后，中间集的剩余元素构成差异集。该算法的时间复杂度为O(N)，其中N是所有集合中元素数的总和。在开始计算差分集时，会分别估计两种算法的期望时间复杂度，然后选择复杂度低的算法进行运算。还有两点需要注意：在某种程度上，第一种算法是首选，因为它涉及的操作较少，只做加法，而第二种算法需要先加后删。如果选择第一种算法，那么在算法执行之前，在Redis的实现中，对第二次集合之后的所有集合按照元素个数从多到少进行排序。这种排序有助于以更大的概率找到元素，从而更快地结束搜索。5总结整数集合是集合键的底层实现之一。整数集合以有序、非重复的方式存储集合元素。必要时，底层数组的类型会根据新添加的元素的类型而改变。升级操作提高了操作的灵活性，并尽可能节省了内存。集合可以执行交集、并集和减法运算。
