Hyper の 个人博客

交流技术，分享生活

0%

Redis 原理初探（四）—— 集合

发表于 更新于 分类于 ， 阅读次数：
本文字数： 2.1k 阅读时长 ≈ 2 分钟

整数集合（intset）

定义

  • 用于保存整数值的集合抽象数据结构

    • 可保存类型为 int16_t、int32_t 或 int64_t 的整数值
    • 保证集合中不会出现重复元素

  • 集合键的底层实现之一

1
2
3
4
5
6
7
8
9
typedef struct intset
{
    //编码方式，决定contents数组的真正类型
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

注：contents 数组是整数集合的底层实现，每个数组元素作为一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含任何重复项。

适用场景

  • 集合只包含整数值元素，并且该集合的元素数量不多

升级（upgrade）

产生原因

  • 添加新元素到数组中时，由于新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级

目的

  • 提升整数集合的灵活性：因为整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将 int16_t、int32_t 或者 int64_t 类型的整数添加到集合中，而不必担心出现类型错误

  • 尽可能地节约内存

步骤

  • 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间

  • 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。

  • 将新元素添加到底层数组中，再更新原整数集合的 encoding 和 length

时间复杂度

  • O (N)：每次升级都需要对底层数组中已有的所有元素进行类型转换

降级（degrade）

  • 整数集合不支持该操作。这也意味着一旦整数集合经过升级并占用更大的内存后，即便经过后续操作后不再需要过大的内存空间时，也无法进行回退

集合操作

常用命令

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import redis

# 获取连接
conn = redis.Redis(host='127.0.0.1', password='123456', port=6379)

# SADD：向指定集合中添加尚不存在的元素（可一次添加多个）
# 返回的是被添加元素的数量
conn.sadd('set_key', 'a', 'b', 'c', 'd', 'e')
# SREM：从指定集合中移除元素（可一次移除多个）
# 注：Python中返回布尔值；实际redis中返回的是被移除元素的数量
conn.srem('set_key', 'c', 'd')
# SISMEMBER：检查数据项item是否存在于指定集合中
conn.sismember('set_key', 'val')
# SCARD：返回集合中元素的数量
conn.scard('set_key')
# SMEMBERS：返回集合中包含的所有元素
conn.smembers('set_key')
# SRANDMEMBER：从指定集合中随机返回一个或多个元素值
# 这里可以指定count参数，但该值不是随机返回元素的个数
# 而是根据其正负情况决定是否返回重复元素（有无放回）
# 若为正数，则不会重复；否则可以取出重复的值
conn.srandmember('set_key', -1)
# SPOP：随机（！）的移除指定集合中的一个元素
# 返回被移除的元素
conn.spop('set_key')
# SMOVE：从集合1中移除元素并移动到集合2中
# 若成功，返回1；否则返回0，相当于命令无效
conn.smove('set_key', 'set_key2', 'a')

差集、交集与并集运算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# SDIFF：对两个集合作差集运算
# 返回存在于第一个集合但不存在于第二个集合的所有元素
conn.sdiff('set_key', 'set_key2')
# SDIFFSTORE：对两个集合作差集运算
# 储存存在于第一个集合但不存在于第二个集合的所有元素
conn.sdiffstore('store_key', 'set_key', 'set_key2')
# SINTER：对两个集合作交集运算
# 返回那些同时存在于所有集合的元素
conn.sinter('set_key', 'set_key2')
# SINTERSTORE：对两个集合作交集运算
# 储存那些同时存在于所有集合的元素
conn.sinterstore('store_key', 'set_key', 'set_key2')
# SUNION：对两个集合作并集运算
# 返回那些至少存在于一个集合的元素
conn.sunion('set_key', 'set_key2')
# SUNIONSTORE：对两个集合作并集运算
# 储存那些至少存在于一个集合的元素
conn.sunionstore('store_key', 'set_key', 'set_key2')

注：就集合这一结构而言，其基本功能在 Python 与 Redis 中的实现并无过大差别。Redis 集合的好处在于，可以同时被多个客户端进行远程访问。

【参考】
[1] 《Redis 的设计与实现》

[2] 《Redis 实战》

相关文章：