文章目录

前言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

与 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 redisTemplate;

// key for testing

private 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 {

@Autowired

private SetEncodingDemoService setEncodingDemoService;

@Test

public 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 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