redis数据结构-整数集合

一般集合键只保存整数且集合的大小不大时，采用整数集合作为其底层实现

结构

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

• contents作为整数集合的底层实现，每个元素都是contents数组的一个项，各个节点从小到大排列，并且不会重复
• contents的项的大小不一定为uint8_t，具体是根据encoding的值来决定

整数集合的升级

• 当整数集合中的添加的元素大于现有所有元素的类型都要长时，会将contents中元素的类型进行升级
• 步骤：
  • 首先会根据新加入元素的大小为现有的元素重新分配数组代销
  • 将原来的元素，通过类型转之后，放入新数组的对应位置
  • 将新元素添加入新集合
• 因为每次新添加元素时，可能会发生升级，会遍历所有的元素进行类型转换，所有时间复杂度为O(n)

升级带来的好处

• 提高了灵活性，一般数组中我们都会存储相同类型的int值，集合添加元素时，我们不需要关心是插入uint64还是uint32，intset自动适类型的转化
• 节省了内存空间：当数组中不存在uint64的数时，没有比要把数组初始化为uint64-t类型，这样节约了空间

降级

整数集合不支持降级，整数一旦进行升级之后，不能进行降级

重点回顾