Redis源码解析：数据结构详解-intset

介绍

intset是Redis中set的底层数据结构，当集合中全为整数，并且元素数据不多时，会用intset来实现set，inset和ziplist一样，都是一块连续的存储空间

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

contents：contents数组是整数集合的底层实现，元素按照从小到大的顺序存在数据中，并且数组中不包含重复的项。

contents虽然声明为int8_t类型的数组，但是并不保存任何int8_t类型的值，contents的数据类型取决于encoding属性的值。

encoding：编码格式，有如下三种INTSET_ENC_INT16，INTSET_ENC_INT32，INTSET_ENC_INT64可选值

// 16位，2个字节，表示范围-32,768~32,767
#define INTSET_ENC_INT16 (sizeof(int16_t))
// 32位，4个字节，表示范围-2,147,483,648~2,147,483,647
#define INTSET_ENC_INT32 (sizeof(int32_t))
// 64位，8个字节，表示范围-9,223,372,036,854,775,808~9,223,372,036,854,775,807
#define INTSET_ENC_INT64 (sizeof(int64_t))

当encoding为INTSET_ENC_INT16，contents为一个int16_t类型的数组，数组中的每一项都是int16_t类型

当encoding为INTSET_ENC_INT32，contents为一个int32_t类型的数组，数组中的每一项都是int32_t类型

当encoding为INTSET_ENC_INT64，contents为一个int64_t类型的数组，数组中的每一项都是int64_t类型

升级

当我们往一个set中放数字1，3，10时，数据结构如图所示，此时encoding为INTSET_ENC_INT16。当新增一个数字65535时，encoding为INTSET_ENC_INT16此时并不能表示65535，但是INTSET_ENC_INT32可以，此时原先的int16_t类型数组，会被升级为int32_t类型数组，原来的int16_t类型的数字也被升级为int32_t。同理当一个放入一个范围不在encoding为INTSET_ENC_INT32表示范围的数字，数组会被升级为int64_t类型。

整数集合升级并放置新元素的过程如下

1. 根据新元素的类型，扩张底层底层数组的大小
2. 将数组原来的元素都转换成与新元素相同的类型，并将原来的元素放到正确的位置上
3. 将新元素放到底层数组中

画个图详细演示一下

1. 假设原来的数组中只有1，3，10这3个数组，此时数据类型为int16_t就可以表示
2. 放入一个新元素65535，int16_t类型表示不了了，所以得用int32_t来表示，数组中的其他元素也要升级为int32_t
3. 原先数组的大小为3（个数）*2（每个元素占用字节数）=6字节，升级后的数组为4（个数）*4（每个元素占用字节数）=16字节，在元素数组的后面申请10字节的空间
4. 然后将原来数组中的元素从大到小依次移动到扩容后数组正确的位置上。例如原先10的起始位置为2（下标） * 2（大小）=4字节，结束位置为3 * 2=6字节。则现在10的位置为2 （下标）* 4（大小）=8字节，结束位置为3 * 4=12字节
5. 将新添加的元素放到扩容后的数组上

为什么要从大到小放呢？
从大到小放不会造成数据覆盖，从小到大放会造成数据覆盖

如果确定新添加的元素放到哪个位置？
既然引发了扩容，那么当前元素一定比现在所有的元素都小，或者比现在所有的元素都大。所以如果新增加的元素<0，则把放在数组的第一个，否则把它放到数组的最后一个

为什么要有升级的过程？直接用int64_t存不行吗？
当然可以啊，这不是基于内存的考虑，能尽量少占用空间就少占用空间，只有真正需要的时候才用int64_t存

整数集合会降级吗？
整数集合不会进行降级操作，一旦对整数进行了升级，编码就一直会保持升级后的状态，以上面的例子来说，当把65535删除后，编码值依然为INTSET_ENC_INT32

set的实现

底层实现为intset时

底层实现是hashtable时

参考博客

[1]https://www.jianshu.com/p/f0d52a80c358
[3]https://zhuanlan.zhihu.com/p/144210551