前言: set 类似于数学上面的集合概念,包含的元素无序,不能重复,能进行交、并、差操作。
一、内部原理
set 数据结构,也是随着元素数目的多少而变化。当 set 中添加的元素都是整数且元素数据较少时,set 使用 intset 为底层的数据结构,否则,set 使用 dict 作为底层的数据结构。
intset 是什么?
从字面意思可以看出是由整数组成的集合。是一个整数组成的有序集合,便于进行二分查找,快速判断一个元素是否属于这个集合。内存分配上也是一整块连续的内存空间,而且根据数值的大小采取了不同的编码,对内存使用进行了优化。 intset 数据结构如下:
- typedefstruct intset {
- uint32_t encoding;/*数据编码,表示intset中每个数据元素用几个字节来存储。有三种:数据编码,表示intset中每个数据元素用几个字节来存储。
- 1.INTSET_ENC_INT16表示每个元素用2个字节存储,
- 2.INTSET_ENC_INT32表示每个元素用4个字节存储,
- 3.INTSET_ENC_INT64表示每个元素用8个字节存储。
- 因此,intset中存储的整数最多只能占用64bit*/
- uint32_t length; /*元素个数。encoding和length组成了intset头部。*/
- int8_t contents[]; /*是一个柔性数组,表示intset的header后面紧跟着数据元素。这个数组的总长度(即总字节数)等于encoding * length*/
- } intset;
注:intset 可能会随着数据的添加而改变它的数据编码,创建时 intset 使用占内存最小的 INTSET_ENC_INT16 作为编码,每增加一个元素,则根据大小决定是否对数据编码进行改变。
例子:
如上图: 1、新建一个 intset 只有一个 header,总共 8 个字节,encoding=2,length=0。 2.、添加 6,15 之后,因为数值较小,所以 encoding 不变,length=2。 3、添加 32768 的时候,超过了两个字节(2 个字节能表达的数据范围是 - 32768~32767),此时 encoding 升级到 INTSET_ENC_INT32 为 4,即用 4 个字节表示一个元素。 4、添加元素都是按照从小到大的顺序。 5、intset 是按 little endian 模式存储的。在上图 intset 添加完所有数据之后,32768=>0x00008000 什么时间转为 dict? 1、大于 512,默认设置:set-max-intset-entries 512 2、超出最大范围 - 264~264-1 3、元素里面包含非数字 set 底层用 dict 时,key 是要添加的元素,value 为 NULL。 区别: 小集合(整数)用 intset 存储节省内存。dict 带来的开销很大(包含元数据信息,两个 hash 表、链表指针等等) 从时间复杂度上看,intset 是 o(log n), 而 dict 可以认为是 o(1)(因为 zipmap),但是 intset 元素个数较少,影响不大
二、相关操作 SADD key member [member ...] 将一个或多个元素加入到集合 key 中,已存在被忽略。若不存在,则创建。 SCARD key 返回集合 key 的数目。 SDIFF key [key ...] 返回集合之间的差集 SDIFFSTORE destination key [key ...] 返回集合之间的差集,并将结果存储到目标集合。 SINTER key [key ...] 返回集合集合之间的交集 SINTERSTORE destination key [key ...] 返回集合之间的交集,并将结果存储到目标集合。 SISMEMBER key member 判断元素是否属于集合 key 的成员。 SMOVE source destination member 将元素从源集合移动到目标集合。 SPOP key 随机移除 key 集合的某一元素,并返回该元素。 SRANDMEMBER key [count] 随机返回一个 key 集合的元素,若提供 count 参数,则返回一个包含 count 个元素的数组。 SREM key member [member ...] 移除集合中的一个或多个元素。不存在则忽略。 SUNION key [key ...] 返回若干个集合的并集。 SUNIONSTORE destination key [key ...] 返回若干个集合的并集,并存储在目标集合
来源: http://www.cnblogs.com/programlearning/p/7053396.html