在 Redis 的五大基本数据类型中，Set（集合）以其无序性、唯一性的特性，在去重、交集、并集等场景中被广泛应用。不同于表面上简单的 “元素集合” 概念，Redis Set 的底层实现并非单一结构，而是根据存储数据的类型和数量，动态选择intset（整数集合） 或 hashtable（哈希表） 两种编码方式，以实现性能与内存的最优平衡。本文将从数据结构定义、核心操作逻辑、编码转换机制三个维度，彻底拆解 Set 的底层实现原理。
一、Set 结构的核心特性与设计思路
在深入底层之前，首先需要明确 Redis Set 的核心特性：
元素唯一性：集合中不存在重复元素，插入重复值时会被自动过滤；
无序性：元素存储不依赖插入顺序，无法通过索引访问（与 List 的有序性形成鲜明对比）；
支持复杂操作：原生提供交集（SINTER）、并集（SUNION）、差集（SDIFF）等集合运算，且性能高效。
Redis 设计 Set 底层结构的核心思路是 “因地制宜”：当存储的元素全为整数且数量较少时，使用内存更紧凑的 intset；当元素包含非整数或数量超过阈值时，自动切换为查询效率更高的 hashtable。这种动态适配机制，既避免了小数据场景下的内存浪费，又保证了大数据场景下的操作性能。
二、intset：紧凑高效的整数集合
intset（整数集合）是 Redis 专门为存储纯整数元素设计的紧凑数据结构，其核心优势是内存占用极小—— 通过连续的内存空间存储整数，且不浪费任何字节（例如根据整数大小自动选择 16 位、32 位或 64 位存储）。
1. intset 的数据结构定义
intset 的底层是一个有序的、无重复的整数数组，其 C 语言定义如下（简化版）：
typedef struct intset {
// 编码方式：决定每个整数的存储字节数
uint32_t encoding;
// 集合中元素的数量
uint32_t length;
// 存储整数的柔性数组（实际占用内存由encoding和length决定）
int8_t contents[];
} intset;其中，encoding 是 intset 的关键属性，它决定了每个整数的存储宽度，支持三种类型：
INTSET_ENC_INT16：每个整数占 2 字节（范围：-32768 ~ 32767）；
INTSET_ENC_INT32：每个整数占 4 字节（范围：-2147483648 ~ 2147483647）；
INTSET_ENC_INT64：每个整数占 8 字节（覆盖所有 64 位整数范围）。
contents 数组是实际存储整数的区域，且数组始终保持升序排列—— 这一特性为后续的 “二分查找” 提供了基础，也是 intset 实现高效查询的核心。
2. intset 的核心操作逻辑
intset 的核心操作包括插入（add）、查询（find）、删除（remove），所有操作都依赖于 “有序数组 + 二分查找” 的组合，时间复杂度均为 O (log n)。
（1）查询操作（find）
由于 contents 数组是有序的，查询某个整数时直接使用二分查找：
根据当前 encoding 确定每个元素的字节数，计算数组的起始和结束位置；
执行二分查找，对比目标值与中间元素的大小；
若找到匹配元素，返回其在数组中的索引；若未找到，返回 - 1。
二分查找的高效性，让 intset 在小数据量场景下的查询性能不逊于 hashtable，同时还能节省内存。
（2）插入操作（add）
插入操作需保证两个核心：不重复和保持有序，步骤如下：
先通过 find 操作判断元素是否已存在，若存在则直接返回；
检查当前 encoding 是否能容纳新元素（例如，当前为 INT16，新元素是 65536 则无法容纳）；
若无法容纳，执行 “编码升级”：将所有现有元素按新编码（如 INT32）重新存储，扩展 contents 数组的内存空间；
通过二分查找确定新元素的插入位置，将插入位置后的所有元素向后移动一个单位（避免覆盖）；
将新元素写入插入位置，更新 length 值。
注意：intset 的编码只支持 “升级”，不支持 “降级”。例如，当插入一个 64 位整数导致编码升级为 INT64 后，即使后续删除该元素，编码也不会回退到 INT32 或 INT16—— 这是为了避免频繁的内存重分配，保证操作效率。
（3）删除操作（remove）
删除操作同样依赖二分查找，步骤如下：
通过 find 操作找到待删除元素的索引，若不存在则直接返回；
将该索引后的所有元素向前移动一个单位，覆盖待删除元素；
更新 length 值（无需缩小内存空间，避免频繁重分配）。
3. intset 的适用场景
intset 仅适用于两个条件同时满足的场景：
集合中的所有元素都是整数（包括正数、负数、零）；
集合元素数量不超过配置阈值（默认通过set-max-intset-entries配置，默认值为 512）。
当任一条件不满足时（例如插入非整数元素，或元素数量超过 512），Redis 会自动将 intset 编码转换为 hashtable。
三、hashtable：通用高效的哈希表
当 Set 存储的元素包含非整数（如字符串），或元素数量超过 intset 的阈值时，Redis 会使用 hashtable 作为底层实现。这里的 hashtable 与 Redis 的 Hash 类型底层使用的字典（dict）结构完全一致—— 本质是一个 “数组 + 链表” 的哈希表，通过链地址法解决哈希冲突。
1. hashtable 的数据结构定义
Redis 的字典（dict）结构是 hashtable 的核心，其 C 语言定义如下（简化版）：
// 哈希表节点：存储键值对（Set中键为元素，值为NULL）
typedef struct dictEntry {
// 键（Set中的元素）
void *key;
// 值（Set中无实际意义，固定为NULL）
union {
void *val;
uint64_t u64;
int64_t s64;
} v;
// 指向下一个哈希节点（解决哈希冲突的链表）
struct dictEntry *next;
} dictEntry;
// 哈希表
typedef struct dictht {
// 哈希表数组（存储dictEntry指针）
dictEntry **table;
// 哈希表数组的大小（必须是2的幂）
unsigned long size;
// 哈希表大小的掩码（size-1），用于计算索引
unsigned long sizemask;
// 哈希表中已存储的节点数量
unsigned long used;
} dictht;
// 字典（管理两个哈希表，用于扩容/缩容）
typedef struct dict {
// 哈希表操作函数（不同类型键的哈希、比较函数）
dictType *type;
// 私有数据（供操作函数使用）
void *privdata;
// 两个哈希表：ht[0]是主表，ht[1]用于扩容/缩容
dictht ht[2];
// 扩容进度标识（rehashidx=-1表示未在扩容）
long rehashidx;
} dict;对于 Set 而言，hashtable 的核心特点是：
键即元素：dictEntry 的 key 存储 Set 中的元素，保证唯一性；
值无意义：dictEntry 的 v 字段固定为 NULL，仅用键的唯一性实现 Set 的去重功能；
哈希表大小为 2 的幂：通过sizemask = size - 1，将哈希值与 sizemask 按位与，快速计算出键在 table 数组中的索引（比取模运算更高效）。
2. hashtable 的核心操作逻辑
hashtable 的操作依赖于 “哈希计算 + 链地址法”，核心操作包括插入（add）、查询（find）、删除（remove），平均时间复杂度为 O (1)（最坏情况 O (n)，但通过合理扩容可避免）。
（1）查询操作（find）
查询某个元素是否存在的步骤：
对元素（key）执行哈希函数，得到哈希值；
用哈希值与sizemask（size-1）按位与，计算出在 table 数组中的索引；
遍历该索引对应的链表（dictEntry 链表），对比每个节点的 key 与目标元素；
若找到匹配的 key，返回该节点；若遍历完链表未找到，返回 NULL。
由于哈希函数的随机性和链表的短长度，查询操作通常能在 O (1) 时间内完成。
（2）插入操作（add）
插入操作需保证键的唯一性，步骤如下：
先通过 find 操作判断元素是否已存在，若存在则直接返回；
检查哈希表的负载因子（used / size），若超过阈值（默认 1），则触发扩容（rehash）；
对新元素执行哈希计算，得到索引；
将新创建的 dictEntry 节点插入到该索引对应的链表头部（头插法，效率更高）；
更新 used 值（已存储节点数量）。
扩容（rehash）机制是 hashtable 性能的关键：
当负载因子 > 1 时，将 ht [1] 的 size 设为 ht [0] size 的 2 倍（保证是 2 的幂）；
逐步将 ht [0] 中的所有节点迁移到 ht [1]（每次操作迁移一个或多个节点，避免阻塞主线程）；
迁移完成后，将 ht [1] 设为新的 ht [0]，清空 ht [1]，重置 rehashidx。
（3）删除操作（remove）
删除操作与查询操作逻辑类似，步骤如下：
通过哈希计算找到元素所在的索引和链表；
遍历链表，找到匹配的 dictEntry 节点；
从链表中移除该节点（调整前驱节点的 next 指针）；
释放节点内存，更新 used 值；
若负载因子 < 0.1（可配置），则触发缩容（逻辑与扩容类似，size 减半）。
3. hashtable 的适用场景
hashtable 是 Set 的 “通用编码”，适用于以下场景：
集合中包含非整数元素（如字符串、浮点数等）；
集合中元素数量超过set-max-intset-entries阈值（默认 512）。
尽管 hashtable 的内存占用比 intset 高（每个元素需额外存储指针和链表节点），但其 O (1) 的平均操作复杂度，使其在大数据量场景下的性能远超 intset。
四、Set 的编码转换机制
Redis Set 的编码转换是单向的、自动触发的，仅支持 “intset → hashtable”，不支持反向转换。转换的触发条件有两个：
1. 插入非整数元素
当向 intset 编码的 Set 中插入非整数元素（如字符串"redis"）时，intset 无法存储非整数，Redis 会立即触发编码转换：
创建一个新的 hashtable；
将 intset 中的所有整数元素逐一迁移到 hashtable 中（键为整数，值为 NULL）；
将新插入的非整数元素也加入 hashtable；
释放原 intset 的内存，将 Set 的编码标记为 hashtable。
2. 元素数量超过阈值
当 intset 中的元素数量超过set-max-intset-entries（默认 512）时，即使所有元素仍为整数，Redis 也会触发编码转换：
原因：intset 的查询、插入、删除时间复杂度为 O (log n)，当 n 超过 512 时，O (log n) 的性能会逐渐落后于 hashtable 的 O (1)；
过程与 “插入非整数元素” 一致，最终将编码转换为 hashtable。
注意：编码转换后，即使后续删除元素导致数量减少到 512 以下，或删除所有非整数元素，Set 的编码也不会回退到 intset。这是因为 Redis 认为 “转换的成本（内存重分配、数据迁移）高于回退带来的内存收益”，避免频繁转换影响性能。
五、总结：两种编码的对比与选型建议
通过前文的分析，我们可以清晰对比 intset 和 hashtable 的差异，并给出 Set 的选型建议：
小数据量纯整数场景：优先使用 intset 编码，例如存储用户 ID 列表（数量 < 512）、商品 ID 集合等，以节省内存；
大数据量或非整数场景：使用 hashtable 编码，例如存储用户标签（含字符串）、日志关键词集合（数量大）等，以保证高性能；
配置优化：若业务中纯整数 Set 的常见规模超过 512，可适当调大set-max-intset-entries（如 1024），延长 intset 的使用周期，减少内存占用。
总之，Redis Set 的底层实现是 “因地制宜” 的典范 —— 通过两种编码的动态适配，在内存效率和操作性能之间找到了最优平衡，这也是 Redis 能在各种场景下保持高性能的重要原因之一。