装修平台网站排名前十名,修改wordpress后台路径,企业推广ppt模板,设计公司网站模板前言 整数集合(intset)是集合键的底层实现之一#xff0c;当一个集合只包含整数值元素#xff0c;并且这个集合的元素数量不多时#xff0c;Redis就会使用整数集合作为集合键的底层实现。
一. 整数集合的实现 1.1 结构 整数集合(intset)是Redis用于保存整数值的集合抽象数据…前言 整数集合(intset)是集合键的底层实现之一当一个集合只包含整数值元素并且这个集合的元素数量不多时Redis就会使用整数集合作为集合键的底层实现。
一. 整数集合的实现 1.1 结构 整数集合(intset)是Redis用于保存整数值的集合抽象数据结构它可以保存类型为int16_tint32_t或者int64_t的整数值并且保证集合中不会出现重复元素。 每个intset.h/intset结构表示一个整数集合
typedef struct intset {//编码方式uint32_t encoding;//集合中包含元素的个数uint32_t length;//保存元素的数组int8_t contents[];
} intset; content数组是整数集合的底层实现整数集合的每一个元素都是contents数组的一个数组项。各个项在数组中按值的大小从小到大有序地排列并且数组中不包含任何重复项。 length属性记录了整数集合包含的元素数量也即是contents数组长度。 虽然intset结构contents属性声明为int8_t类型的数组。但是实际上contents数组并不保持任何int8_t类型的值。contents数组的真正类型取决于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类型的整数值。 下图展示了一个encoding为INTSET_ENC_INT64length等于4的整数集合。contents数组按从小到大的顺序保存集合中的四个元素。因为每一个元素是int64_t类型的整数值所以contents数组大小为sizeof(int64_t) * 4 64 * 4 256位。 虽然contents数组保存的四个整数值中只有-2675256175807981027真正需要int64_t类型来进行保存而其他的134可以使用int16_t类型保存。不过根据整数集合的升级规则当向一个底层位int16_t数组的整数集合添加一个int64_t类型的整数值时整数集合中的所有元素都会被转化成int64_t类型。 1.2 升级 每当我们要将一个新元素添加到整数集合中并且新元素的类型比整数集合现有的所有元素类型都要长时整数集合需要先进行升级(upgrade)然后才能将新元素添加到整数集合中。 升级步骤
根据新元素类型扩展整数集合底层数组的空间大小并为新元素分配空间。将底层数组现有元素都转化成与新元素相同的类型并将类型转化后的元素放置到正确位置上。而在放置元素过程中需要维持底层数组有序性不变。将新元素添加到底层数组里。 举个例子 现在有一个INTSET_ENC_INT16编码的整数集合集合中包含三个int16_t类型的元素。纵隔占16*348位。 现在要将类型int32_t的整数值65535添加到整数集合中。因为65535的类型int32_t比整数集合中的所有元素都长所以需要对整数集合进行升级。 升级首先要做的是根据新类型长度以及集合中元素数量(包括新元素)对底层数组空间进行重新分配。 现在整数集合中又四个元素类型需要升级位int32_t需要空间32 * 4 128位如下图。虽然程序对底层数组进行了空间重新分配但是数组中原有的三个元素123类型仍然是int16_t。这些元素还是保存在数组contents的前48位。 所以程序接下来需要做的是将原来的三个元素转化成int32_t类型。并且将转化后的元素放置到正确的位上并且需要维持底层数组的有序性。 首先因为元素3在12365535四个元素中排第三。所以它被移动到contents数组的索引2的位置上也就是数组64位至95位的空间内。 接着因为元素2在12365535四个元素中排第二。所以它被移动到contents数组的索引1的位置上也就是数组32位至63位的空间内。 之后 因为元素1在12365535四个元素中排第一。所以它被移动到contents数组的索引0的位置上也就是数组0位至31位的空间内。 然后 因为元素65535在12365535四个元素中排第四。所以它被移动到contents数组的索引3的位置上也就是数组96位至127位的空间内。 最后程序将encoding属性值从INTSET_ENC_INT16修改为INTSET_ENC_INT32并将length属性值从3修改为4。 因为每次向整数集合中添加新元素可能会引起升级每次升级都需要对底层数组中已有元素进行类型转换所以向整数集合添加新元素的时间复杂度为O(N)。 升级后新元素的摆放位置 因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大。所以这个新元素要么大于所有现有元素要么小于所有现有元素。 在新元素小于所有现有元素的情况下新元素会被放置在底层数组的最开头(索引为0) 在新元素大于所有现有元素的情况下新元素会被放置在底层数组的最末尾(索引为length-1) 1.3 升级的好处 整数集合的升级策略有两个好处一个是提升整数集合的灵活性二是尽可能地节约内存。
提升灵活性 因为C语言是静态类型语言为了避免类型错误我们一般不会将两种不同类型地值放在同一个数据结构里面。例如我们只会用int16_t类型地数组来保存int16_t类型的值只使用int32_t类型的数组来保存int32_t类型的值。 因为整数集合可以通过自动升级底层数组来适应新元素我们可以随意将int16_tint_32_t或int64_t类型的整数添加到集合中而不用担心类型错误。
节约内存 让一个数组既能保存int16_tint32_t或者int64_t类型的值最简单的做法就是直接使用int64_t类型的数组作为整数集合底层数组的实现。但是这样一来即使添加到整数集合里面的都是int16_t类型的值或者int32_t类型的值数组都会需要用int64_t类型来保存从而出现浪费内存的问题。 而整数集合的做法既可以让集合同时保存三个类型的值又可以确保升级操作只会在有需要的时候进行这样实现尽可能地节约内存。 1.4 降级 整数集合不支持降级操作一旦数组进行升级编码就会一直保存升级后地状态。 举个例子即使我们将集合中唯一一个真正需要int64_t类型来保存地元素删除了整数集合地编码(encoding)仍然会保持INTSET_ENC_INT64底层数组地类型仍然是int64_t类型。 1.5 整数集合API int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep): 验证数据结构的完整性。当“deep”为0时仅验证标头的完整性。当“deep”为1时我们会确保没有重复或无序的记录。
