Redis数据结构：整数集合

2015-02-13 23:12 Redis redis , 数据结构

Redis数据结构：整数集合

整数集合是集合键采用的数据结构之一，它有两个特性：

有序：集合的元素从小到大排列。
元素唯一：集合中的元素不允许重复。

但它的底层其实是基于数组来实现的，所以它的插入删除时间复杂度为O(n)（插入要保证数组有序和唯一），查找为O(log n)（使用二分查找）。数据结构定义为：


xxxxxxxxxx
typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

encoding决定了元素的数据类型（int16_t、int32_t、int64_t之一）

升级

整数集合要面对一个很严肃的问题，如果集合元素类型在全是int16_t的情况下，要插入一个int32_t类型，这时该怎么做呢？这就牵涉到了整数集合的升级，所谓升级就是把元素类型提升到更高一级，比如int16_t提升到int32_t。

升级整数集合并添加新元素共分为三步进行：

根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
将新元素添加到底层数组里面。

降级

整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。

整数集合API

函数	作用	时间复杂度
`intsetNew`	创建一个新的整数集合。	O(1)
`intsetAdd`	将给定元素添加到整数集合里面。	O(N)
`intsetRemove`	从整数集合中移除给定元素。	O(N)
`intsetFind`	检查给定值是否存在于集合。	因为底层数组有序，查找可以通过二分查找法来进行，所以复杂度为 O(\log N) 。
`intsetRandom`	从整数集合中随机返回一个元素。	O(1)
`intsetGet`	取出底层数组在给定索引上的元素。	O(1)
`intsetLen`	返回整数集合包含的元素个数。	O(1)
`intsetBlobLen`	返回整数集合占用的内存字节数。	O(1)

参考

书籍《 Redis设计与实现》