欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

redis 系列8 数据结构之整数集合

程序员文章站 2022-09-14 16:58:56
一.概述 整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素,并且这个集合元素数量不多时, Redis就会使用整数集合作为集合键的底层实现。下面创建一个只包含5个元素的集合键,并且集合中所有元素都是整数值,那么这个集合键的底层实现就会是整数集合。 接着添加非整数值,集合键的 ......

一.概述

  整数集合(intset)是集合键的底层实现之一, 当一个集合只包含整数值元素,并且这个集合元素数量不多时, redis就会使用整数集合作为集合键的底层实现。下面创建一个只包含5个元素的集合键,并且集合中所有元素都是整数值,那么这个集合键的底层实现就会是整数集合。 接着添加非整数值,集合键的底层实现就会是hashtable。

127.0.0.1:6379> sadd numbers 1 3 5 7 9 
(integer) 5
127.0.0.1:6379> object encoding numbers
"intset"
127.0.0.1:6379> sadd numbers 'one'
(integer) 1
127.0.0.1:6379> object encoding numbers
"hashtable"

 

二. 整数集合实现

  整数集合是redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t, int32_t, int64_t的整数值,并且保证集合中不会出现重复元素。数据集合定义如下:

// 每个intset.h/intset结构表示一个整数集合
           typedef struct intset
        {
            //编码方式
            uint32_t encoding;
            //集合包含的元素数量
             uint32_t  length;
            //保存元素的数组
             int8_t contents[];
        }intset;

  (1) contents数组是整数集合的底层实现,整数集合的每个元素都是contents数组的一个数组项(item),各个项在数组中按值从小到大有序排列,并且数组中不包含重复项。如下面脚本:

127.0.0.1:6379> sadd record 5 3 4 5 6 0
(integer) 5
127.0.0.1:6379> smembers record
1) "0"
2) "3"
3) "4"
4) "5"
5) "6"

  (2) length属性记录了整数集合包含的元素数量,也即是contents数组的长度。虽然contents属性声明为int8_t类型的数组,但实现上contents数组并不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值。

  a. 如果encoding 属性的值为intset_enc_int16,那么contents就是一个int16_t类型的数组,数组里的每个项都是一个int16_t类型的整数值(范围在 -32768 ~ 32767)。如下图encoding属性的值有5个整数型,根据这些整数值得出encoding为int16_t类型。

redis 系列8 数据结构之整数集合

  b. 如果encoding属性的值为intset_enc_int32, 那么数组里每个项就是一个int32_t类型的整数值(范围在 -2147483648 ~ 2147483647)。还有encoding属性的值为intset_enc_int64类型的,数组里每个项取取值范围更大。

  需要注意的是:假设contents数组保存的值为2147483647, 1,2,3 四个整数值。 但只有第一个整数值需要用int32_t类型来保存,而其它三个值可以用int16_t类型来保存。不过根据整数集合的升级规则,当一个底层的int16_t数组的整数集合添加一个int64_t类型的整数值时,整数集合中所有元素都会被转换成int64_t类型。 所以contents数组保存的整数值都是int64_t类型的。

 

三. 升级

   当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级,然后才能将新元素添加到整数集合中。假设:集合中包含三个int16_t类型的元素,值分别是1,2,3 。因为每个元素都占用16位空间,所以整数集合底层数组的大小 为3 * 16 =48位。现将int32_t的数值65535添加进去,这里程序需要对整数集合进行升级。

  升级整数集合并添加新元素共分三步进行:

    (1) 根据新元素的类型,扩展整数集合底层数组的空间大小 ,并为新元素分配空间。分配空间后,现在整数集合4个元素的底层数组大小为4 *32 =128位, 此时前三位还是48位空间,如下图所示:

redis 系列8 数据结构之整数集合

    (2) 将底层数组现有的所有元素都转换成与新元素相同的类型(需要从int16_t 转成int32_t所需的空间) ,转换后元素位置有序不变,如下图所示:

redis 系列8 数据结构之整数集合

    (3) 将新元素添加到底层数组里面,如下图所示:

redis 系列8 数据结构之整数集合

四. 升级的好处

  4.1 提升灵活性

    为了避免类型错误,通常不会将两种不同类型的值放在同一个数据结构里面,通过升级处理可以随意地将int16_t, int32_t, , int64_t 类型的整数添加到集合中,而不必担心出现类型错误。

       4.2 节约内存

    要让一个数组可以同时保存int16_t,int32_t, , int64_t三种类型的值,最简单的做法就是直接使用int64_t类型的数组作为整数集合的底层实现,不过这样浪费内存空间。

 

五.   降级

  整数集合不支持降级操作,一旦对数组进行了升级,编码就会一直保持升级后的状态。即使集合里只有一个需要使用int64_t类型的元素被删除了,整数集合的编码仍然会维持intset_enc_int64, 底层数组也仍然会是int64_t类型,如下图所示:

redis 系列8 数据结构之整数集合

 

六. 整数集合api

函数

作用

intsetnew

创建一个新的压缩列表

intsetadd

将给定元素添加到整数集合里面

intsetremove

从整数集合中移除给定元素

intsetfind

检查给定值是否存在于集合

intsetrandom

从整数集合中随机返回一个元素

intsetget

取出底层数组在给定索引上的元素

intsetlen

返回整数集合包含的元素个数

intsetbloblen

返回整数集合占用的内存字节数

  

上一篇: 磁悬浮兽

下一篇: 我的小舅是头驴