Redis Set 用了 2 种数据结构来存储，到现在才知道

谁践踏了优雅 2023-09-26 23:23 95阅读 0赞

Sets 无序集合，他的功能就好像你熟悉的 Java 中的 HashSet 一样。集合是通过散列表实现的，所以添加、删除、查找元素的时间复杂度是 O(1)。

## 1. 是什么 ##

Sets 是 String 类型的无序集合，集合中的元素是唯一的，集合中**不会出现重复的数据**。

Java 的 HashSet 底层是用 HashMap 实现，Sets 的底层数据结构也是用 Hashtable（散列表）实现，散列表的 key 存的是 Sets 集合元素的 value，散列表的 value 则指向 NULL。

不同的是，当元素内容都是 64 位以内的十进制整数的时候，并且元素个数不超过 `set-max-intset-entries` 配置的值（默认 512）的时候，**会使用更加省内存的 intset（整形数组）来存储**。

![7d3c403e26d711d2cd83b4d5e8adfa69.png][]

图2-15

**使用场景**

当你需要存储多个元素，并且要求不能出现重复数据，无需考虑元素的有序时，就可以使用 Sets 来存储，这样能利用我对单个元素操作 O(1) 时间复杂度带来的性能优势。

并且 Sets 还支持在集合之间做交集、并集、差集操作，比如当你遇到如下场景，需要统计多个集合元素的聚合结果。

*  统计多个元素的共有数据（交集）。
 *  统计两个集合其中的一个独有元素（差集统计）。
 *  统计多个集合的所有元素（并集统计）。

常见的使用场景。

1.  社交软件中共同关注，通过交集实现。
2.  每日新增关注数，只需要对近两天的总注册用户量集合取差集即可。
3.  打标签：比如微信收藏功能，你可以为自己收藏的每一篇文章打标签，这样你可以快速的找到被添加了某个标签的所有文章。

## 2. 修炼心法 ##

关于散列表结构我会在专门的章节介绍，先看 intset 结构，结构体定义在源码 `intset.h`中。

typedef struct intset {
        uint32_t encoding;
        uint32_t length;
        int8_t contents[];
    } intset;

*  length，记录整数集合存储的元素个数，其实就是 contents 数组的长度。
 *  contents，真正存储整数集合的数组，是一块连续内存区域。每个元素都是数组的一个数组元素，数组中的元素会按照值的大小从小到大有序排列存储，并且不会有重复元素。
 *  encoding，编码格式，决定数组类型，一共有三种不同的值。
    
     *  INTSET\_ENC\_INT16，表示 contents 数组的存储元素是 int16\_t 类型，每 2 字节表示一个整数元素。
     *  INTSET\_ENC\_INT32，表示 contents 数组的存储元素是 int32\_t 类型，每 4 字节表示一个元素。
     *  INTSET\_ENC\_INT64，表示 contents 数组的存储元素是 int64\_t 类型，每 8 字节表示一个元素。

![166c012ed6de4b60c233eefa534d8f65.png][]

图2-16

> MySQL：“如果在一个 int16\_t 类型的整数集合中插入一个 int64\_t 类型的值会怎样？”

这个问题问得好，下次可以继续保持。

这种情况会触发整数集合升级，也就是集合的所有元素都会转换成 int64\_t 类型，步骤如下。

1.  根据新元素的类型，以及集合元素的数量，包括新添加的元素在内，计算新的空间大小，对底层数组空间扩容，进行空间重新分配。
2.  将数组原有的元素都转换成新元素类型，把转换后的元素按照从大到小的顺序放到正确的位置上，**需要保证数组元素的有序性**。
3.  修改 encoding 的值，length + 1。

所以每次向整形数组集合添加新元素都可能会引起升级，升级又会对原始数据进行类型转换，时间复杂度是 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 的位置。

## 3. 出招实战：共同好友 ##

三国天下有限公司开发了一个名叫“三国恋”的社交 APP，想要实现共同好友功能，这个场景就能使用集合交集来实现。为每个用户创建一个 Sets 集合，账号名作为集合的 key，集合 value 存储该账号的好友。

如下指令构建刘备和曹操的好友集合。

SADD user:刘备 赵子龙 张飞 关羽 貂蝉
    SADD user:曹操 貂蝉 夏侯惇 典韦 张辽

想要知道两个人的共同好友，也就是两个集合的交集，只需要使用 `SINTERSTORE`指令。

SINTERSTORE user:曹刘好友 user:刘备 user:曹操

命令执行后，刘备与曹操两个集合的交集数据就存储到了“user:曹刘好友”集合中。使用 `SMEMBERS` 查看曹操与刘备的共同好友。

redis> SMEMBERS user:曹刘好友
    1) "貂蝉"

好家伙，他们都喜欢貂蝉，你喜不喜欢呢？

![4129c41df3513d5f8cc0cdcfc400a451.png][]

[7d3c403e26d711d2cd83b4d5e8adfa69.png]: https://img-blog.csdnimg.cn/img_convert/7d3c403e26d711d2cd83b4d5e8adfa69.png
[166c012ed6de4b60c233eefa534d8f65.png]: https://img-blog.csdnimg.cn/img_convert/166c012ed6de4b60c233eefa534d8f65.png
[4129c41df3513d5f8cc0cdcfc400a451.png]: https://img-blog.csdnimg.cn/img_convert/4129c41df3513d5f8cc0cdcfc400a451.png