Redis数据结构：Set类型全面解析

栗筝i

发布于 2023-10-16 14:35:33

8840

发布于 2023-10-16 14:35:33

文章被收录于专栏：迁移内容

Set 类型是一个无序并唯一的键值集合，它的存储顺序不会按照插入的先后顺序进行存储。Redis 中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。相对于列表，集合也有两个特点：无序、不可重复一个集合最多可以存储 2^32-1 个元素。概念和数学中个的集合基本类似，数学集合的概念是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。简而言之，Redis 集合就是一些不重复值的组合。利用集合（Set）这个数据结构，Redis 可以存储一些集合类型的数据，Redis也通过一些简便的命令很好的支持了交集、并集和差集等集合的基本运算。

1、Set数据类型

1.1、Set类型简介

Set 类型是一个无序并唯一的键值集合，它的存储顺序不会按照插入的先后顺序进行存储。Redis 中集合是通过哈希表实现的，所以添加，删除，查找的复杂度都是 O(1)。相对于列表，集合也有两个特点：无序、不可重复

一个集合最多可以存储 2^32-1 个元素。概念和数学中个的集合基本类似，数学集合的概念是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。

简而言之，Redis 集合就是一些不重复值的组合。利用集合（Set）这个数据结构，Redis 可以存储一些集合类型的数据，Redis也通过一些简便的命令很好的支持了交集、并集和差集等集合的基本运算。

1.2、Set应用场景

常见的应用场景有：投票系统、标签系统、共同好友、共同关注、共同爱好、抽奖、商品筛选栏，访问 IP 统计等

使用场景：

点赞、踩、收藏：Set 类型可以保证一个用户只能点一个赞；
共同关注、标签：Set 类型支持交集运算，所以可以用来计算共同关注的好友、公众号等；
抽奖活动：存储某活动中中奖的用户名，Set 类型因为有去重功能，可以保证同一个用户不会中奖两次

2、Set底层结构

2.1、List底层结构介绍

Redis Set 的底层存储采用整数集合 IntSet 和哈希表，二者是相互转换的，使用 IntSet 存储必须满足下面两个条件，否则使用 HashTable，条件如下：

结合对象保存的所有元素都是整数值；
集合对象保存的元素数量不超过 512 个

以 Set 的 SADD 命令为例子，整个添加过程如下：

检查 Set 是否存在不存在则创建一个 Set 结合。
根据传入的 Set 集合一个个进行添加，添加的时候需要进行内存压缩。
setTypeAdd 执行 Set 添加过程中会判断是否进行编码转换

void saddCommand(redisClient *c) {
    robj *set;
    int j, added = 0;
 
    // 取出集合对象
    set = lookupKeyWrite(c->db,c->argv[1]);
 
    // 对象不存在，创建一个新的，并将它关联到数据库
    if (set == NULL) {
        set = setTypeCreate(c->argv[2]);
        dbAdd(c->db,c->argv[1],set);
 
    // 对象存在，检查类型
    } else {
        if (set->type != REDIS_SET) {
            addReply(c,shared.wrongtypeerr);
            return;
        }
    }
 
    // 将所有输入元素添加到集合中
    for (j = 2; j < c->argc; j++) {
        c->argv[j] = tryObjectEncoding(c->argv[j]);
        // 只有元素未存在于集合时，才算一次成功添加
        if (setTypeAdd(set,c->argv[j])) added++;
    }
 
    // 如果有至少一个元素被成功添加，那么执行以下程序
    if (added) {
        // 发送键修改信号
        signalModifiedKey(c->db,c->argv[1]);
        // 发送事件通知
        notifyKeyspaceEvent(REDIS_NOTIFY_SET,"sadd",c->argv[1],c->db->id);
    }
 
    // 将数据库设为脏
    server.dirty += added;
 
    // 返回添加元素的数量
    addReplyLongLong(c,added);
}

稍微深入分析一下set的单个元素的添加过程，首先如果已经是 HashTable 的编码，那么我们就走正常的 HashTable 的元素添加，如果原来是 IntSet 的情况，那么我们就需要进行如下判断：

如果能够转成 int 的对象（isObjectRepresentableAsLongLong），那么就用 IntSet 保存。
如果用 IntSet 保存的时候，如果长度超过5 12（REDIS_SET_MAX_INTSET_ENTRIES）就转为 HashTable 编码。
其他情况统一用 HashTable 进行存储。

2.2、整数集合IntSet

整数集合 IntSet 是 Redis用来保存整数值的集合的一种数据结构，可以用来保存 int 类型数据，并且可以保证不会出现重复元素。因此当一个集合中只包含整数元素且数量不多的时候，Redis 会选择使用整数集合作为底层实现。

IntSet 内部其实是一个数组（int8_t coentents[] 数组），而且存储数据的时候是有序的，因为在查找数据的时候是通过二分查找来实现的。

如果你的集合只有整数值元素，并且数量是轻量的，这时候 Redis 会使用使用整数集合作为 Redis 集合的底层数据结构。参考如下代码：

typedef struct IntSet{
     // 编码格式
     uint32_t encoding;
     // 集合中的元素个数
     uint32_t length;
     // 保存元素数据
     int8_t contents[];
} IntSet;

我们拆解下：

属性	说明
“encoding”	编码方式
“length”	数组中元素个数，也就是数组的整体长度
“contents[]”	整数集合，集合的每个元素都是数组的一个数组项（item）。具有特点：按值的大小增序排列、不包含任何重复项

“contents” 是整数集合的底层实现，保存了整数集合的每一个元素，每个元素在该数组中从小到大有序排列，并且不重复（如何保证有序性和唯一性我们后面讨论插入的时候在说）。“contents” 数组虽然声明为 int8_t 类型，但其实真正的类型取决于 “encoding” 的值。在操作一个整数集合的时候，会首先获取 “encoding” 的值。

举个栗子，当我们执行 SADD numbers 1 3 5 向集合对象插入数据时，该集合对象在内存的结构如下：

2.3、哈希表HashTable

Redis 中的 key-value 是通过 dictEntry 对象来实现的，而哈希表就是将 dictEntry 进行了再一次的包装得到的，这就是哈希表对象 dictht：

typedef struct dictht {
    dictEntry **table;//哈希表数组
    unsigned long size;//哈希表大小
    unsigned long sizemask;//掩码大小，用于计算索引值，总是等于size-1
    unsigned long used;//哈希表中的已有节点数
} dictht;

PS：table 是一个数组，其每个元素都是一个 dictEntry 对象。

hashtable 编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象对应一个集合元素，字典的值都是 NULL。当我们执行 SADD fruits "apple" "banana" "cherry" 向集合对象插入数据时，该集合对象在内存的结构如下：