Redis数据类型之Set-13003666

hc6538

　　前言:set类似于数学上面的集合概念，包含的元素无序，不能重复，能进行交、并、差操作。
　　一、内部原理
　　set数据结构，也是随着元素数目的多少而变化。当set中添加的元素都是整数且元素数据较少时，set使用intset为底层的数据结构，否则，set使用dict作为底层的数据结构。
　　intset是什么？
　　从字面意思可以看出是由整数组成的集合。是一个整数组成的有序集合，便于进行二分查找，快速判断一个元素是否属于这个集合。内存分配上也是一整块连续的内存空间，而且根据数值的大小采取了不同的编码，对内存使用进行了优化。
　　intset数据结构如下：

typedef struct 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 ...]
　　返回若干个集合的并集，并存储在目标集合