Redis的集合相当于Java中的Hashset.内部键值无序,唯一.内部实现相当于一个特殊字典,字典的value都是null.集合set类型底层编码包括hashTable和intset.
使用整数集合intset实现set的条件:
- 存储数据均为整数
- 存储数据元素个数小于512个
如果不能同时满足,这是用dict来存储集合的数据
hashTable在上文已解释其结构
接下来我们聊聊intset
intset结构体
typedef struct intset {
uint32_t encoding;
// length就是数组的实际长度
uint32_t length;
// contents 数组是实际保存元素的地方，数组中的元素有以下两个特性：
// 1.没有重复元素
// 2.元素在数组中从小到大排列
int8_t contents[];
} intset;
// encoding 的值可以是以下三个常量的其中一个
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))
intset的查询
intset是有序集合,查找元素的复杂度为O(logN)(采用二分法),但插入不一定为O(logN),可能涉及升级操作. 例:集合中存的是int16_t的整数,这时要插入一个int31_t,那么为了维持集合中的数据类型统一.其他所有的数据都会转成int32_t类型,涉及内存重新分配,插入的复杂度为O(N).
intset不支持降级操作
