当一个集合中只包含整数，并且元素的个数不是很多的话，redis 会用整数集合作为底层存储，它的一个优点就是可以节省很多内存，虽然字典结构的效率很高，但是它的实现结构相对复杂并且会分配较多的内存空间。

而我们的整数集合（intset）可以做到使用较少的内存空间却达到和字典一样效率的实现，但也是前提的，集合中只能包含整型数据并且数量不能太多。整数集合最多能存多少个元素在 redis 中也是有体现的。

OBJ_SET_MAX_INTSET_ENTRIES 512

也就是超过 512 个元素，或者向集合中添加了字符串或其他数据结构，redis 会将整数集合向字典结构进行转换。

一、基本的数据结构

intset 的结构定义很简单，有以下成员构成：

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

encoding 记录当前 intset 使用编码，有三个取值：

#define INTSET_ENC_INT16 (sizeof(int16_t)) #define INTSET_ENC_INT32 (sizeof(int32_t)) #define INTSET_ENC_INT64 (sizeof(int64_t))

length 记录整数集合中目前存储了多少个元素，contents 记录我们实际的数据集合，虽然我们看到结构体中给数组元素的类型定死成 int8_t，但实际上这个 int8_t 定义的毫无意义，因为这里的处理方式非常规的数组操作，content 字段虽然被定义成指向一个 int8_t 类型数据的指针，但实际上 redis 无论是读取数组元素还是新增元素进去都依赖 encoding 和 length 两个字段直接操作的内存。

基本数据结构还是非常的简单的，下面我们来看看它的一些核心方法。

二、核心 API 实现

1、初始化一个 intset

intset *intsetNew(void) {     intset *is = zmalloc(sizeof(intset));     is->encoding = intrev32ifbe(INTSET_ENC_INT16);     is->length = 0;     return is; }

可见，默认的 inset 配置是使用 INTSET_ENC_INT16 作为数据存储大小，并且不会为 content 数组初始化。常规的数组需要先预先确定数组长度，然后分配内存，继而通过 contents[x] 可以访问数组中任一元素。

但是，inset 这里是非常规式操作数组，encoding 字段定义了数组中每个元素实际类型，lenth 字段定义了数组中实际的元素个数，那么 contents[x] 是失效的，这种方式只会按照 int8_t 进行内存偏移，这种方式是拿不到正确的数据的，所以 redis 中通过 memcpy 按照 encoding 字段的值暴力直接偏移地址操作内存读取数据。

所以，这也是为什么 intset 初始化时不初始化 content 数组的原因所在，因为没有必要。而每当新增一个元素的时候都会去动态扩容原数组的长度以盛放下新插入进来的元素，扩容不会扩容很多，刚好一个新元素所占用的内存即可。具体的细节，我们接着看。

2、添加新元素

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {     //计算得到新插入的元素的编码     uint8_t valenc = _intsetValueEncoding(value);     uint32_t pos;     if (success) *success = 1;     //如果大于 intset 目前存储元素的编码大小     if (valenc > intrev32ifbe(is->encoding)) {         //触发 intset 升级         return intsetUpgradeAndAdd(is,value);     } else {         //二分搜索当前元素，如果元素已经存在会直接返回         //如果没找到元素，pos 的值就是该元素的位置索引         if (intsetSearch(is,value,&pos)) {             if (success) *success = 0;             return is;         }         //resize 集合，扩容一个元素的内存空间         is = intsetResize(is,intrev32ifbe(is->length)+1);         //移动 pos 后面的元素，以插入我们的新元素         if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);     }     //赋值     _intsetSet(is,pos,value);     is->length = intrev32ifbe(intrev32ifbe(is->length)+1);     return is; }

由此，我们应该知道为什么 intset 内的数据是有序且无重复的了，二分查找 O(logN)，但是 intset 插入一个元素却不是 O(logN)，因为有些情况会触发升级操作，或者极端情况下，会移动所有元素，时间复杂度达到 O(N)。

3、升级