Sets 无序集合,他的功能就好像你熟悉的 JAVA 中的 HashSet 一样。集合是通过散列表实现的,所以添加、删除、查找元素的时间复杂度是 O(1)。
Sets 是 String 类型的无序集合,集合中的元素是唯一的,集合中不会出现重复的数据。
Java 的 HashSet 底层是用 HashMap 实现,Sets 的底层数据结构也是用 Hashtable(散列表)实现,散列表的 key 存的是 Sets 集合元素的 value,散列表的 value 则指向 NULL。
不同的是,当元素内容都是 64 位以内的十进制整数的时候,并且元素个数不超过 set-max-intset-entries 配置的值(默认 512)的时候,会使用更加省内存的 intset(整形数组)来存储。
图2-15
当你需要存储多个元素,并且要求不能出现重复数据,无需考虑元素的有序时,就可以使用 Sets 来存储,这样能利用我对单个元素操作 O(1) 时间复杂度带来的性能优势。
并且 Sets 还支持在集合之间做交集、并集、差集操作,比如当你遇到如下场景,需要统计多个集合元素的聚合结果。
常见的使用场景。
关于散列表结构我会在专门的章节介绍,先看 intset 结构,结构体定义在源码 intset.h中。
typedef struct intset {
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;
图2-16
MySQL:“如果在一个 int16_t 类型的整数集合中插入一个 int64_t 类型的值会怎样?”
这个问题问得好,下次可以继续保持。
这种情况会触发整数集合升级,也就是集合的所有元素都会转换成 int64_t 类型,步骤如下。
所以每次向整形数组集合添加新元素都可能会引起升级,升级又会对原始数据进行类型转换,时间复杂度是 O(N)。
MySQL:“如果删除刚刚添加的 int64_t 类型元素,会执行降级操作么?”
整形数组不支持降级操作。
MySQL:“Sets 是无序集合,为何存储整形数字的场景下 contents 数组元素需要有序?”
为了查询元素速度,数组有序我就能使用二分法来提高查询效率。insetFind() 函数返回值等于 0 表示集合中没有目标数据,反之 1 存在目标数据。方法的内部会调用 intsetSearch() 函数使用二分法来实现。
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
int64_t cur = -1;
// 省略一些检查代码
while(max >= min) {
mid = ((unsigned int)min + (unsigned int)max) >> 1;
cur = _intsetGet(is,mid);
if (value > cur) {
min = mid+1;
} else if (value < cur) {
max = mid-1;
} else {
break;
}
}
// 修改 pos 指针
if (value == cur) {
if (pos) *pos = mid;
return 1;
} else {
if (pos) *pos = min;
return 0;
}
}
pos 指针的作用有两个,如果查找到目标值, pos 记录目标值的位置;查找不到目标值,pos 记录的就是这个目标值插入到 intset 的位置。
三国天下有限公司开发了一个名叫“三国恋”的社交 App,想要实现共同好友功能,这个场景就能使用集合交集来实现。为每个用户创建一个 Sets 集合,账号名作为集合的 key,集合 value 存储该账号的好友。
如下指令构建刘备和曹操的好友集合。
SADD user:刘备 赵子龙 张飞 关羽 貂蝉
SADD user:曹操 貂蝉 夏侯惇 典韦 张辽
想要知道两个人的共同好友,也就是两个集合的交集,只需要使用 SINTERSTORE指令。
SINTERSTORE user:曹刘好友 user:刘备 user:曹操
命令执行后,刘备与曹操两个集合的交集数据就存储到了“user:曹刘好友”集合中。使用 SMEMBERS 查看曹操与刘备的共同好友。
redis> SMEMBERS user:曹刘好友
1) "貂蝉"
好家伙,他们都喜欢貂蝉,你喜不喜欢呢?