【Redis】整数集合

Metadata

title: 【Redis】 整数集合
date: 2023-07-09 08:33
tags:
  - 行动阶段/完成
  - 主题场景/数据存储
  - 笔记空间/KnowladgeSpace/ProgramSpace/BasicsSpace
  - 细化主题/数据存储/Redis
categories:
  - 数据存储
keywords:
  - 数据存储/Redis
description: 【Redis】 整数集合

概述

当一个集合只包含整数元素，并且元素不多时，Redis 就会使用整数集合作为集合键的底层实现。

整数集合是集合键的底层实现之一。
整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型。
升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存。
整数集合只支持升级操作，不支持降级操作。

整数集合的实现

整数集合是 Redis 中用于保存整数值的集合抽象数据结构，可以保证集合有序不重复。每个intset.h/intset结构来表示一个整数集合：

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

length 属性记录了整数集合包含的元素数量，contents 是整数集合的底层实现。contents 存储元素的真实类型取决于 encoding，比如encoding==INT_ENC_INT16时，contents 数组中每个向都是 int16_t 类型的整数。可以为int16_t,int32_t或int64_t。

升级

当我们要将一个新元素添加至集合时，并且新元素的类型比现有集合类型都长时，整数集合就要升级。

步骤：

根据新元素类型，扩展数组空间，为新元素分配空间。
将底层数组现有所有元素都转为新元素相同类型，并将类型转换后的元素放到正确位置。
将新元素添加到底层数组。

由于每次向整数集合添加新元素都可能会引起升级，而每次升级都需要对底层数组中已有元素进行类型转换，所以添加的**时间复杂度为 O(N)**。

升级的好处

有两个好处，可以提升整数集合的灵活性，也能尽可能地节约内存。
C 语言是静态类型语言，一般数组中的元素类型都相同，使用升级可以不用担心类型兼容问题，提升灵活性。元素统一以最大类型存储，而不是都用int64_t，可节约内存。

降级

整数集合不支持降低，一旦升级就不能降级。

整数集合的时间复杂度

操作	时间复杂度
给定元素添加到/移出集合	O(N)
判断给定元素是否在集合	“由于有序,可用二分查找,复杂度为O(logN)”
取出给定索引元素	0(1)

整数集合API

函数	作用	时间复杂度
intsetNew	创建一个新的压缩列表	O(1)
intsetAdd	将给定元素添加到整数集合里面	O(N)
intsetRemove	从整数集合中移除给定元素	O(N)
intsetFind	检查给定值是否存在于集合	“因为底层数组有序,查找可以通过二分查找法来进行,所以复杂度为 0(logN)”
intsetRandom	从整数集合中随机返回一个元素	O(1)
intsetGet	取出底层数组在给定索引上的元素	O(1)
intsetLen	返回整数集合包含的元素个数	0(1)
intsetBlobLen	返回整数集合占用的内存字节数	O(1)