Set 类型是一个无序并唯一的键值集合,它的存储顺序不会按照插入的先后顺序进行存储。Redis 中集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)。相对于列表,集合也有两个特点:无序、不可重复 一个集合最多可以存储
2^32-1
个元素。概念和数学中个的集合基本类似,数学集合的概念是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。 简而言之,Redis 集合就是一些不重复值的组合。利用集合(Set)这个数据结构,Redis 可以存储一些集合类型的数据,Redis也通过一些简便的命令很好的支持了交集、并集和差集等集合的基本运算。
Set 类型是一个无序并唯一的键值集合,它的存储顺序不会按照插入的先后顺序进行存储。Redis 中集合是通过哈希表实现的,所以添加,删除,查找的复杂度都是 O(1)。相对于列表,集合也有两个特点:无序、不可重复
一个集合最多可以存储 2^32-1
个元素。概念和数学中个的集合基本类似,数学集合的概念是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。
简而言之,Redis 集合就是一些不重复值的组合。利用集合(Set)这个数据结构,Redis 可以存储一些集合类型的数据,Redis也通过一些简便的命令很好的支持了交集、并集和差集等集合的基本运算。
常见的应用场景有:投票系统、标签系统、共同好友、共同关注、共同爱好、抽奖、商品筛选栏,访问 IP 统计等
使用场景:
Redis Set 的底层存储采用 整数集合 IntSet 和哈希表,二者是相互转换的,使用 IntSet 存储必须满足下面两个条件,否则使用 HashTable,条件如下:
以 Set 的 SADD 命令为例子,整个添加过程如下:
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 的情况,那么我们就需要进行如下判断:
整数集合 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
向集合对象插入数据时,该集合对象在内存的结构如下:
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"
向集合对象插入数据时,该集合对象在内存的结构如下:
使用 SADD 命令添加集合元素
SADD set value
若值已存在,则不进行添加,并返回 0
使用 SMEMBERS 命令查看集合所有值
SMEMBERS set
使用 SISMEMBER 命令判断一个值是否在集合中
使用 SCARD 命令查看某集合的存值的数量
SCARD set
使用 SREM 删除集合中指定值的元素
SREM set value
使用 SRANDMEMBER 命令随机选出某集合中一个元素
SRANDMEMBER set
使用 SPOP 命令随机删除某集合中一个元素
SPOP set
使用 SMOVE 命令 将一个集合中的某值移动至另一个集合
SMOVE source target value
使用 SDIFF 命令进行集合运算:差集
SDIFF set1 set2
使用 SINTER 命令进行集合运算:交集
SINTER set1 set2
使用 SUNION 命令进行集合运算:并集
SUNION set1 set2