在 Redis 中,如果有用过它的 set 集合,底层的实现整数集合。
整数集合,就是只能包括整数值的元素,我们试着创建一个整数集合

创建一个整数集合
创建一个整数集合

它的结构很简单,具体的源码在 src/intset.h 文件中

typedef struct intset {
    uint32_t encoding;  // 编码类型
    uint32_t length;    // 元素数量
    int8_t contents[];  // 保存元素数组
} intset;

contents 数组中,集合的每个元素,都对应着数组的一个元素,
他们按照从小到大的顺序,有序的排列着,并且每个元素在数组中都是唯一的。
length 记录了集合中现有元素的数量,可以 O(1)的方式,每次快速
返回 contents 数组的数量。encoding 属性是值,contents 数组
中的每个元素,都是以什么类型存的,共有三种类型:

/* Note that these encodings are ordered, so:
 * INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))  // int16, -2^15 ~ 2^15 - 1 
#define INTSET_ENC_INT32 (sizeof(int32_t))  // int32, -2^31 ~ 2^31 - 1  
#define INTSET_ENC_INT64 (sizeof(int64_t))  // int64, -2^63 ~ 2^63 - 1

一个拥有5个int16类型的整数集合

集合的类型转换

当我们需要往现有集合中增加插入一个整数的时候,如果要添加的整数的大小不满足
现有集合的编码类型,则需要对现有集合的每个元素转换类型。具体步骤:

  1. 根据新元素的类型,扩展整数集合的空间大小;
  2. 将现有元素类型,转换为集合中最大数所属类型,保持原有顺序,再添加新元素至合适位置;
  3. 修改 contents 数组长度 length 和 编码类型 encoding

例如,有一个集合,包含3个元素,分别是 1,2,3,集合的 encoding 属性
INTSET_ENC_INT16,所占空间为 3 * 16 = 48 位,6个字节。现在要将
65535 添加到集合中,按照上面说的步骤:

  • 首先,因为 65535 超过 INTSET_ENC_INT16,属于 INTSET_ENC_INT32 范围内,
    所以,需要对空间进行重新分配,新的空间需要 4 * 32 = 128 位,16个字节;
  • 接着,从 96 ~ 127 位,留给最后一个 65535 元素,剩下的三个元素,从 95 位开始,
    96 - 32 = 64 位,保存3,从 63 位开始至 64 - 32 = 32 位,保存2,剩下的
    0 至 31 位,保存 1,最后将要插入的 65535 放入最先预留的 96 - 127 位;
  • length 改为4, encoding 改为 INTSET_ENC_INT32

至此,类型转换就完成了。整数集合,不会将高位的 encoding,改为低位,如果说,
因为增加元素 encoding 的类型改为高位,即使后来再删除元素,encoding 始终
就是增加时修改的值。