简策小栈

Appearance

Set（集合） ​

1. 概述 ​

Set是无序字符串集合，元素唯一不重复。

常用命令：SADD、SREM、SMEMBERS、SISMEMBER、SCARD、SUNION、SINTER、SDIFF

2. 底层数据结构 ​

2.1 编码类型 ​

编码说明适用场景
intset整数集合全是整数且元素少
hashtable哈希表大集合或包含非整数

2.2 intset结构 ​

c
typedef struct intset {
    uint32_t encoding;    // 编码：16/32/64位
    uint32_t length;      // 元素数量
    int8_t contents[];    // 柔性数组存储元素
} intset;

特点：

  • 内存连续紧凑
  • 支持16位、32位、64位整数
  • 查找使用二分查找 O(log n)
  • 元素按值从小到大排序

2.3 编码转换条件 ​

c
// 满足任一条件转换为hashtable
set-max-intset-entries 512  // 元素超过512个
// 元素无法用整数表示（超过int64范围）

转换过程：intset → hashtable（不可逆）

3. 面试考点 ​

Q1: Set的底层实现？ ​

答案： Set使用intset（整数集合）或hashtable（哈希表）。当集合所有元素都是整数且元素数≤512时使用intset，否则使用hashtable。intset内存紧凑且有序，hashtable支持O(1)查找但无序。

Q2: Set如何实现交并差运算？ ​

答案： 使用hashtable的特性：

  • SINTER：同时存在于多个集合
  • SUNION：合并所有集合（去重）
  • SDIFF：存在于第一个集合但不在其他集合

这些操作时间复杂度取决于集合大小和元素分布。

Q3: 如何用Set做UV统计？ ​

答案： 使用Set自动去重特性：

bash
SADD uv:2026-04-05 user:1001
SADD uv:2026-04-05 user:1002
SADD uv:2026-04-05 user:1001  # 重复访问不重复计数
SCARD uv:2026-04-05          # UV = 2

注意：UV数据量大会很占内存，生产环境建议使用HyperLogLog。

4. 应用场景 ​

4.1 标签系统 ​

bash
SADD tag:article:1001 技术
SADD tag:article:1001 Redis
SADD tag:article:1001 缓存

# 获取文章的所有标签
SMEMBERS tag:article:1001

# 获取拥有多个标签的文章
SINTER tag:article:1001 tag:article:1002

4.2 好友关系 ​

bash
SADD friends:1001 1002  # 用户1001的好友
SADD friends:1002 1001  # 用户1002的好友

# 共同好友
SINTER friends:1001 friends:1002

# 可能认识的人（好友的好友）
SDIFF friends:1002 friends:1001

4.3 去重计数 ​

bash
# 页面UV统计
SADD page:view:2026-04-05 192.168.1.1
SADD page:view:2026-04-05 192.168.1.2
SCARD page:view:2026-04-05

# 每日签到
SADD checkin:1001:2026-04-05 1
SISMEMBER checkin:1001:2026-04-05 1

5. 实践问题 ​

Q: Set和Hash的区别？ ​

答案：

  • Set：存储值集合，用于去重、交集、并集、差集
  • Hash：存储键值对集合，用于对象、计数器

Q: Set的内存占用？ ​

答案： intset非常紧凑，每元素约4-8字节。hashtable每元素约40-60字节（包含指针和哈希表开销）。大数据量建议使用HyperLogLog。

Q: 如何遍历大Set？ ​

答案： 使用SSCAN命令：

bash
SSCAN cursor MATCH pattern COUNT count
SSCAN 0 MATCH user:* COUNT 100

最后更新: