Set

无序集合，其中的元素不重复。

内存数据结构

Set在Redis中以intset或hashtable存储。hashtable中的value永远为NULL。当set中只包含整数型元素时，采用intset实现。

intset

typedef struct intset{
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

intset的核心元素是一个字节数组，其中从小到大地有序存放着set的元素，length表示元素个数，encoding表示每个元素的编码方式。其中编码方式指定了一个整数元素占用多少个contents数组位。

由于元素有序排列，所以set的获取操作采用二分查找方式实现，复杂度O(log(N))。

进行插入操作时，首先通过二分查找得到本次插入的位置，再对元素进行扩容，再将预计插入位置之后的所有元素向后移动一个位置，最后插入元素。插入复杂度为O(N)。

存储在content中的元素应该是定长的，即所有的元素占用content数组相同的格子。因此对于一个所有元素为小整数的intset突然插入一个大整数，intset中原有的所有元素都需要将所占有的字节升级为更多的字节。这个过程涉及全集合的移动。由于引起升级的新元素一定大于(或小于)全部已有元素，所以新的元素的插入位置要么在头要么在尾。

原有元素从后面的元素开始移动，由于每个元素的新位置一定大于旧位置，移动过程不会发生覆盖。

intset针对小整数进行了性能优化，对不同类型的整数采用变长的存储，在元素均不大的情况下减少了内存开销。

升级实例

假设有一个intset，里面有三个int16_t保存的数值，分别是1、2、3，结构如下：

encoding=INTSET_ENC_INT16;
length=3;
contents=[1,2,3];

其中intset中contents在内存中的排列如下：

现在需要将一个长度为int32_t的值65535加入到集合中，intset需要进行以下步骤：

1.将encoding设置为INTSETENCINT32；

2.根据encoding的值，对contents数组进行内存重分配。重分配完成后，contents在内存中的排列如下:

3.因为原来的3个int16_t值还在contents前面48个位里，所以程序需要移动它们并转换类型，让她们适应集合的新编码方式。

首先移动3：

接着移动2：

最后移动1：

4.最后将新值65535添加到数组，将length设置为4：

至此，集合的升级和新增操作完成，现在的结构如下：

encoding=INTSET_ENC_INT32;
length=4;
contents=[1,2,3,65535];