02.4 - Set 底层实现

定位: Redis 的无序集合——去重、交并差运算，底层由 intset 和 hashtable 组成 面试高频度: ⭐⭐⭐⭐ 考查方式: intset 升级机制、集合运算优化（SINTER/SUNION/SDIFF）、适用场景

---

一、这是什么？为什么需要它？

是什么

Redis Set 是一个无序的、不可重复的字符串集合，支持交、并、差等集合运算。

为什么需要 Set？

---

二、原理拆解

2.1 编码切换

2.2 Intset（整数集合）结构

2.3 集合运算复杂度

操作	复杂度	说明
SADD / SREM	O(1)	直接哈希操作
SISMEMBER	O(1)	判断元素是否存在
SMEMBERS	O(N)	返回所有元素（注意 N 大小）
SCARD	O(1)	元素个数直接读取
SINTER key1 key2	O(N×M)	对小集合遍历查大集合
SUNION key1 key2	O(N+M)	遍历合并所有元素
SDIFF key1 key2	O(N)	遍历 key1 看不在 key2 中的
SRANDMEMBER	O(1)	随机返回（hashtable 随机遍历）

SINTER 优化策略：

SINTER 不是 O(N²) 暴力双重循环

策略：元素最少集合作外循环、其他集合作哈希查询
  min_set = min(集合1, 集合2, ...)
  result = []
  for elem in min_set:            ← O(N_min) 外循环
      if elem in all other sets:  ← O(1) 哈希查询
          result.append(elem)
  总复杂度：O(N_min × K) = O(N_min) 当 K 固定时

---

三、图解全景

---

四、实战验证

4.1 验证编码切换

redis-cli

# 1. 全部整数 → intset 编码
127.0.0.1:6379> SADD numbers 1 2 3 4 5
(integer) 5
127.0.0.1:6379> OBJECT ENCODING numbers
"intset"

# 2. 插入一个字符串 → 切换到 hashtable
127.0.0.1:6379> SADD numbers "hello"
(integer) 1
127.0.0.1:6379> OBJECT ENCODING numbers
"hashtable"

# 3. 超过阈值 → hashtable
127.0.0.1:6379> EVAL "for i=1,600 do redis.call('SADD',KEYS[1],i) end" 1 bigset
(nil)
127.0.0.1:6379> SCARD bigset
(integer) 600
127.0.0.1:6379> OBJECT ENCODING bigset
"hashtable"

4.2 集合运算实战

# 共同关注（社交场景）
redis-cli

SADD user:1:follow "alice" "bob" "charlie" "dave"
SADD user:2:follow "bob" "charlie" "eve" "frank"

# 共同关注（交集）
127.0.0.1:6379> SINTER user:1:follow user:2:follow
1) "bob"
2) "charlie"

# 我关注但 TA 没关注（差集）
127.0.0.1:6379> SDIFF user:1:follow user:2:follow
1) "alice"
2) "dave"

# 推荐关注（并集）
127.0.0.1:6379> SUNION user:1:follow user:2:follow
1) "alice"
2) "bob"
3) "charlie"
4) "dave"
5) "eve"
6) "frank"

4.3 SINTER 性能测试

# 准备两个大数据集合
for i in $(seq 1 1000); do
  redis-cli SADD setA "element:$i" > /dev/null
  redis-cli SADD setB "element:$((i + 500))" > /dev/null
done

# 测试 SINTER 时间
time redis-cli SINTER setA setB | wc -l
# 500 个交集（id 500-1000）

# 测试 SUNION 时间（较大集合）
time redis-cli SUNION setA setB | wc -l
# 1500 个并集（差 500 个重复）

---

五、面试视角

追问	答案要点
Set 和 List 的区别？	Set 无序不重复、List 有序可重复；Set 有交并差运算，List 没有
intset 的升级机制？	插入更大范围的整数时自动升级编码（int16→int32→int64），只升不降
intset 为什么用二分查找？	intset 内部保持有序数组，二分查找 O(logN)，元素少则足够快
SINTER 的时间复杂度优化？	对元素最少集合遍历，对其他集合 O(1) 哈希查询，总体 O(N_min×K)
SPOP 和 SRANDMEMBER 的区别？	SPOP 随机返回并删除（抽奖消耗券）；SRANDMEMBER 只返回不删除（抽样）
SMEMBERS 的注意事项？	O(N)，集合很大时可能阻塞，推荐用 SSCAN 分批迭代
Set 的交集结果可以存下来吗？	用 SINTERSTORE 存到新 key，避免每次重新计算

📚 相关链接

• **Hash 底层** — Set 的 hashtable 编码与 Hash 共享 dict 结构
• **ZSet 与 SkipList** — 有序集合的底层实现
• ← 返回 **核心数据结构索引**