Skip to content

Latest commit

 

History

History
90 lines (59 loc) · 5.69 KB

intset.md

File metadata and controls

90 lines (59 loc) · 5.69 KB

整数集合（intset）

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

Struct定义

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

contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量，也即是contents数组的长度。

虽然intset结构将contents属性声明为int8_t类型的数组， 但实际上contents数组并不保存任何int8_t类型的值 —— contents数组的真正类型取决于encoding属性的值。encoding值见：https://github.com/antirez/redis/blob/3.2.0/src/intset.c#L39

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))  // -32768~32767
#define INTSET_ENC_INT32 (sizeof(int32_t))  // -2147483648~2147483647
#define INTSET_ENC_INT64 (sizeof(int64_t))

intset的编码是由最大的一个数决定的，如果有一个数是int64，那么整个inset的编码都是int64。

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
  2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
  3. 将新元素添加到底层数组里面。

升级之后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大，所以这个新元素的值要么就大于所有现有元素（正数），要么就小于所有现有元素（负数）：

  • 在新元素小于所有现有元素的情况下， 新元素会被放置在底层数组的最开头（索引 0 ）；
  • 在新元素大于所有现有元素的情况下， 新元素会被放置在底层数组的最末尾（索引 length-1 ）。

升级的好处

整数集合的升级策略有两个好处，一个是提升整数集合的灵活性，另一个是尽可能地节约内存。

提升灵活性

因为C语言是静态类型语言，为了避免类型错误，我们通常不���将两种不同类型的值放在同一个数据结构里面。

比如说，我们一般只使用int16_t类型的数组来保存int16_t类型的值，只使用int32_t类型的数组来保存int32_t类型的值，诸如此类。

但是，因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将int16_t、int32_t或者int64_t类型的整数添加到集合中，而不必担心出现类型错误，这种做法非常灵活。

节约内存

当然，要让一个数组可以同时保存int16_t、int32_t、int64_t三种类型的值，最简单的做法就是直接使用int64_t类型的数组作为整数集合的底层实现。不过这样一来，即使添加到整数集合里面的都是int16_t类型或者int32_t类型的值，数组都需要使用int64_t类型的空间去保存它们，从而出现浪费内存的情况。

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

比如说，如果我们一直只向整数集合添加int16_t类型的值，那么整数集合的底层实现就会一直是int16_t类型的数组，只有在我们要将int32_t类型或者int64_t类型的值添加到集合时，程序才会对数组进行升级。

降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

主要API

函数 作用 时间复杂度
intset *intsetNew(void) 创建一个新的整数集合 O(1)
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) 将给定元素添加到整数集合里面 O(N)
intset *intsetRemove(intset *is, int64_t value, int *success) 从整数集合中移除给定元素 O(N)
uint8_t intsetFind(intset *is, int64_t value) 检查给定值是否存在于集合 因为底层数组有序，查找可以通过二分查找法来进行， 所以复杂度为 O(log N)
int64_t intsetRandom(intset *is) 从整数集合中随机返回一个元素 O(1)
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value) 取出底层数组在给定索引上的元素 O(1)
uint32_t intsetLen(intset *is) 返回整数集合包含的元素个数 O(1)
size_t intsetBlobLen(intset *is) 返回整数集合占用的内存字节数 O(1)

总结

  1. 整数集合是集合键的底层实现之一。
  2. 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
  3. 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
  4. 整数集合只支持升级操作，不支持降级操作。