6、Redis系统-数据结构-05-整数

五、整数集合(Intset)

整数集合是 Redis 中 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素,并且元素数量不大时,就会使用整数集合这个数据结构作为底层实现。整数集合通过紧凑的内存布局和升级机制,实现了高效的整数存储和操作。

1. 结构设计

整数集合本质上是一块连续的内存空间,其结构定义如下:

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

可以看到,保存元素的容器是一个 contents 数组,虽然 contents 被声明为 int8_t 类型的数组,但是实际上 contents 数组并不保存任何 int8_t 类型的元素,contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如:

  • 如果 encoding 属性值为 INTSET_ENC_INT16,那么 contents 就是一个 int16_t 类型的数组,数组中每一个元素的类型都是 int16_t
  • 如果 encoding 属性值为 INTSET_ENC_INT32,那么 contents 就是一个 int32_t 类型的数组,数组中每一个元素的类型都是 int32_t
  • 如果 encoding 属性值为 INTSET_ENC_INT64,那么 contents 就是一个 int64_t 类型的数组,数组中每一个元素的类型都是 int64_t
2. 升级操作

整数集合的一个重要特性是支持升级操作。当将一个新元素加入到整数集合中,如果新元素的类型(例如 int32_t)比集合中现有所有元素的类型(例如 int16_t)都要长时,整数集合需要先进行升级操作。升级操作包括扩展 contents 数组的空间大小和维持集合的有序性。

升级示例

假设一个整数集合包含三个 int16_t 类型的元素:

contents: [1, 2, 3]  // 类型:int16_t

现在,我们将一个新元素 65535 加入到集合中,由于这个新元素需要用 int32_t 类型来保存,因此需要进行升级操作:

  1. 扩展空间:首先需要为 contents 数组扩容,在原本空间的大小之上再扩容多 80 位(4x32 - 3x16 = 80),这样就能保存下 4 个 int32_t 类型的元素。

  2. 转换类型:扩容完 contents 数组空间大小后,需要将之前的三个 int16_t 类型的元素转换为 int32_t 类型,并将转换后的元素放置到正确的位置上,并且需要维持底层数组的有序性不变。

升级后的 contents 数组如下:

contents: [1, 2, 3, 65535]  // 类型:int32_t
升级的好处
  1. 节省内存:如果直接使用 int64_t 类型的数组来保存所有元素,虽然可以保存不同类型的整数,但会造成内存浪费。例如,当元素都是 int16_t 类型时,使用 int64_t 类型数组会浪费大量内存。
  2. 灵活性:通过升级机制,整数集合可以根据需要动态调整数组类型,既能节省内存,又能支持更大范围的整数。
不支持降级

值得注意的是,整数集合不支持降级操作。一旦数组类型升级到更大的整数类型,就不会再降级回较小的类型。这是为了简化实现和避免降级过程中可能产生的复杂性。

3. 操作实现

整数集合支持多种操作,包括插入、删除、查找等。以下是一些常见操作的实现示例:

插入操作

插入新元素时,首先检查新元素的类型是否需要升级。如果需要升级,先进行升级操作,然后将新元素插入到正确的位置,维持数组的有序性。

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)) {
        // 升级操作
        return intsetUpgradeAndAdd(is, value);
    } else {
        if (intsetSearch(is, value, &pos)) {
            if (success) *success = 0;
            return is;
        }
        // 插入操作
        is = intsetResize(is, intrev32ifbe(is->length) + 1);
        if (pos < intrev32ifbe(is->length)) {
            memmove(intsetGet(is, pos + 1), intsetGet(is, pos),
                (intrev32ifbe(is->length) - pos) * intrev32ifbe(is->encoding));
        }
        intsetSet(is, pos, value);
        is->length = intrev32ifbe(intrev32ifbe(is->length) + 1);
    }
    return is;
}
查找操作

查找元素时,通过二分查找算法在有序数组中高效地查找目标元素的位置。

uint8_t intsetSearch(const intset *is, int64_t value, uint32_t *pos) {
    int64_t cur;
    int min = 0, max = intrev32ifbe(is->length) - 1, mid = -1;
    if (intrev32ifbe(is->length) == 0) {
        if (pos) *pos = 0;
        return 0;
    } else {
        while (max >= min) {
            mid = (min + 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;
        }
    }
}
删除操作

删除元素时,首先查找到目标元素的位置,然后移除该元素并调整数组大小。

intset *intsetRemove(intset *is, int64_t value, int *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    uint32_t pos;
    if (success) *success = 0;

    if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is, value, &pos)) {
        uint32_t len = intrev32ifbe(is->length);

        // 移除操作
        if (pos < (len - 1)) {
            memmove(intsetGet(is, pos), intsetGet(is, pos + 1),
                (len - pos - 1) * intrev32ifbe(is->encoding));
        }
        is = intsetResize(is, len - 1);
        is->length = intrev32ifbe(len - 1);
        if (success) *success = 1;
    }
    return is;
}
4. 使用示例

以下是一些使用 Redis 整数集合的示例,展示了如何利用整数集合进行数据的存储和操作。

插入数据

SADD myset 1
SADD myset 2
SADD myset 3

获取数据

SMEMBERS myset
# 1) "1"
# 2) "2"
# 3) "3"

删除数据

SREM myset 2
SMEMBERS myset
# 1) "1"
# 2) "3"
结论

通过上述解析,我们可以更好地理解整数集合的设计思想和实现原理,从而在实际开发中更好地利用整数集合提供的优势。在 Redis 中,整数集合通过紧凑的内存布局和动态升级机制,实现了高效的整数存储和操作。了解这些优化策略,可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。

上一篇:STM32+ESP8266连接阿里云-堆栈大小调整


下一篇:数据结构(3.8)——栈的应用