用符号做照片的网站,滨江网站建设制作,南山住房和建设局网站,淘宝pc端官网五、整数集合#xff08;Intset#xff09;
整数集合是 Redis 中 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素#xff0c;并且元素数量不大时#xff0c;就会使用整数集合这个数据结构作为底层实现。整数集合通过紧凑的内存布局和升级机制#xff0c;实现了…五、整数集合Intset
整数集合是 Redis 中 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素并且元素数量不大时就会使用整数集合这个数据结构作为底层实现。整数集合通过紧凑的内存布局和升级机制实现了高效的整数存储和操作。
1. 结构设计
整数集合本质上是一块连续的内存空间其结构定义如下
typedef struct intset {// 编码方式uint32_t encoding;// 集合包含的元素数量uint32_t length;// 保存元素的数组int8_t contents[];
} intset;可以看到保存元素的容器是一个 contents 数组虽然 contents 被声明为 int8_t 类型的数组但是实际上 contents 数组并不保存任何 int8_t 类型的元素contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。比如
如果 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。
2. 升级操作
整数集合的一个重要特性是支持升级操作。当将一个新元素加入到整数集合中如果新元素的类型例如 int32_t比集合中现有所有元素的类型例如 int16_t都要长时整数集合需要先进行升级操作。升级操作包括扩展 contents 数组的空间大小和维持集合的有序性。
升级示例
假设一个整数集合包含三个 int16_t 类型的元素
contents: [1, 2, 3] // 类型int16_t现在我们将一个新元素 65535 加入到集合中由于这个新元素需要用 int32_t 类型来保存因此需要进行升级操作 扩展空间首先需要为 contents 数组扩容在原本空间的大小之上再扩容多 80 位4x32 - 3x16 80这样就能保存下 4 个 int32_t 类型的元素。 转换类型扩容完 contents 数组空间大小后需要将之前的三个 int16_t 类型的元素转换为 int32_t 类型并将转换后的元素放置到正确的位置上并且需要维持底层数组的有序性不变。
升级后的 contents 数组如下
contents: [1, 2, 3, 65535] // 类型int32_t升级的好处
节省内存如果直接使用 int64_t 类型的数组来保存所有元素虽然可以保存不同类型的整数但会造成内存浪费。例如当元素都是 int16_t 类型时使用 int64_t 类型数组会浪费大量内存。灵活性通过升级机制整数集合可以根据需要动态调整数组类型既能节省内存又能支持更大范围的整数。
不支持降级
值得注意的是整数集合不支持降级操作。一旦数组类型升级到更大的整数类型就不会再降级回较小的类型。这是为了简化实现和避免降级过程中可能产生的复杂性。
3. 操作实现
整数集合支持多种操作包括插入、删除、查找等。以下是一些常见操作的实现示例
插入操作
插入新元素时首先检查新元素的类型是否需要升级。如果需要升级先进行升级操作然后将新元素插入到正确的位置维持数组的有序性。
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 {if (intsetSearch(is, value, pos)) {if (success) *success 0;return is;}// 插入操作is intsetResize(is, intrev32ifbe(is-length) 1);if (pos intrev32ifbe(is-length)) {memmove(intsetGet(is, pos 1), intsetGet(is, pos),(intrev32ifbe(is-length) - pos) * intrev32ifbe(is-encoding));}intsetSet(is, pos, value);is-length intrev32ifbe(intrev32ifbe(is-length) 1);}return is;
}查找操作
查找元素时通过二分查找算法在有序数组中高效地查找目标元素的位置。
uint8_t intsetSearch(const intset *is, int64_t value, uint32_t *pos) {int64_t cur;int min 0, max intrev32ifbe(is-length) - 1, mid -1;if (intrev32ifbe(is-length) 0) {if (pos) *pos 0;return 0;} else {while (max min) {mid (min max) 1;cur intsetGet(is, mid);if (value cur) {min mid 1;} else if (value cur) {max mid - 1;} else {break;}}if (value cur) {if (pos) *pos mid;return 1;} else {if (pos) *pos min;return 0;}}
}删除操作
删除元素时首先查找到目标元素的位置然后移除该元素并调整数组大小。
intset *intsetRemove(intset *is, int64_t value, int *success) {uint8_t valenc _intsetValueEncoding(value);uint32_t pos;if (success) *success 0;if (valenc intrev32ifbe(is-encoding) intsetSearch(is, value, pos)) {uint32_t len intrev32ifbe(is-length);// 移除操作if (pos (len - 1)) {memmove(intsetGet(is, pos), intsetGet(is, pos 1),(len - pos - 1) * intrev32ifbe(is-encoding));}is intsetResize(is, len - 1);is-length intrev32ifbe(len - 1);if (success) *success 1;}return is;
}4. 使用示例
以下是一些使用 Redis 整数集合的示例展示了如何利用整数集合进行数据的存储和操作。
插入数据
SADD myset 1
SADD myset 2
SADD myset 3获取数据
SMEMBERS myset
# 1) 1
# 2) 2
# 3) 3删除数据
SREM myset 2
SMEMBERS myset
# 1) 1
# 2) 3结论
通过上述解析我们可以更好地理解整数集合的设计思想和实现原理从而在实际开发中更好地利用整数集合提供的优势。在 Redis 中整数集合通过紧凑的内存布局和动态升级机制实现了高效的整数存储和操作。了解这些优化策略可以帮助我们在实际应用中更好地利用 Redis 的性能和功能。
