intset实现

Redis intset（整数集合）实现详解（基于 6.0.10 版本）

intset（整数集合）是 Redis 中 Set 类型的底层实现之一，专门用于存储整数值元素（如 int16_t、int32_t、int64_t）。当 Set 中仅包含整数且元素数量较少时，Redis 会选择 intset 而非哈希表（hashtable），以节省内存空间。

intset 的核心设计目标

内存高效：相比哈希表（需存储键值对和指针），intset 以紧凑数组形式存储整数，无冗余开销。
类型灵活：支持不同长度的整数（16 位、32 位、64 位），并能自动升级编码以容纳更大的整数。
有序性：元素在数组中按升序排列，支持快速查找（二分查找）。

intset 的结构体设计

intset 的结构体定义简洁高效，源码如下：

typedef struct intset {
    uint32_t encoding;  // 编码方式（决定元素的类型和长度）
    uint32_t length;    // 元素数量
    int8_t contents[];  // 柔性数组，存储整数元素（实际类型由 encoding 决定）
} intset;

各字段详解：

encoding：编码方式
用于标识集合中元素的类型（长度），Redis 定义了三种编码：
- INTSET_ENC_INT16：元素为 16 位整数（int16_t），范围 -32768 ~ 32767。
- INTSET_ENC_INT32：元素为 32 位整数（int32_t），范围 -2147483648 ~ 2147483647。
- INTSET_ENC_INT64：元素为 64 位整数（int64_t），范围 -9223372036854775808 ~ 9223372036854775807。
编码决定了 contents 数组中每个元素的占用空间（2 字节、4 字节、8 字节）。
length：元素数量
记录集合中当前存储的整数个数，用于快速获取集合大小（SCARD 命令直接返回此值）。
contents：元素存储数组
柔性数组（不占用结构体固定大小），实际存储整数元素，且始终按升序排列（无重复元素，符合 Set 特性）。
- 数组的实际类型由 encoding 决定（如 encoding=INTSET_ENC_INT32 时，contents 本质是 int32_t[]）。
- 元素有序性为二分查找（O (logN)）提供基础。

intset 的核心特性

自动编码升级

当插入的新元素超出当前编码的范围时，intset 会自动升级编码方式，步骤如下：

计算新元素所需的编码（如当前为 INT16，新元素为 40000，需升级为 INT32）。
重新分配 contents 数组的内存（按新编码的元素大小计算总长度）。
将原有元素按新编码重新存储（从尾部向头部迁移，避免覆盖数据）。
插入新元素（保持升序）。
更新 encoding 为新编码。

示例：

当前编码为 INT16（存储 16 位整数），插入 32768（超出 INT16 上限 32767）。
升级为 INT32，原有元素（如 100、200）转为 32 位整数存储，再插入 32768。

注意：编码只能升级，不能降级（一旦升级为 INT64，即使删除大元素，编码也不会退回）。

元素的查找、插入与删除

（1）查找元素

由于 contents 数组有序，查找通过二分查找实现，时间复杂度 O (logN)：

根据 encoding 确定元素大小（如 2 字节）。
二分查找目标值在数组中的位置。
找到返回索引，未找到返回 -1。

（2）插入元素

检查新元素是否需要触发编码升级（若需要，先执行升级）。
通过二分查找确定插入位置（保持升序）。
若插入位置不在数组末尾，将插入位置后的元素向后移动（避免覆盖）。
插入新元素，length 加 1。

（3）删除元素

通过二分查找定位元素位置。
若存在该元素，将其后面的元素向前移动（覆盖待删除元素）。
length 减 1（无需缩小数组内存，节省操作开销）。

intset 与 Set 类型的关系

Set 类型的底层实现策略：

当 Set 中所有元素都是整数且元素数量 ≤ 512 个（由 set-max-intset-entries 配置）时，使用 intset 存储。
否则，自动转为哈希表（hashtable） 存储（哈希表支持任意类型元素，但内存开销更高）。

配置参数：

1	set-max-intset-entries 512 # 超过此数量，intset 转为哈希表

intset 的优缺点

优点

内存紧凑：无指针和哈希表元数据开销，存储整数比哈希表节省 50% 以上内存。
查找高效：有序数组支持二分查找，小数据量下性能优于哈希表。
自动适配：编码升级机制保证能存储任意大小的整数。

缺点

适用场景有限：仅支持整数元素，且元素数量不宜过多（插入 / 删除需移动元素，O (N) 时间复杂度）。
编码不可逆：升级后无法降级，可能导致内存浪费（如插入一个大整数后删除，编码仍为 INT64）