文章目录

前言
redis中的set结构
- 疑问1 ：为什么使用数组后整体时间复杂度还是O(1)
- 疑问2： set特性是无序的那为什么当元素少的时候用连续数组去存储呢？
- 疑问3：当元素少于512的时候即使用intset存储的时候是如何维护唯一性的？
- 疑问4: set底层的hashtable 如何处理hash冲突的对比redis 的Hash类型的处理策略
- 实际看看 intset 和hashtable 的底层存储数据区别
使用例子
- 在线用户统计（去重）
- 相似度计算（用户标签交集）
- 秒杀活动参与者去重
总结

前言

我们已经分析了三种不同数据类型在redis中的使用以及底层的数据结构

Redis常用数据结构以及多并发场景下的使用分析：String类型
Redis常用数据结构以及多并发场景下的使用分析：Hash类型
Redis常用数据结构以及多并发场景下的使用分析：List类型

接下来我们要来分析下 set的基本使用

redis中的set结构

按照惯例首先还是需要搞清楚 redis中的 set 结构是怎样去处理的

Redis 中 Set 类型的两种底层实现方式：intset（整数集合）和 hashtable（哈希表）
查找、插入、删除时间复杂度为O(1)

intset（整数集合）

所有元素都是整数（可以转为 long 类型）；元素个数小于 set-max-intset-entries（默认 512）；

特点：

连续内存：底层是一个连续的数组（有序数组 优势利用上了 内存的局部性 所以是连续内存 ）
查找：使用二分查找（因为数组是有序的）
插入：时保持有序（需要移动数组）

hashtable（哈希表）

元素中存在非整数（如字符串、UUID、中文等）；或者元素数量超过 set-max-intset-entries（默认512）；或者手动添加一个大字符串，也会触发升级。

特点：

哈希表结构：底层是一个 dict；插入查找效率 O(1)：基于哈希函数定位；空间占用较大：因为要维护哈希桶和冲突处理结构；支持任意类型元素（比如 "abc", "hello", "uuid"）；

看完基本介绍不知道你是否有以下的疑问？

疑问1 ：为什么使用数组后整体时间复杂度还是O(1)

前面说了intset是一个内存连续并且内部integer 连续的数组采用二分查找我们都只带二分查找时间复杂度是O(logn)而不是O(1) 为什么还是O(1)呢？

解答：

那就是因为集合较小（只有512个元素），在实践中表现为“常数时间”—— 所以平均复杂度可认为是 O(1)。

疑问2： set特性是无序的那为什么当元素少的时候用连续数组去存储呢？

解答：

高效性 + 空间紧凑性。

内存连续性为了利用上 CPU Cache 缓存的机制尽管查找用的是二分查找 O(log n)，但数据小、内存局部性好，速度非常快

疑问3：当元素少于512的时候即使用intset存储的时候是如何维护唯一性的？

解答：

先二分查找，发现已经存在元素就不插入

疑问4: set底层的hashtable 如何处理hash冲突的对比redis 的Hash类型的处理策略

Set 类型：

Set 的底层是 dict，插入元素之前 Redis 会先判断：

当前 key 是否已经存在于某个 hash 桶的链表中（即元素是否存在）

插入逻辑如下：

if (dictFind(set, value) == NULL) {dictAdd(set, value); // 插入
}

如果哈希冲突，但值不相等（链表中找不到值），会继续插入；

如果值已经存在（即链表中有相同元素），则不插入，保持唯一性。

结论：

Set 类型允许哈希冲突，只要值不同就能插入；不允许值重复，即使哈希值一样，Redis 也会用 memcmp 判断值是否相等

Hash 类型（field-value 映射）：
Hash 类型本质是：

dict<field, value>

与 Set 类似：

冲突时使用链式哈希解决

同一个 field 不允许重复，如果 field 已存在，则更新 value

插入逻辑：

dictReplace(hash, field, value);  // 如果存在就覆盖

总结：

Set：
bucket[5] --> ["apple"] --> ["banana"]      // 值不能重复，但可以 hash 冲突Hash：
bucket[5] --> ["name" => "Tom"] --> ["age" => 20] // key 冲突则更新 value

实际看看 intset 和hashtable 的底层存储数据区别

设计一个实验去看插入519个数据之前和插入520个数据的区别

@Service
@RequiredArgsConstructor
@Slf4j
public class SetEncodingDemoService {private final RedisTemplate<String, String> redisTemplate;// key for testingprivate static final String SET_KEY = "demo:set:encoding";// 清空 & 初始化测试public void runEncodingTest() {redisTemplate.delete(SET_KEY);log.info("开始添加整数元素，触发 intset -> hashtable 升级演示");// 1. 添加 500 个整数（仍为 intset 编码）IntStream.range(0, 500).forEach(i -> {redisTemplate.opsForSet().add(SET_KEY, String.valueOf(i));});log.info("添加 500 个整数完成，请用命令 `debug object demo:set:encoding` 查看编码，预计为 intset");// 2. 继续添加超过限制，触发升级IntStream.range(500, 520).forEach(i -> {redisTemplate.opsForSet().add(SET_KEY, String.valueOf(i));});log.info( 添加第 520 个整数完成，预计编码变为 hashtable");}
}

测试类

@SpringBootTest
class SetEncodingDemoServiceTest {@Autowiredprivate SetEncodingDemoService setEncodingDemoService;@Testpublic void testEncodingChange() {setEncodingDemoService.runEncodingTest();}
}

分别执行步骤 1 和步骤 2:
在这里插入图片描述

在这里插入图片描述

可以非常详细的看到内部数据结构由intset 变成了hashtable

使用例子

okok 我们已经了解了 set底层为整数数组+hashtable 那么接下来我们就来看看实际的使用例子
wait 稍等一下 set 有哪些常见的使用场景

特异元素都多少个？求交并集？元素是否存在？

ok 那不就是可以使用这些场景吗

在线用户统计（去重）

记录所有在线用户，使用 Set 去重，并可实时获取当前在线用户数量。

redis结构：

// userID加入
SADD online:users userId
// 求在key（online:users）下有多少个userID
SCARD online:users
// 移除online:users userId 元素
SREM online:users userId

@Service
@RequiredArgsConstructor
public class OnlineUserService {private final RedisTemplate<String, Object> redisTemplate;private static final String ONLINE_USER_KEY = "online:users";// 用户上线public void userOnline(String userId) {redisTemplate.opsForSet().add(ONLINE_USER_KEY, userId);}// 用户下线public void userOffline(String userId) {redisTemplate.opsForSet().remove(ONLINE_USER_KEY, userId);}// 获取当前在线人数public long getOnlineCount() {return redisTemplate.opsForSet().size(ONLINE_USER_KEY);}// 获取所有在线用户public Set<Object> getAllOnlineUsers() {return redisTemplate.opsForSet().members(ONLINE_USER_KEY);}
}

相似度计算（用户标签交集）

为每个用户打标签，利用标签集合之间的交集计算相似度（如推荐系统）。

redis结构

// 给user:tags:uid123  打上三个标签
SADD user:tags:uid123 "java" "redis" "ai"
// 给user:tags:uid456  打上三个标签
SADD user:tags:uid456 "java" "kafka" "ai"
// 求交集
SINTER user:tags:uid123 user:tags:uid456

@Service
@RequiredArgsConstructor
public class UserTagSimilarityService {private final RedisTemplate<String, Object> redisTemplate;// 为用户添加标签public void addTags(String userId, String... tags) {String key = "user:tags:" + userId;redisTemplate.opsForSet().add(key, (Object[]) tags);}// 获取两个用户的共同标签（交集）public Set<Object> getCommonTags(String uid1, String uid2) {String key1 = "user:tags:" + uid1;String key2 = "user:tags:" + uid2;return redisTemplate.opsForSet().intersect(key1, key2);}// 相似度得分（交集大小 / 并集大小）public double computeSimilarity(String uid1, String uid2) {String k1 = "user:tags:" + uid1;String k2 = "user:tags:" + uid2;Set<Object> inter = redisTemplate.opsForSet().intersect(k1, k2);Set<Object> union = redisTemplate.opsForSet().union(k1, k2);if (union == null || union.isEmpty()) return 0.0;return (double) inter.size() / union.size();}
}

秒杀活动参与者去重

高并发下秒杀活动记录用户参与，每个用户只能参与一次。

Redis 结构：

// seckill:activity:10001 下 增加一个 userId
SADD seckill:activity:10001 userId

@Service
@RequiredArgsConstructor
public class SeckillService {private final RedisTemplate<String, Object> redisTemplate;// 秒杀参与：返回是否成功（是否重复）public boolean tryJoinSeckill(String activityId, String userId) {String key = "seckill:activity:" + activityId;Long added = redisTemplate.opsForSet().add(key, userId);return added != null && added > 0;}// 获取参与人数public long getJoinCount(String activityId) {return redisTemplate.opsForSet().size("seckill:activity:" + activityId);}// 判断用户是否参与过public boolean hasJoined(String activityId, String userId) {return Boolean.TRUE.equals(redisTemplate.opsForSet().isMember("seckill:activity:" + activityId, userId));}
}

总结：

场景	Redis Key 样例	操作	高并发优势
在线用户统计	`online:users`	`SADD` / `SCARD`	去重 + 实时查询人数
用户相似度分析	`user:tags:uid123`	`SINTER` / `SUNION`	集合交集操作原子且高效
秒杀用户去重	`seckill:activity:10001`	`SADD`	去重保证每人只能参与一次