整数集合

  • 是Redis保存整数值的集合抽象数据结构，可以保存类型为int16_t，int32_t，int64_t的整数值，并且保证集合中不会出现重复元素

  • 整数集合的定义

    1
    2
    3
    4
    5
    6
    7
    8
    typedef struct intset {
    		// 编码方式
        uint32_t encoding;
    		// 集合包含的元素数量
        uint32_t length;
    		// 保存元素的数组
        int8_t contents[];
    } intset;

  • 属性定义

    • contents
      • contents数组是整数集合的底层实现，每个item按值从小到大有序排列，而且不包含重复项
    • length
      • 记录整数集合的元素数量，即contents数组的长度
    • encoding
      • 决定了contents数组存放什么类型的item

  • 升级

    • 将一个新元素添加到整数集合，如新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，upgrade，然后才能将新元素添加到整数集合
    • 步骤
      • 根据新元素的类型，扩展数组空间，并且为新元素分配空间
      • 将旧元素都转换为与新元素相同的类型，并且将旧元素放置到正确的位置上，过程中要维持有序性不变
      • 将新元素添加到数组中
    • 向整数集合添加新元素的时间复杂度为O（N）
    • 升级的好处
      • 提升灵活性
      • 节约内存

  • 降级

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