Redis数据结构之Set结构详解

一、前言：无序、唯一、高效的集合

在 redis 的五大数据类型中，set（集合） 是一个非常独特且强大的存在。它天生具备两个核心特性：

• 元素唯一性：自动去重，确保集合内不存在重复元素。
• 无序性：元素没有固定的顺序（尽管 smembers 返回的顺序是稳定的）。

基于这两个特性，set 被广泛应用于：

• 标签系统（用户兴趣标签、文章分类）
• 共同好友/关注（sinter 交集运算）
• 抽奖池（srandmember 随机抽取）
• 全局去重（如爬虫 url 去重）

但你是否想过，redis 是如何在底层高效地实现“唯一性”和“快速查找”的？答案就藏在它的两种精巧数据结构中。

核心价值：

redis set 的底层会根据数据特征，在 intset（整数集合）和 dict（字典）之间智能切换，以实现内存效率与操作性能的最佳平衡！

本文将带你：

• 拆解 intset 的紧凑内存布局
• 揭秘 dict 如何实现 o(1) 的唯一性校验
• 理解编码转换背后的阈值逻辑

二、set 的双重身份：intset 与 dict

redis set 并非只有一种底层实现，而是拥有两种编码（encoding），由 redisobject 的 encoding 字段决定：

这种设计体现了 redis “因地制宜” 的优化哲学：对简单、规则的数据用最省空间的结构；对复杂、庞大的数据用最高效的结构。

三、编码一：intset - 整数的极致压缩

3.1 诞生背景

当一个 set 中的所有元素都是整数时，使用通用的哈希表（dict）来存储显得有些“大材小用”。因为哈希表需要为每个元素存储一个完整的 dictentry 结构（包含 key, value, next 指针等），内存开销较大。

为了极致节省内存，redis 引入了 intset。

3.2 源码结构

typedef struct intset {
    uint32_t encoding; // 编码方式：intset_enc_int16, intset_enc_int32, intset_enc_int64
    uint32_t length;   // 元素个数
    int8_t contents[]; // 柔性数组，存储实际的整数数据
} intset;

关键特性：

• 内存连续：所有整数紧密排列在 contents 数组中，无任何指针开销。
• 有序存储：内部元素按从小到大排序，为二分查找提供可能。
• 类型升级：encoding 字段决定了每个整数占用的字节数（2/4/8字节）。

3.3 类型升级机制（核心！）

intset 最精妙的设计在于其动态类型升级能力。

• 初始状态：插入第一个整数 5，encoding = intset_enc_int16，每个元素占 2 字节。
• 插入更大整数：当插入一个超出当前 encoding 范围的整数（如 70000，超过了 int16 的最大值 32767）时，intset 会自动将整个集合升级到 intset_enc_int32。

过程：

• 申请一块新的、更大的内存空间。
• 将原有所有元素按新类型（如 int32）重新写入新空间。
• 更新 encoding 和 length 字段。
• 释放旧内存。

注意：这个过程需要 o(n) 的时间复杂度和额外的内存，但只会在必要时发生一次，之后的插入操作又恢复 o(log n)（二分查找+插入）。

3.4 内存优势

假设一个 set 包含 1000 个 int16 范围内的整数：

• intset：8 (header) + 1000 * 2 = 2008 bytes
• dict：每个 dictentry 至少需要 8(key)+8(value)+8(next) = 24字节，加上哈希表本身的桶数组，总内存轻松超过 24000+ bytes。

内存节省高达 90% 以上！

四、编码二：dict - 通用的高性能解决方案

一旦 set 不再满足 intset 的苛刻条件（出现非整数，或整数太多），redis 会立即将其转换为 dict（字典）。

4.1 为什么是 dict？

dict 是 redis 的基石数据结构之一，它是一个哈希表，天然具备以下特性：

• o(1) 平均时间复杂度：用于添加 (sadd)、删除 (srem)、查找 (sismember) 操作。
• 天然去重：哈希表的 key 本身就是唯一的，完美契合 set 的“元素唯一”要求。

4.2 dict 在 set 中的特殊用法

在 set 的场景下，dict 的使用非常巧妙：

• key：存储 set 的元素（字符串或序列化后的整数）。
• value：统一设置为 null 指针。

// 伪代码示意
dict *d = dictcreate(&setdicttype, null);
dictadd(d, "element1", null);
dictadd(d, "element2", null);

✅ 优势：这样既利用了 dict 的高效哈希和唯一性保证，又省去了 value 的内存开销。

4.3 渐进式 rehash

dict 本身也有一套精妙的扩容/缩容机制（渐进式 rehash），确保在数据量巨大时，单次操作的延迟依然很低。这部分内容在此不展开，但它保证了即使 set 包含百万级元素，性能依然稳定。

五、编码转换：阈值与触发条件

redis 通过两个配置项来控制 set 何时从 intset 转换为 hashtable：

设计考量：

• 512 这个阈值：是内存效率和操作性能的平衡点。超过 512 个元素后，intset 的 o(log n) 查找和 o(n) 的插入（因需移动内存）开销开始显现，而 dict 的 o(1) 优势则愈发明显。
• 即时转换：保证了数据模型的一致性。一旦数据不再是“纯整数”，就必须切换到通用模型。

六、动手实验：观察 set 的编码变化

6.1 验证 intset

# 添加纯整数
> sadd myset 1 2 3 100 200
(integer) 5

# 查看编码
> object encoding myset
"intset"

6.2 触发转换：插入非整数

# 插入一个字符串
> sadd myset "hello"
(integer) 1

# 编码已变为 hashtable
> object encoding myset
"hashtable"

6.3 触发转换：超过阈值

# 创建一个脚本，添加513个整数
> for i in {1..513}; do redis-cli sadd big_intset $i; done

# 查看编码（应为 hashtable）
> object encoding big_intset
"hashtable"

七、总结

以上为个人经验，希望能给大家一个参考，也希望大家多多支持代码网。