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

  1. 云栖社区>
  2. 博客>
  3. 正文

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

杰克.陈 2018-11-13 21:02:00 浏览504
展开阅读全文
原文:redis 系列8 数据结构之整数集合

一.概述

  整数集合(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类型。

  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位空间,如下图所示:

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

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

四. 升级的好处

  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类型,如下图所示:

 

六. 整数集合API

函数

作用

intsetNew

创建一个新的压缩列表

intsetAdd

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

intsetRemove

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

intsetFind

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

intsetRandom

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

intsetGet

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

intsetLen

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

intsetBloblen

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

  

网友评论

登录后评论
0/500
评论
杰克.陈
+ 关注