文档章节

Redis 整数集合

casoc
 casoc
发布于 2017/08/23 15:40
字数 864
阅读 5
收藏 0

整数集合(intset)是集合键的底层实现之一,当一个集合含整数元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。

intset.h/intset源码

typedef struct intset {
  
  // 编码方式
  uint32_t encoding;

  // 集合包含的元素数量
  uint32_t length;

  // 保存元素的数组
  int8_t contents[];

} intset;

length记录了元素个数

encoding表示当前整数集合的编码方式,可选值有:

  1. INTSET_ENC_INT16 表示当前元素都是16位的数字编码,即每个元素使用contents素组的2个数组单位存储
  2. INTSET_ENC_INT32 表示当前元素都是32位的数字编码,即每个元素使用contents素组的4个数组单位存储
  3. INTSET_ENC_INT64 表示当前元素都是64位的数字编码,即每个元素使用contents素组的8个数组单位存储

 

升级

当添加一个新的数字到整数集合中,并且这个数字长度大于当前的编码方式时,整数集合需要进行升级编码方式,使数组的每一个元素都编程新添加数字能够放入最小的编码方式,再将新加元素放入。

部分源代码:

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {

  // 计算编码 value 所需的长度
  uint8_t valenc = _intsetValueEncoding(value);

  uint32_t pos;

  // 默认设置插入为成功
  if (success) *success = 1;

  /* Upgrade encoding if necessary. If we need to upgrade, we know that
  * this value should be either appended (if > 0) or prepended (if < 0),
  * because it lies outside the range of existing values. */
  // 如果 value 的编码比整数集合现在的编码要大
  // 那么表示 value 必然可以添加到整数集合中
  // 并且整数集合需要对自身进行升级,才能满足 value 所需的编码
  if (valenc > intrev32ifbe(is->encoding)) {
    /* This always succeeds, so we don't need to curry *success. */
    // T = O(N)
    return intsetUpgradeAndAdd(is,value);
  } else {
    ......
  }

  ......

}

intsetUpgradeAndAdd方法源码:

static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {

  ....
  // 当前的编码方式
  uint8_t curenc = intrev32ifbe(is->encoding);

  // 新值所需的编码方式
  uint8_t newenc = _intsetValueEncoding(value);

  // 当前集合的元素数量
  int length = intrev32ifbe(is->length);

  // 根据 value 的值,决定是将它添加到底层数组的最前端还是最后端
  // 注意,因为 value 的编码比集合原有的其他元素的编码都要大
  // 所以 value 要么大于集合中的所有元素,要么小于集合中的所有元素
  // 因此,value 只能添加到底层数组的最前端或最后端
  int prepend = value < 0 ? 1 : 0;

  /* First set new encoding and resize */
  // 更新集合的编码方式
  is->encoding = intrev32ifbe(newenc);
  // 根据新编码对集合(的底层数组)进行空间调整
  // T = O(N)
  is = intsetResize(is,intrev32ifbe(is->length)+1);
  while(length--)
    intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));

  /* Set the value at the beginning or the end. */
  // 设置新值,根据 prepend 的值来决定是添加到数组头还是数组尾
  if (prepend)
    intsetSet(is,0,value);
  else
   _intsetSet(is,intrev32ifbe(is->length),value);

  // 更新整数集合的元素数量
  is->length = intrev32ifbe(intrev32ifbe(is->length)+1);

  return is;

}

升级添加大概流程如下:

  1. 根据新值需要的编码方式扩展当前数组长度
  2. 将旧值根据老的编码方式和新的编码方式重新编码并移动到正确位置
  3. 插入新值

升级的好处:

  1. 灵活,可以根据最长数字灵活调整统一整个数组的编码
  2. 节约内存

整数数组不支持降级

© 著作权归作者所有

casoc
粉丝 47
博文 85
码字总数 60735
作品 0
成都
程序员
私信 提问
NoSql之Redis整数集合(intset)源码探究

1 为什么需要intset 动态字符串,双端链表,字典,跳跃表等,这些数据结构都非常强大实用,但是在内存消耗方面也非常“巨大”。 Redis的数据都是存放在内存上面的,所以对内存的使用要求及其...

芥末无疆sss
2018/01/30
0
0
Redis底层详解(四) 整数集合

一、集合概述 对于集合,STL 的 set 相信大家都不陌生,它的底层实现是红黑树。无论插入、删除、查找都是 O(log n) 的时间复杂度。当然,如果用哈希表来实现集合,插入、删除、查找都可以达到...

英雄哪里出来
2018/12/03
0
0
Redis 数据结构——整数集合

整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时,Redis就会使用整数集合作为集合键的底层实现。 整数集合的实现: 整数集合(intset) ...

nao
2016/05/09
166
0
Redis的六种数据结构

本节将对Redis底层的六种数据结构展开详述:简单动态字符串、链表、字典、跳跃表、整数集合、压缩列表。 一、简单动态字符串(SDS) Redis基于C语言开发但并没有直接使用C语言传统的字符串,...

u012050154
2017/11/27
0
0
Redis源码阅读笔记-整数集合结构

整数集合 《Redis设计与实现》 整数集合(intset)是Redis中集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素不多时,Redis就会使用整数集合作为集合键的底层实现。 在R...

Jian_Ming
2018/09/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

基础工具类

package com.atguigu.util;import java.sql.Connection;import java.sql.SQLException;import java.util.Properties;import javax.sql.DataSource;import com.alibaba.druid......

architect刘源源
今天
43
0
P30 Pro劲敌!DxO官宣新机:排行榜又要变

5月26日晚间,DxOMark官方推特预告,将在5月27日公布一款新机型的DxOMark评分,猜猜是哪款? 网友猜想的机型有:红米K20、谷歌Pixel 3a、索尼Xperia 1、诺基亚9 PureView等。 DxOMark即将公布...

linux-tao
昨天
15
0
Ubuntu18.04.2窗口过小不能自适应(二次转载)

解决Ubuntu在虚拟机窗口不能自适应 2018年09月06日 16:20:08 起不了名儿 阅读数 855 此博文转载:https://blog.csdn.net/nuddlle/article/details/77994080(原地址) 试了很多办法这个好用 ...

tahiti_aa
昨天
2
0
死磕 java同步系列之CountDownLatch源码解析

问题 (1)CountDownLatch是什么? (2)CountDownLatch具有哪些特性? (3)CountDownLatch通常运用在什么场景中? (4)CountDownLatch的初始次数是否可以调整? 简介 CountDownLatch,可以...

彤哥读源码
昨天
6
0
Nginx提供下载apk服务

有时候我们可能需要提供文件或者其他apk下载链接,通过 nginx 配置可以很简单地实现。 server {    listen 80;    server_name download.xxx.com;    root app;    locati...

Jack088
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部