关于后端:Redis数据结构五之整数集合

本文首发于公众号：Hunter 后端
原文链接：Redis 数据结构五之整数汇合

整数集（intset）是汇合键的底层实现之一，当一个汇合只蕴含整数值元素，并且这个汇合的元素数量不多时，Redis 就会应用整数汇合作为汇合键的底层实现。

整数汇合能够保留类型为 int16_t，int32_t，int64_t 的整数值，并且保障汇合中不会呈现反复元素。

1、整数汇合

以下是整数汇合的构造：

typedef struct intset{
    // 编码方式
    uint32_t encoding;
    
    // 汇合蕴含的元素数量
    uint_32_t length;
    
    // 保留元素的数组
    int8_t contents[];}

其中，encoding 属性的值为 INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64，别离示意 contents 数组里存储的整数类型是 int16_t，int32_t，int64_t。

当 encoding 的值为 INTSET_ENC_INT16，contents 数组里每个项都是 int16_t 类型的整数值，范畴在 -215 ～ 2 15 – 1 之间，也就是 -32768 ～ 32767

当 encoding 的值为 INTSET_ENC_INT32，contents 数组里每个项都是 int32_t 类型的整数值，范畴在 -231 ～ 2 31 – 1 之间

当 encoding 的值为 INTSET_ENC_INT64，contents 数组里每个项都是 int64_t 类型的整数值，范畴在 -263 ～ 2 63 – 1 之间

length 属性记录的是整数汇合中蕴含的元素数量，也就是 contents 数组的长度。

contents 数组中的数值按值的大小从小到大有序排列，并且不蕴含反复项。

contents 数组中蕴含的元素类型都是一样的，比方以后数组中元素的类型是 int16_t，如果要向其中插入的整数值的类型是 int32_t，那么 contents 数组就要将 contents 数组的元素类型先降级再插入，这个就波及降级的操作。

2、降级

当咱们要增加到整数汇合中的元素的类型比现有所有元素类型都要长时，整数汇合须要进行降级（upgrade）操作，而后能力将新元素插入整数汇合中。

降级并增加新元素共分为三步进行：

1. 依据新元素类型，扩大整数汇合底层数组的空间大小，并为新元素调配空间
2. 将底层数组所有元素转换成与新元素雷同的类型，并将类型转换后的元素放在正确的位上，且维持其有序性不变
3. 将新元素增加到底层数组外面

对于整数的三种类型，int16_t，int32_t，int64_t，每种类型的数据占用的位数别离是 16，32，64

假如以后 contents 数组有三个元素：1，2，3。类型是 int16_t，对应的元素和位数展现如下：

接下来须要增加一个整数，65535，类型是 int32_t，那么就须要先调配额定的空间，新调配的空间长度等于元素总数 新类型的位数 – 原有空间长度 = 4 32 – 48 = 80：

而后别离将元素 3，2，1 挪动到对应的空间内，再将新元素 65535 放在对应的空间上：

而后将整数汇合 encoding 属性的值从 INTSET_ENC_INT16 改为 INTSET_ENC_INT32，length 属性的值从 3 改为 4。

3、降级的益处

为整数汇合应用降级策略有两个益处，一个是晋升整数汇合的灵活性，一个是尽可能的节约内存

因为 C 语言是动态类型语言，通常不会将两种不同类型的值放在一个数据结构里，然而整数汇合能够通过主动降级底层数组来适应新元素，所以咱们能够随便将 int16_t，int32_t，int64_t 类型的整数增加到汇合中，而不用放心呈现类型谬误

另外，要让数组能够同时保留 int16_t，int32_t，int64_t 这三种类型的整数，最简略的形式是间接应用 int64_t 类型的数组去保留数据，但这样的话如果元素都是 int16_t，int32_t 类型的值，那么会呈现节约内存的状况。

因而当初降级策略能够尽量节约内存。

4、降级

整数汇合不反对升高操作，一旦对数组进行了降级，编码就会始终放弃降级后的状态。

比方后面的数组 1，2，3，65535，如果咱们删除了 65535，整数汇合还是会维持原有 INTSET_ENC_INT64 的编码，底层数组也还是 int64_t 类型的。

如果想获取更多相干文章，可扫码关注浏览：