1.4 set - 图1

1.内部结构

set类型内部存储结构有2种：

  • insert（整数集合）：当集合中的元素都是整数且元素个数小于set-maxintset-entries配置（默认512个）时，Redis会选用intset来作为集合的内部实现，从而减少内存的使用。
  • hashtable(哈希表）：当集合类型无法满足insert的条件时，Redis会使用hashtable （dict.c）作为集合的内部实现;

    1.1 整数集合（inset）

    1. typedef struct intset {
    2.   uint32_t encoding;
    3.   uint32_t length;
    4.   int8_t contents[];
    5. } intset;
    整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素。

    1.1.1 组成部分

    1.1.1.1 encoding

    1. /* Note that these encodings are ordered, so:
    2. * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
    3. #define INTSET_ENC_INT16 (sizeof(int16_t))
    4. #define INTSET_ENC_INT32 (sizeof(int32_t))
    5. #define INTSET_ENC_INT64 (sizeof(int64_t))
    contents数组的真正类型取决于encoding属性的值。
    encoding属性的值为INTSET_ENC_INT16则数组就是uint16_t类型，数组中的每一个元素都是int16_t类型的整数值(-32768——32767)，
    encoding属性的值为INTSET_ENC_INT32则数组就是uint32_t类型，数组中的每一个元素都是int16_t类型的整数值(-2147483648——2147483647)。

1.1.1.2 length

length属性记录了数组的长度

1.1.1.3 contents

contents数组是整数集合的底层实现，整数集合的每个元素都是 contents数组的个数组项(item),各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。

1.4 set - 图2

如上图，为一int16_t类型的整数集合，我们可以看到数组中存储了5个int16_t类型的整数，它们按照从小到大的顺序依次排列。这个时候我们思考一个问题。如果这个时候存入一个int32_t类型的整数会怎么样？内存溢出？这个时候就要提到整数集合的升级。

1.1.2 整数集合的升级

1.1.2.1 整数集合升级过程

正如上面所提到的问题，每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合里面。升级整数集合并添加新元素主要分三步来进行。

  • 根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
  • 将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
  • 将新元素添加到底层数组里面；

1.4 set - 图3

1.1.2.2 整数集合升级的优点

  • 提升灵活性

    1. 因为C语言是静态类型语言,为了避免类型错误,我们通常不会将两种不同类型的值放在同一个数据结构里面。
    2. 例如,我们一般只使用int16_t类型的数组来保存int16_t类型的值,只使用int32_t类型的数组来保存int32_t类型的值,诸如此类。
    3. 但是,因为整数集合可以通过自动升级底层数组来适应新元素,所以我们可以随意地将int16_t、int32_t或者int64_t类型的整数添加到集合中,
    4. 而不必担心出现类型错误,这种做法非常灵活。

  • 节约内存 ```cpp 要让一个数组可以同时保存int16_t、int32_t、int64_t三种类型的值,最简单的做法就是直接使用int64t类型的数组作为整数集合的底层实现。 不过这样一来,即使添加到整数集合里面的都是int16_t类型或者int32_t类型的值,数组都需要使用int64_t类型的空间去保存它们,从而出现浪费内存的情况。

而整数集合现在的做法既可以让集合能同时保存三种不同类型的值,又可以确保升级操作只会在有需要的时候进行,这可以尽量节省内存。 如果我们一直只向整数集合添加int16_t类型的值,那么整数集合的底层实现就会一直是int16_t类型的数组,只有在我们要将int32_t类型或者int64_t类型的值添加到集合时,程序才会对数组进行升级。

  1. <a name="sExZD"></a>
  2. ### 1.1.3 缺点-无法降级
  3.   整数集合不支持降级操作,一旦对数组进行了升级,编码就会一直保持升级后的状态。也就是说一旦我们向一个int16_t的整数集合内添加了一个int32_t的元素后，整数集合将升级到int32_t类型。即使后续的操作中我们删除了这个元素，整数集合还是会保持int32_t类型的状态。可能在某些场景下会造成内存浪费。
  4. <a name="ZHFBo"></a>
  5. ## 1.2 哈希表 hashtable
  6. 详情查看 1.3 hash 中描述。
  8. <a name="1MvJG"></a>
  9. # 2.常用命令
  10. | 命令 | 说明 | 时间复杂度 |
  11. | --- | --- | --- |
  12. | [SADD key member [member ...]](http://blog.laoyu.site/2020/redis_command/set/sadd/) | 添加一个或者多个元素到集合(set)里 | O(N) |
  13. | [SCARD key](http://blog.laoyu.site/2020/redis_command/set/scard/) | 获取集合里面的元素数量 | O(1) |
  14. | [SDIFF key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sdiff/) | 获得队列不存在的元素 | O(N) |
  15. | [SDIFFSTORE destination key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sdiffstore/) | 获得队列不存在的元素，并存储在一个关键的结果集 | O(N) |
  16. | [SINTER key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sinter/) | 获得两个集合的交集 | O(N*M) |
  17. | [SINTERSTORE destination key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sinterstore/) | 获得两个集合的交集，并存储在一个关键的结果集 | O(N*M) |
  18. | [SISMEMBER key member](http://blog.laoyu.site/2020/redis_command/set/sismember/) | 确定一个给定的值是一个集合的成员 | O(1) |
  19. | [SMEMBERS key](http://blog.laoyu.site/2020/redis_command/set/smembers/) | 获取集合里面的所有元素 | O(N) |
  20. | [SMOVE source destination member](http://blog.laoyu.site/2020/redis_command/set/smove/) | 移动集合里面的一个元素到另一个集合 | O(1) |
  21. | [SPOP key [count]](http://blog.laoyu.site/2020/redis_command/set/spop/) | 删除并获取一个集合里面的元素 | O(1) |
  22. | [SRANDMEMBER key [count]](http://blog.laoyu.site/2020/redis_command/set/srandmember/) | 从集合里面随机获取一个元素 |  |
  23. | [SREM key member [member ...]](http://blog.laoyu.site/2020/redis_command/set/srem/) | 从集合里删除一个或多个元素 | O(N) |
  24. | [SUNION key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sunion/) | 添加多个set元素 | O(N) |
  25. | [SUNIONSTORE destination key [key ...]](http://blog.laoyu.site/2020/redis_command/set/sunionstore/) | 合并set元素，并将结果存入新的set里面 | O(N) |
  26. | [SSCAN key cursor [MATCH pattern] [COUNT count]](http://blog.laoyu.site/2020/redis_command/set/sscan/) | 迭代set里面的元素 | O(1) |
  28. <a name="j5Ehd"></a>
  29. # 3.使用场景
  30. 通过上文，我们可以知道集合的主要几个特性，无序、不可重复、支持并交差等操作。因此集合类型比较适合用来数据去重和保障数据的唯一性，还可以用来统计多个集合的交集、错集和并集等，当我们存储的数据是无序并且需要去重的情况下，比较适合使用集合类型进行存储
  31. <a name="o1Qtb"></a>
  32. ## 3.1 标签系统
  33. 集合类型比较典型的使用场景是标签（tag）。<br />1.给用户添加标签。
  34. ```cpp
  35. sadd user:1:tags tag1 tag2 tag5
  36. sadd user:2:tags tag2 tag3 tag5
  37. ...
  38. sadd user:k:tags tag1 tag2 tag4
  39. ...

2.给标签添加用户

  1. sadd tag1:users user:1 user:3
  2. sadd tag2:users user:1 user:2 user:3
  3. ...
  4. sadd tagk:users user:1 user:2
  5. ...

3.使用sinter命令，可以来计算用户共同感兴趣的标签

  1. sinter user:1:tags user:2:tags

这种标签系统在电商系统、社交系统、视频网站，图书网站，旅游网站等都有着广泛的应用。例如一个用户可能对娱乐、体育比较感兴趣，另一个用户可能对历史、新闻比较感兴趣，这些兴趣点就是标签。有了这些数据就可以得到喜欢同一个标签的人，以及用户的共同喜好的标签，这些数据对于用户体验以及增强用户黏度比较重要。例如一个社交系统可以根据用户的标签进行好友的推荐，已经用户感兴趣的新闻的推荐等，一个电子商务的网站会对不同标签的用户做不同类型的推荐，比如对数码产品比较感兴趣的人，在各个页面或者通过邮件的形式给他们推荐最新的数码产品，通常会为网站带来更多的利益

3.2 抽奖系统

Redis集合的 SPOP(随机移除并返回集合中一个或多个元素) 和 SRANDMEMBER(随机返回集合中一个或多个元素) 命令可以帮助我们实现一个抽奖系统
如果允许重复中奖，可以使用SRANDMEMBER 命令
image.png