概述
IntSet 是Redis中set集合的一种实现方式，基于 整数数组 来实现，并且具备长度可变、有序等特征。
结构如下：
// intset 结构体定义 typedef struct intset { uint32_t encoding; // 编码方式，用于表示存储的整数类型 uint32_t length; // intset 中包含的元素个数 int8_t contents[]; // 存储整数的数组 } intset;
其中的 encoding 包含三种模式，表示存储的整数大小不同：
为了方便查找，Redis 会将 intset 中所有的整数按照 升序 依次保存在contents数组中，结构如图：
IntSet升级
假如现在，数组中每个数字都在 int16_t 的范围内，因此采用的编码方式是 INTSET_ENC_INT16，每部分占用的字节大小为：
encoding：4字节
length：4字节
contents：2字节 * 3 = 6字节
我们向该其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动 升级 编码方式到合适的大小。
以当前案例来说流程如下：
- 升级编码为 INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
- 倒序 依次将数组中的元素拷贝到扩容后的正确位置
- 将待添加的元素放入数组末尾
- 最后，将 inset 的 encoding 属性改为 INTSET_ENC_INT32 ，将 length 属性改为4
简易源码
#include <stdio.h> #include <stdlib.h> #include <stdint.h> // intset 结构体定义 typedef struct intset { uint32_t encoding; // 编码方式，用于表示存储的整数类型 uint32_t length; // intset 中包含的元素个数 int8_t contents[]; // 存储整数的数组 } intset; // 创建一个新的 intset intset *intset_new() { intset *is = malloc(sizeof(intset)); if (!is) return NULL; is->encoding = 0; // 初始编码方式为 0 is->length = 0; return is; } // 添加整数到 intset intset *intset_add(intset *is, int64_t value) { // 添加元素的逻辑实现省略 return is; } // 检查整数是否存在于 intset int intset_contains(const intset *is, int64_t value) { // 检查元素是否存在的逻辑实现省略 return 0; } // 删除整数从 intset intset *intset_remove(intset *is, int64_t value) { // 删除元素的逻辑实现省略 return is; } // 打印 intset 中的元素 void intset_print(const intset *is) { printf("Intset Length: %d\n", is->length); printf("Intset Elements: "); for (int i = 0; i < is->length; ++i) { printf("%lld ", (long long)is->contents[i]); } printf("\n"); } int main() { intset *is = intset_new(); if (!is) { printf("Error: Unable to create intset.\n"); return 1; } is = intset_add(is, 5); is = intset_add(is, 10); is = intset_add(is, 15); intset_print(is); // 检查元素是否存在 if (intset_contains(is, 10)) { printf("Element 10 exists in the intset.\n"); } else { printf("Element 10 does not exist in the intset.\n"); } is = intset_remove(is, 10); intset_print(is); free(is); return 0; }
总结
Intset可以看做是特殊的整数数组，具备一些特点：
- Redis会确保Intset中的元素唯一、有序
- 具备类型升级机制，可以节省内存空间
- 底层采用二分查找方式来查询
