肇庆做网站,申请云应用wordpress,云南省城乡住房建设厅网站,电子商务网站建设试题及答案4、整数集合
整数集合#xff08;intset#xff09;是 Redis 用于保存整数值的集合抽象数据结构#xff0c; 可以保存 int16_t 、 int32_t 、 int64_t 的整数值#xff0c; 并且保证集合中不会出现重复元素。
实现较为简单#xff1a;
typedef struct intset {// 编码方…4、整数集合
整数集合intset是 Redis 用于保存整数值的集合抽象数据结构 可以保存 int16_t 、 int32_t 、 int64_t 的整数值 并且保证集合中不会出现重复元素。
实现较为简单
typedef struct intset {// 编码方式uint32_t encoding;// 集合包含的元素数量uint32_t length;// 保存元素的数组int8_t contents[];
} intset;
各个项在数组中从小到大有序地排列 并且数组中不包含任何重复项。
虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组 但实际上 contents 数组并不保存任何 int8_t 类型的值 —— contents 数组的真正类型取决于 encoding 属性的值
如果 encoding 属性的值为 INTSET_ENC_INT16 那么 contents 就是一个 int16_t 类型的数组 数组里的每个项都是一个 int16_t 类型的整数值 最小值为 -32,768 最大值为 32,767 。
如果 encoding 属性的值为 INTSET_ENC_INT32 那么 contents 就是一个 int32_t 类型的数组 数组里的每个项都是一个 int32_t 类型的整数值 最小值为 -2,147,483,648 最大值为 2,147,483,647 。
如果 encoding 属性的值为 INTSET_ENC_INT64 那么 contents 就是一个 int64_t 类型的数组 数组里的每个项都是一个 int64_t 类型的整数值 最小值为 -9,223,372,036,854,775,808 最大值为 9,223,372,036,854,775,807 。 升级
c语言是静态类型语言不允许不同类型保存在一个数组。这样第一灵活性较差第二有时会用掉不必要的内存
比如用long long储存1
为了提高整数集合的灵活性和节约内存我们引入升级策略。
当我们要将一个新元素添加到集合里 并且新元素类型比集合现有元素的类型都要长时 集合需要先进行升级。
分为三步进行
根据新元素的类型 扩展整数集合底层数组的空间大小 并为新元素分配空间。将底层数组现有的所有元素都转换成与新元素相同的类型 并将类型转换后的元素放置到正确的位上将新元素添加到底层数组里面。
因为每次添加新元素都可能会引起升级 每次升级都要对已有元素类型转换 所以添加新元素的时间复杂度为 O(N) 。
因为引发升级的新元素比原数据都长所以要么他是最大的要么他是最小的。我们把它放在开头或结尾即可。 降级
略略略不管你们信不信整数集合不支持降级操作。。我也不知道为啥
5、压缩列表 压缩列表是列表键和哈希键的底层实现之一。
当一个列表键只包含少量列表项并且列表项都是小整数或者短字符串redis就会用压缩列表做列表键底层实现。
压缩列表是 Redis 为了节约内存而开发的 由一系列特殊编码的连续内存块组成的顺序型sequential数据结构。
一个压缩列表可以包含任意多个节点entry 每个节点可以保存一个字节数组或者一个整数值。
具体实现 具体说一下entry
由三个部分组成
1、previous_entry_length:记录上一个节点的长度这样我们就可以从最后一路遍历到开头。
2、encoding记录了content所保存的数据类型和长度。具体编码不写了不重要
3、content保存节点值可以是字节数组或整数。具体怎么压缩的等我搞明白再补 连锁更新
前面说过 每个节点的 previous_entry_length 属性都记录了前一个节点的长度
如果前一节点的长度 254 KB 那么 previous_entry_length 需要用 1 字节长的空间如果前一节点的长度254 KB 那么 previous_entry_length 需要用 5 字节长的空间
现在 考虑这样一种情况 在一个压缩列表中 有多个连续的、长度介于 250 字节到 253 字节之间的节点 这时 如果我们将一个长度大于等于 254 字节的新节点 new 设置为压缩列表的表头节点。。。。
然后脑补一下就会导致连锁扩大每个节点的空间对吧e(i)因为e(i-1)的扩大而扩大i1也是如此以此类推。。。 删除节点同样会导致连锁更新。
这个事情只是想说明一个问题插入删除操作的最坏时间复杂度其实是o(n*n)因为每更新一个节点都要o(n)。
但是也不用太过担心因为这种特殊情况并不多见这些命令的平均复杂度依旧是o(n)。
