Set详解

要理解Redis的Set类型，我们需要从核心特性、底层实现、命令原理和应用场景四个维度展开。Set是Redis中最常用的集合类型之一，其设计目标是高效存储无序、唯一的元素，并支持快速的集合操作（如交集、并集、差集）。

一、Set的核心特性

Set是无序（Unordered）、**元素唯一（Unique）**的字符串集合，具备以下关键特征：

无重复性：插入重复元素会被自动忽略（SADD命令返回0）。
无序性：Redis不保证Set中元素的存储顺序（即使底层用有序结构实现，对外也不暴露顺序）。
多元素类型支持：元素可以是整数或字符串（但整数会优先用更紧凑的结构存储）。
高效集合操作：支持SUNION（并集）、SINTER（交集）、SDIFF（差集）等命令，时间复杂度取决于集合大小。

二、Set的底层实现：两种结构的权衡

Redis的Set并非用单一结构实现，而是根据元素类型和数量自动选择更优的底层结构，以平衡内存效率和操作性能。具体来说，Set的底层实现有两种：

intset（整数集合）：用于存储纯整数元素且数量较少的场景（默认阈值：512个元素）。
dict（字典/哈希表）：用于存储非整数元素或数量超过阈值的场景。

1. intset（整数集合）：紧凑的有序数组

intset是Redis为纯整数集合设计的内存优化结构，其本质是有序的整数数组（升序排列），用于快速判断元素是否存在（二分查找）。

（1）intset的结构

intset的内存布局由**头部（Header）和数据区（Contents）**组成：

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

encoding（编码）：表示数组中元素的存储格式，支持三种类型：
- INTSET_ENC_INT16：每个元素占2字节（范围：-32768 ~ 32767）。
- INTSET_ENC_INT32：每个元素占4字节（范围：-2^31 ~ 2^31-1）。
- INTSET_ENC_INT64：每个元素占8字节（范围：-2^63 ~ 2^63-1）。
length：数组中的元素个数（即contents的长度）。
contents：存储整数的柔性数组，按升序排列（便于二分查找）。

（2）intset的操作原理

插入元素（SADD）：
1. 先通过二分查找判断元素是否已存在（O(log n)），存在则直接返回。
2. 若不存在，检查元素的类型是否超过当前encoding（如当前是INT16，插入INT32元素），若超过则升级编码（不可逆）。
3. 升级编码的过程：
  - 扩展contents数组的空间（按新编码计算总字节数）。
  - 将旧数组中的所有元素转换为新编码（如INT16→INT32），并保持升序。
  - 将新元素插入到正确位置（保持数组有序）。
4. 若无需升级，直接扩展数组空间，插入元素并保持有序。
查找元素（SISMEMBER）：通过二分查找判断元素是否存在（O(log n)）。
删除元素（SREM）：二分查找找到元素位置，删除后收缩数组空间（O(n)，因为需要移动后续元素）。

（3）intset的优缺点

优点：内存占用极小（无额外指针或哈希表结构），适合存储小批量整数。
缺点：插入/删除的时间复杂度较高（O(n)，因为需要移动元素），且编码升级不可逆（一旦升级为INT64，无法转回INT32）。

2. dict（字典/哈希表）：通用的高性能结构

当Set中的元素包含非整数或数量超过intset阈值（默认512）时，Redis会自动将intset转换为dict（字典）。dict是Redis中最核心的数据结构之一（Hash类型也用dict实现），其本质是哈希表，用于快速存储和查找键值对。

（1）dict的结构

dict的内存布局由字典结构体和哈希表组成：

typedef struct dict {
    dictType *type;      // 字典类型（用于自定义键值对操作）
    void *privdata;      // 私有数据（如内存分配函数）
    dictht ht[2];        // 两个哈希表（ht[0]存当前数据，ht[1]用于rehash）
    long rehashidx;      // rehash索引（-1表示未在rehash）
    unsigned long iterators; // 迭代器数量（防止rehash时迭代出错）
} dict;

typedef struct dictht {
    dictEntry **table;   // 哈希表数组（每个元素是dictEntry指针）
    unsigned long size;  // 哈希表大小（必须是2的幂）
    unsigned long sizemask; // 掩码（size-1，用于计算哈希索引）
    unsigned long used;  // 已存储的元素个数
} dictht;

typedef struct dictEntry {
    void *key;           // 键（Set中的元素值）
    union {
        void *val;       // 值（Set中无用，设为NULL）
        uint64_t u64;
        int64_t s64;
    } v;
    struct dictEntry *next; // 下一个节点（解决哈希冲突的链表法）
} dictEntry;

ht[2]：两个哈希表，ht[0]存储当前数据，ht[1]用于rehash（哈希表扩展/收缩）。
rehashidx：标记rehash的进度（-1表示未开始，非-1表示当前处理到ht[0]的第几个索引）。
dictEntry：哈希表节点，key存储Set中的元素（唯一），val设为NULL（因为Set不需要值）。

（2）dict的操作原理

插入元素（SADD）：
1. 计算元素的哈希值（通过dictType中的哈希函数）。
2. 用哈希值和ht[0].sizemask计算索引（hash & sizemask）。
3. 遍历该索引对应的链表（dictEntry->next），判断元素是否已存在（O(1)平均，O(n)最坏）。
4. 若不存在，创建新dictEntry，插入到链表头部（O(1)）。
5. 若哈希表的负载因子（used / size）超过阈值（默认1），触发rehash（扩展哈希表大小为原来的2倍）。
查找元素（SISMEMBER）：
1. 计算哈希值和索引。
2. 遍历链表查找元素（O(1)平均）。
删除元素（SREM）：
1. 计算哈希值和索引。
2. 遍历链表找到元素，删除节点并调整链表指针（O(1)平均）。
rehash（哈希表扩展）：当负载因子超过阈值时，Redis会启动渐进式rehash（避免一次性迁移大量数据阻塞主线程）：
1. 初始化ht[1]的大小为大于等于ht[0].used * 2的最小2的幂（如ht[0].used=100，则ht[1].size=128）。
2. 将rehashidx设为0（开始rehash）。
3. 每次处理客户端命令时，迁移ht[0]中rehashidx索引对应的所有元素到ht[1]。
4. 当ht[0]的所有元素迁移完成后，释放ht[0]，将ht[1]改为ht[0]，重置rehashidx为-1。

（3）dict的优缺点

优点：插入/删除/查找的平均时间复杂度为O(1)，适合存储大量元素或非整数元素。
缺点：内存占用比intset大（需要存储哈希表数组、指针和链表结构）。

三、Set的命令与底层映射

Set的常用命令对应底层结构的操作如下：

命令	功能	底层实现（intset）	底层实现（dict）
`SADD key val`	添加元素	二分查找→插入（需升级则升级）	哈希计算→链表插入
`SREM key val`	删除元素	二分查找→删除（移动元素）	哈希计算→链表删除
`SISMEMBER key val`	判断元素是否存在	二分查找（O(log n)）	哈希计算→链表查找（O(1)平均）
`SMEMBERS key`	返回所有元素	遍历数组（O(n)）	遍历所有dictEntry的key（O(n)）
`SCARD key`	返回元素个数	直接返回`length`（O(1)）	直接返回`ht[0].used`（O(1)）
`SUNION key1 key2`	并集	遍历两个intset→合并有序数组	遍历两个dict→合并key（去重）
`SINTER key1 key2`	交集	遍历较小intset→二分查找存在性	遍历较小dict→判断是否在另一个dict中
`SDIFF key1 key2`	差集（key1 - key2）	遍历key1的intset→二分查找不存在性	遍历key1的dict→判断是否不在key2的dict中

四、Set的应用场景

Set的特性使其适合以下场景：

存储唯一标识：如用户的点赞记录（SADD like:article:1001 user:100），避免重复点赞。
标签系统：如用户的兴趣标签（SADD tag:user:100 "sports" "music"），支持快速查询有共同标签的用户（SINTER tag:user:100 tag:user:200）。
好友关系：如用户的好友列表（SADD friend:user:100 user:200 user:300），查询共同好友（SINTER friend:user:100 friend:user:200）。
去重统计：如统计网站的独立访客（SADD uv:2025-07-10 "192.168.1.1"），用SCARD获取独立访客数。

五、总结：Set的设计哲学

Redis的Set通过两种底层结构的动态切换，实现了内存效率和操作性能的平衡：

intset：适合小批量整数集合，内存占用极小，但插入/删除效率较低。
dict：适合大量元素或非整数集合，操作效率高，但内存占用较大。

这种设计使得Set既能高效处理小数据量的整数集合，又能支持大规模的通用集合操作，是Redis中最灵活的集合类型之一。

扩展思考：如果需要有序的集合（如按分数排序），可以使用Redis的Sorted Set（ZSet），其底层用**跳表（Skip List）**实现，支持按分数范围查询和排序。

Set详解 ​

一、Set的核心特性 ​

二、Set的底层实现：两种结构的权衡 ​

1. intset（整数集合）：紧凑的有序数组 ​

（1）intset的结构 ​

（2）intset的操作原理 ​

（3）intset的优缺点 ​

2. dict（字典/哈希表）：通用的高性能结构 ​

（1）dict的结构 ​

（2）dict的操作原理 ​

（3）dict的优缺点 ​

三、Set的命令与底层映射 ​

四、Set的应用场景 ​

五、总结：Set的设计哲学 ​