redis 从0到1完整学习（五）：集合 IntSet 数据结构

文章目录

1. 引言
2. redis 源码下载
3. IntSet 数据结构
4. 参考

1. 引言

前情提要：
《redis 从0到1完整学习（一）：安装&初识 redis》
《redis 从0到1完整学习（二）：redis 常用命令》
《redis 从0到1完整学习（三）：redis 数据结构》
《redis 从0到1完整学习（四）：字符串 SDS 数据结构》
本文主要结合源码来介绍 Redis IntSet 的数据结构

2. redis 源码下载

Redis 源码可以点击这里下载，方便查看其中定义的一些数据结构。
在这里插入图片描述

3. IntSet 数据结构

Redis 的 IntSet 是一个整数 set 数据结构，用于存储一系列整数值。它具有以下特点：

有序性：IntSet 中的元素按照升序排列。
唯一性：IntSet 中的元素是唯一的，不会出现重复的值。
空间效率：IntSet 使用紧凑的存储方式，元素之间没有额外的空间开销。

Redis 的 IntSet 数据结构常用于需要存储和快速查找整数集合的场景。它提供了一组操作命令，可以对 IntSet 进行插入、删除、查找等操作。
在这里插入图片描述
encoding 表示编码方式，支持16位、32位、64位整数；
length 表示元素的个数；
contents 整数数组，保存数据。

下面从源码来分析，Intset 是如何自动升级编码方式到合适的大小的：

// 插入到 IntSet 中
intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {// 获取当前值需对应的编码uint8_t valenc = _intsetValueEncoding(value);uint32_t pos;if (success) *success = 1;if (valenc > intrev32ifbe(is->encoding)) {// 如果超出了之前的编码，则需要调整之前的编码跟当前一致return intsetUpgradeAndAdd(is,value);} else {// 查找当前值应该放置的位置，如果返回1，表示已经存在一样的值if (intsetSearch(is,value,&pos)) {if (success) *success = 0; // 如果return is;}// 数组扩容 + 移动原先的元素is = intsetResize(is,intrev32ifbe(is->length)+1);if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);}// 插入新元素到指定位置_intsetSet(is,pos,value);// 元素长度+1is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {uint8_t curenc = intrev32ifbe(is->encoding);uint8_t newenc = _intsetValueEncoding(value);int length = intrev32ifbe(is->length);// 出现了新的编码，要么是数字太小了（负数），要么是数字太大（正数）int prepend = value < 0 ? 1 : 0;// 重设编码以及sizeis->encoding = intrev32ifbe(newenc);is = intsetResize(is,intrev32ifbe(is->length)+1);// 从后往前倒序将元素挪到指定位置while(length--)_intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));// prepend=1表示为负数，最小的，应该放置到队首if (prepend)_intsetSet(is,0,value);else // prepend=0表示为正数，最大的，应该放置到队尾_intsetSet(is,intrev32ifbe(is->length),value);// 数组长度+1is->length = intrev32ifbe(intrev32ifbe(is->length)+1);return is;
}// 计算 value 插入的位置 pos，同时返回0表示未找到一样的值，1表示找到一样的值
static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;int64_t cur = -1;/* The value can never be found when the set is empty */if (intrev32ifbe(is->length) == 0) {if (pos) *pos = 0;return 0;} else {// 比最大的还大，比最小的还小，则可以直接返回要插入的位置if (value > _intsetGet(is,max)) {if (pos) *pos = intrev32ifbe(is->length);return 0;} else if (value < _intsetGet(is,0)) {if (pos) *pos = 0;return 0;}}// 常见的二分法找值while(max >= min) {mid = ((unsigned int)min + (unsigned int)max) >> 1;cur = _intsetGet(is,mid);if (value > cur) {min = mid+1;} else if (value < cur) {max = mid-1;} else {break;}}// 找到了，则返回1if (value == cur) {if (pos) *pos = mid;return 1;} else { // 没找到，返回要插入的地方if (pos) *pos = min;return 0;}
}