跳到主要内容

整数集合实现原理

整数集合（IntSet）是 Redis 中用于存储整数的数据结构。它具有以下特点：

  1. 节省内存：整数集合采用了紧凑的存储方式，能够有效地节省内存空间。它会根据存储的整数范围自动选择合适的编码方式，例如，如果存储的整数都在较小的范围内，就会使用更紧凑的编码方式。
  2. 支持快速查找：整数集合在查找元素时具有较高的效率，可以快速判断一个整数是否存在于集合中。
  3. 自动升级：当需要添加的整数超出了当前编码方式所能表示的范围时，整数集合会自动升级编码方式，以容纳更大范围的整数。
  4. 不允许重复元素：整数集合中不允许存在重复的元素。

源码对应文件：

  • intset.c
  • intset.h

源码及原理​

数据结构​

typedef struct intset {
    uint32_t encoding; // 编码
    uint32_t length; // 长度
    int8_t contents[]; // 内容
} intset;
  1. uint32_t encoding：表示整数集合的编码方式。不同的编码方式决定了contents数组中存储整数的方式和范围。
  2. uint32_t length：表示整数集合中元素的数量。
  3. int8_t contents[]：这是一个可变长度的数组，用于存储整数集合的实际内容。

升级操作​

源码：

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) { // 升级intset到更大的编码并插入给定的整数
    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; // 返回更新后的intset
}

当把一个元素插入到整数集合时，如果这个元素比所有元素都长，那么就要进行升级，升级后每个元素大小为新的元素大小。

升级不会分配新数组，就在原来数组进行扩展，需要先扩容原来的数组。

img

使用整数升级机制的好处就是节省空间。

比如原来都是int16大小，那么就用不到int64，直到有int64来

不支持降级​

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

参考资料​

小林Coding 整数集合

0%