数据结构-BitSet和RoaringBitmap

落日映苍穹つ 2023-02-09 14:12 48阅读 0赞

# 数据结构-BitSet和RoaringBitmap #

# 转载声明 #

***本文大量内容系转载自以下文章，有删改，并参考其他文档资料加入了一些内容：***

*  [RoaringBitmap数据结构及原理][RoaringBitmap]
    
     *  作者：yizishou
     *  出处：csdn
 *  [谈谈Roaring Bitmap][Roaring Bitmap]
    
     *  作者：TheLudlows
     *  出处：csdn
 *  [BitSet的使用场景及简单示例][BitSet]
    
     *  作者：cloud-coder
     *  出处：OSCHINA
 *  [不深入而浅出 Roaring Bitmaps 的基本原理][Roaring Bitmaps]
    
     *  作者：木东居士
     *  出处：腾讯云专栏
 *  [Roaring Bitmap更好的位图压缩算法][Roaring Bitmap 1]
    
     *  作者：smartsi
     *  出处：腾讯云专栏
 *  [BitSet的使用场景及简单示例][BitSet]
    
     *  作者：cloud-coder
     *  出处：OSChina

# 1 BitMap #

## 1.1 简介 ##

BitMap/BitSet被广泛的应用于数据查询中，但其由于数据稀疏造成的内存浪费也不可忽视，因此对压缩BitMap的探索一直在进行，比较知名的有WAH、EWAH、RoaringBitmap等。

## 1.2 原理 ##

BitMap 是用一个bit的0或者1来表示一个数是否在集合中，相当于1个32位int就能放32个数（0-31）。

## 1.3 实现 ##

### 1.3.1 sun.jvm.hotspot.utilities.BitMap ###

测试代码如下：

int num = 952;
    BitMap bitMap = new BitMap(num);
    for(int i = 1 ; i < num ; i *= 2){ 
        bitMap.atPut(i,true);
    }
    for(int i = 1 ; i < num ; i ++){ 
        if(bitMap.at(i)){ 
            System.out.print(i+",");
        }
    }
    System.out.println("");

### 1.3.2 自己实现的ChengcBitmap ###

使用int数组来实现Bitmap

public class ChengcBitmap { 
        public static void main(String[] args) { 
            ChengcBitmap chengcBitmap = new ChengcBitmap(32);
            chengcBitmap.atPut(0,true);
        }
        // 存放的bit位数
        private int sizeInBits;
        // 存放数据的int数组
        private int[] data ;
    
        /** * 构造方法 * @param sizeInBits */
        public ChengcBitmap(int sizeInBits){ 
            this.sizeInBits = sizeInBits;
            int sizeInBytes = this.sizeInBytes(sizeInBits);
            this.data = new int[sizeInBytes];
        }
    
        /** * 给指定bit设置boolean值 * @param offset * @param value */
        public void atPut(int offset, boolean value){ 
            if(offset + 1 > sizeInBits){ 
                try { 
                    throw new Exception("offset can`t be greater than " + (sizeInBits - 1));
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            int index = this.sizeInBytes(offset) - 1;
            int pos = 1 << (offset - 32*index - 1);
            if(value) { 
                this.data[index] |=  pos;
            } else { 
                this.data[index] &=  (~pos);
            }
        }
    
        /** * 清理某个bit位的值 * @param offset */
        public void clear(int offset){ 
            if(offset + 1 > sizeInBits){ 
                try { 
                    throw new Exception("offset can`t be greater than " + (sizeInBits - 1));
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            int index = this.sizeInBytes(offset) - 1;
            int pos = 1 << (offset - 32*index - 1);
            this.data[index] &=  (~pos);
        }
    
        /** * 获取指定bit的boolean值 * @param offset * @return 指定bit的boolean值 */
        public boolean at(int offset){ 
            if(offset + 1 > sizeInBits){ 
                try { 
                    throw new Exception("offset can`t be greater than " + (sizeInBits - 1));
                } catch (Exception e) { 
                    e.printStackTrace();
                }
            }
            int index = this.sizeInBytes(offset) - 1;
            int pos = 1 << (offset - 32*index - 1);
            return ((data[index] & pos) != 0);
        }
    
        /** * 通过给定的bit位数计算需要多少字节来存储 * @param sizeInBits * @return 给定的bit位数计算需要多少字节来存储 */
        private int sizeInBytes(int sizeInBits){ 
            if(sizeInBits <= 32){ 
                return 1;
            }
            int basic = sizeInBits/32;
            return sizeInBits % 32 == 0 ? basic : basic+1;
        }
    }

## 1.4 推荐使用的java.util.BitSet ##

### 1.4.1 BitSet简介 ###

*  实现原理  
    BitSet不同于BitMap，他使用long数组来实现。
    
    BitSet实现了一个按需增长的位向量。位 set 的每个组件都有一个boolean值。用非负的整数将BitSet的位编入索引。
    
    可以对每个编入索引的位进行测试、设置或者清除。通过逻辑与、逻辑或和逻辑异或操作，可以使用一个BitSet修改另一个BitSet的内容。
    
    默认情况下，set 中所有位的初始值都是false。每个位 set 都有一个当前大小，也就是该位 set 当前所用空间的位数。
    
    注意，这个大小与位 set 的实现有关，所以它可能随实现的不同而更改。
    
    位 set 的长度与位 set 的逻辑长度有关，并且是与实现无关而定义的。
 *  不支持Null  
    除非另行说明，否则将 null 参数传递给BitSet中的任何方法都将导致NullPointerException。
 *  非线程安全  
    在没有外部同步的情况下，多个线程操作一个BitSet是不安全的。

### 1.4.2 实现原理详解 ###

BitSet是位操作的对象，值只有0或1即false和true，内部维护了一个long数组，初始只有一个long，所以BitSet最小的size是64，当随着存储的元素越来越多，BitSet内部会动态扩充，最终内部是由N个long来存储，这些针对操作都是透明的。

用1个bit来表示一个数据是否出现过，0为没有出现过，1表示出现过。使用的时候既可根据某一个bit是否为0表示，此数是否出现过。

一个1GB的空间，有 8*1024*1024*1024=8.58*10^9bit，也就是可以表示85亿个不同的数

### 1.4.3 使用场景 ###

常见的应用是那些需要对海量数据进行一些统计工作的时候，比如日志分析、用户数统计等等。

如统计40亿个数据中没有出现的数据，将40亿个不同数据进行排序等。

### 1.4.4 简单使用示例 ###

public static void simpleExample() { 
    	BitSet bites = new BitSet();
    	// 将某bit设为true
    	bites.set(1);
    	// 从指定位开始往后查找为true的bit位（包括当前位），没有时返回-1
    	// 返回1
    	System.out.println(bites.nextSetBit(0));
    	// 返回1
    	System.out.println(bites.nextSetBit(1));
    	// 返回-1
    	System.out.println(bites.nextSetBit(2));
    	// 返回总的有效bit位数，记得一个long 64 bit
    	System.out.println(bites + "，bites.size()=" + bites.size());
    	// 返回最高bit为1的是第几位，0是第1位，1是第2位，9是第10位
    	System.out.println(bites + "，bites.length()=" + bites.length());
    	// 返回存放的不同元素的数量
    	System.out.println(bites + "，bites.cardinality()=" + bites.cardinality());
    	bites.set(2);
    	System.out.println(bites + "，bites.size()=" + bites.size());
    	System.out.println(bites + "，bites.length()=" + bites.length());
    	bites.set(3);
    	System.out.println(bites + "，bites.size()=" + bites.size());
    	System.out.println(bites + "，bites.length()=" + bites.length());
    	bites.set(9);
    	System.out.println(bites + "，bites.size()=" + bites.size());
    	System.out.println(bites + "，bites.length()=" + bites.length());
    
    	bites.set(8);
    	System.out.println(bites + "，bites.length()=" + bites.length());
    
    	// 返回存放的不同元素的数量
    	System.out.println(bites + "，bites.cardinality()=" + bites.cardinality());
    
    	BitSet bitSet2 = new BitSet(64);
    	bitSet2.set(9);
    	bitSet2.set(3);
    	System.out.println(bites+"，bites.get(9)="+bites.get(9));
    	System.out.println(bites+"，bites.get(3)="+bites.get(3));
    	System.out.println(bitSet2+"，bitSet2.get(9)="+bitSet2.get(9));
    	System.out.println(bitSet2+"，bitSet2.get(3)="+bitSet2.get(3));
    	// 将本BitSet的位按BitSet2位true的位进行对应位清理
    	bites.andNot(bitSet2);
    	System.out.println(bites+"，bites.length()="+bites.length());
    	System.out.println(bites+"，bites.size()="+bites.size());
    	System.out.println(bites+"，bites.get(9)="+bites.get(9));
    	System.out.println(bites+"，bites.get(3)="+bites.get(3));
    	System.out.println(bitSet2+"，bitSet2.get(9)="+bitSet2.get(9));
    	System.out.println(bitSet2+"，bitSet2.get(3)="+bitSet2.get(3));
    	
    	// 将BitSet转为long数组
    	long[] longs = bitSet.toLongArray();
    }

## 1.5 BitSet应用 ##

### 1.5.1 快速排序 ###

public static void sortArray() { 
    	int[] array = new int[] {  423, 700, 9999, 2323, 356, 6400, 1,2,3,2,2,2,2 };
    	BitSet bitSet = new BitSet(2 << 13);
    	// 虽然可以自动扩容，但尽量在构造时指定估算大小,默认为64
    	System.out.println("BitSet size: " + bitSet.size());
    
    	for (int i = 0; i < array.length; i++) { 
    		bitSet.set(array[i]);
    	}
    	// 剔除重复数字后的元素个数
    	int bitLen=bitSet.cardinality();	
    
    	// 进行排序，即把bit为true的元素复制到另一个数组
    	int[] orderedArray = new int[bitLen];
    	int k = 0;
    	// 从首位开始往后查找每个为true的bit位，找到后将对应的int数值放入int数组
    	for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { 
    		orderedArray[k++] = i;
    	}
    
    	System.out.println("After ordering: ");
    	for (int i = 0; i < bitLen; i++) { 
    		System.out.print(orderedArray[i] + "\t");
    	}
    	
    	System.out.println("iterate over the true bits in a BitSet");
    	// 或直接迭代BitSet中bit为true的元素iterate over the true bits in a BitSet
    	for (int i = bitSet.nextSetBit(0); i >= 0; i = bitSet.nextSetBit(i + 1)) { 
    		System.out.print(i+"\t");
    	}
    	System.out.println("---------------------------");
    }

### 1.5.2 快速去重 ###

放入相同的数字到Bitset肯定就自动去重了。

### 1.5.3 快速查询 ###

直接bitset.get(bitIndex)，可以O(1)时间拿到结果。

public boolean get(int bitIndex) { 
       if (bitIndex < 0)
            throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    
        checkInvariants();
    
        int wordIndex = wordIndex(bitIndex);
        return (wordIndex < wordsInUse)
            && ((words[wordIndex] & (1L << bitIndex)) != 0);
    }

### 1.5.4 Bloom Filter(布隆过滤器) ###

*  [BloomFilter布隆过滤器][BloomFilter]

### 1.5.5 求一个字符串包含的char ###

BitSetDemo.containChars("How do you do? 你好呀");
    
    public static void containChars(String str) { 
    	BitSet used = new BitSet();
    	for (int i = 0; i < str.length(); i++)
    		used.set(str.charAt(i)); // set bit for char
    
    	StringBuilder sb = new StringBuilder();
    	sb.append("[");
    	int size = used.size();
    	System.out.println(size);
    	for (int i = 0; i < size; i++) { 
    		if (used.get(i)) { 
    			sb.append((char) i);
    		}
    	}
    	sb.append("]");
    	System.out.println(sb.toString());
    }

输出结果：

[ ?Hdouwy你呀好]

可以看到，结果对重复字符进行了去重。

### 1.5.6 求素数 ###

/** * 求素数 有无限个。 * 一个大于1的自然数，如果除了1和它本身外，不能被其他自然数整除(除0以外）的数称之为素数(质数） * 否则称为合数 */
    @Test
    public void computePrime() { 
    	// 计算1024以内的素数
    	BitSet sieve = new BitSet(1024);
    	int size = sieve.size();
    	// 排除0和1，其他数都放入BitSet
    	for (int i = 2; i < size; i++)
    		sieve.set(i);
    	// 开方得到32
    	int finalBit = (int) Math.sqrt(sieve.size());
    
    	// 将这些数的从2倍开始的所有倍数依次从原BitSet中移除
    	for (int i = 2; i < finalBit; i++)
    		if (sieve.get(i))
    			for (int j = 2 * i; j < size; j += i)
    				sieve.clear(j);
    
    	int counter = 0;
    	for (int i = 1; i < size; i++) { 
    		if (sieve.get(i)) { 
    			System.out.printf("%5d", i);
    			if (++counter % 15 == 0)
    				System.out.println();
    		}
    	}
    	System.out.println();
    }

## 1.6 小结 ##

*  优点
    
     *  节约空间，用少量空间存储大量非重复数字
     *  查询速度快
 *  缺点
    
     *  稀疏性  
        特别是在数字间隔很大时，需要很多的int或long组成数组来存储，导致稀疏，浪费空间。可用RoaringBitmap等解决。

# 2 RoaringBitmap #

## 2.1 背景 ##

前面提到的对压缩BitMap的探索中性能最好并且应用最为广泛的当属Roaring Bitmap，比如Spark、Lucene、Redis、Influxdb、Hive、Kylin等著名项目中都可以看到Roaring Bitmap身影，下面就谈谈Roaring Bitmap它是如何实现。

## 2.2 原理 ##

### 2.2.1 概述 ###

在传统的BitMap中，所有的Bit都放在一个Int或者Long数组中，每个数只能存对应区间数值，所以会造成稀疏性（比如1，99999999，99999999999，需要根据最大值99999999999来使用很多个Long数字组成数组来存储，尽管只有三个数）。

位图索引会占用大量的内存，因此我们会更喜欢压缩位图索引。 RoaringBitmaps 就是一种十分优秀的压缩位图索引，后文统称 RBM。

RoaringBitmap将32bit进行了分区，高16位相同的为同一个分区，而每个分区又根据数据量情况来使用专门设计的容器来存放低16位数据，一个分区最多可容纳`2^16`个数。

也就是说，RBM 把一个 32 位的 Integer 划分为高 16 位和低 16 位，通过高 16 位找到该数据存储在哪个桶中（高 16 位可以划分`2^16`个桶），把剩余的低 16 位放入该桶对应的 Container 中。

`2^16`个bit为8KB，在Bitmap中一定占用8KB内存，但是假如一个片下只有一个数据，那么就没必要占用8KB了。再比如所有的数据都存在，即`2^16`个bit全部为1，我们可以用(65536,1)来表示，只占用4Byte。因此就有了三种不同的Container。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]  
每个RoaringBitmap中都包含一个`RoaringArray`，名字叫`highLowContainer`（这个名字意味着，会将32位的整形（int）拆分成高16位和低16位两部分（两个short）来处理）。其中存储了RoaringBitmap中的全部数据。RoaringArray的数据结构很简单，核心为以下三个成员：

short[] keys;
    Container[] values;
    int size;

*  每个32位的整形，高16位会被作为key存储到short\[\] keys中。  
    而且keys数组永远保持有序，方便二分查找分区桶
 *  低16位则被看做value，存储到Container\[\] values中的某个Container中
 *  **keys和values通过下标一一对应**，用于查找某个int要放入的分区桶
 *  size则标示了当前包含的key-value pair的数量，即keys和values中有效数据对的数量。

### 2.2.2 Container ###

#### 2.2.2.1 ArrayContainer ####

##### 2.2.2.1.1 概念 #####

适用于稀疏数据-当一个分区内的Int数据量不超过4096时，用4096作为阈值的原因请看这里

static final int DEFAULT_MAX_SIZE = 4096
    // 该数组直接存放原始int数据的低16位
    short[] content;

*  Array Container 是 Roaring Bitmap 初始化默认的 Container，适合存放稀疏的数据  
    无压缩，直接在short数组中存放原始int数据的低16位，所以只适合存储稀疏的数据。
 *  Array Container内部数据结构是一个有序的 Short 数组  
    该数组初始容量为 4，数组最大容量为 4096，所以 Array Container 是动态变化的。
 *  Array Container可转为Bitmap Container  
    当容量不够时，需要扩容。并且当数组长度超过容量阈值 4096 时，就会转换为 Bitmap Container。
 *  `short[] content`始终保持有序  
    由于数组是有序的，存储和查询时都可以通过二分查找快速定位其在数组中的位置，**且不会存储重复数值**
 *  ArrayContainer占用的空间大小与存储的数据量为线性关系  
    每个short int 占用2B，因此存储了N个数据（N <= 4096）的ArrayContainer占用空间大致为2N B。存储一个数据占用2B，存储4096个数据占用8KB。
 *  ArrayContainer对比Bitmap  
    相较于原始的 Bitmap 需要占用 16KB (131122 / 32 \* 4字节 / 1024) 内存来存储这个数，而使用Array Container实际只占用了4B（桶中是个Short占 2B，Container 为16位也占 2B，不考虑数组的初始容量）。

##### 2.2.2.1.2 插入例子 #####

下面我们具体看一下Array Container中数据如何被存储的，例如，0x00020032（十进制131122）放入一个 RBM 的过程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]

1.  0x00020032 的前 16 位是 0002，找到对应的桶 0x0002。
2.  在桶对应的 Container 中存储低 16 位，因为 Container 元素个数为4不足 4096，因此是一个 Array Container。
3.  低 16 位为 0032（十进制为50）, 在 Array Container 中**二分查找**找到相应的位置插入即可（如上图50的位置）。

#### 2.2.2.2 BitmapContainer ####

##### 2.2.2.2.1 概念 #####

适用于稠密数据-当一个分区内的Int数据量超过4096时

final long[] bitmap;

*  BitmapContainer，顾名思义，和普通的Bitmap（Java的Bitset）一样，通过Long数组来保存数据。
 *  BitmapContainer内部Long数组长度固定位1024  
    而且由于最多需要保存原始数据的低16位即最大`2^16 = 65536`，考虑每个数用64位long内的一个bit表示，因此Long数组长度固定为`65536 / 64 = 1024`。
    
    这一点BitmapContainer和上文的 Array Container 不同，Array Container 是一个动态扩容的数组。
 *  Bitmap Container 不用像 Array Container 那样需要二分查找定位位置，而是可以直接通过下标直接寻址。  
    先用低16位对应的short int数值 / 64得到long数组下标，然后通过前面计算的余数作为offset找到在该long内的bit下标
 *  BitmapContainer和ArrayContainer使用可以相互转化。  
    转移阈值4096
 *  一个BitmapContainer占用空间恒定8KB  
    与ArrayContainer占用的空间大小与存储的数据量为线性关系不同。
    
    一个 Long 值占 8B，Long数组大小固定为 1024，因此一个 Bitmap Container 固定占用内存 8 KB，和数组长度为4096的ArrayContainer所占空间相等。

##### 2.2.2.2.2 插入例子 #####

下面我们具体看一下数据如何被存储的，例如，0xFFFF3ACB（十进制4294916811）放入一个 RBM 的过程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]

1.  0xFFFF3ACB 的前 16 位是 FFFF，找到对应的桶 0xFFFF。
2.  在桶对应的 Container 中存储低 16 位，因为 Container 中元素个数已经超过 4096，因此是一个 Bitmap Container。
3.  低 16 位为 3ACB（十进制为15051）, 因此在 Bitmap Container 中通过下标直接寻址找到相应的位置，将该bit置为 1 即可（如上图15051的位置）。

#### 2.2.2.3 RunContainer ####

private short[] valueslength;
    
    int nbrruns = 0;

*  RunContainer中的Run指的是行程长度压缩算法(Run Length Encoding)，对连续数据有比较好的压缩效果。
 *  内部用一个short\[\]来存储所有的数据。  
    源码中的short\[\] valueslength中存储的就是压缩后的数据。
 *  原理是，对于连续出现的数字，只记录初始数字和后续数量。
    
     *  对于数列11，它会压缩为11,0；
     *  对于数列11,12,13,14,15，它会压缩为11,4；
     *  对于数列11,12,13,14,15,21,22，它会压缩为11,4,21,1；
 *  这种压缩算法的性能和数据的连续性（紧凑性）关系极为密切。  
    对于连续的100个short，它能从200字节（`100 * 2B`）压缩为4字节(`2 * 2B`)；但对于完全不连续的100个short，编码完之后反而会从200字节变为400字节（每个数都压缩为N,1，反而多了一个short）。
 *  如果要分析RunContainer的容量，我们可以做下面两种极端的假设：
    
     *  最好情况，即只存在一个数据或只存在一串连续数字，那么只会存储2个short，占用4B
     *  最坏情况，0~65535的范围内填充所有的奇数位（或所有偶数位），需要存储65536个short，此时空间为128KB
 *  只有当调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。

#### 2.2.2.4 使用4096来区分使用不同container的阈值的原因 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]  
可以看到元素个数达到 4096 之前，Array Container 占用的空间比 Bitmap Container 的少，当 Array Container 中元素到 4096 个时，正好等于 Bitmap Container 所占用的 8 KB。

当元素个数超过了 4096 时，Array Container 所占用的空间还是继续线性增长，而 Bitmap Container 的内存空间由于使用固定长度1024的Long数组，所以并不会增长，始终还是占用 8 KB，与数据量无关。所以当 Array Container 超过最大容量 4096 会转换为 Bitmap Container。

因为一个 Integer 的低 16 位是 2Byte，因此对应到 Arrary Container 中的话就是 2Byte \* 4096 = 8KB；同样，对于 Bitmap Container 来讲，2^16 个 bit 也相当于是 8KB。

然后，基于前面提到的两种 Container，在两个 Container 之间的 Union (bitwise OR) 或者 Intersection (bitwise AND) 操作又会出现下面三种场景：

*  Bitmap vs Bitmap
 *  Bitmap vs Array
 *  Array vs Array  
    RBM 提供了相应的算法来高效地实现这些操作，比如下图是 Bitmap vs Bitmap，这里暂不再深入讨论，感兴趣的可以看一下论文原文：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 4]

## 2.3 插入数据例子 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 5]

### 2.3.1 插入821697800 ###

现在我们要将`821697800`这个 32 bit 的整数插入 RBM 中，整个算法流程是这样的：

1.  821697800 对应的 16 进制数为 30FA1D08， 其中高 16 位为 30FA， 低16位为 1D08。
2.  我们先用二分查找从一级索引（即 Container Array）中找到数值为 30FA 的容器（如果该容器不存在，则新建一个），从图中我们可以看到，该容器是一个 Bitmap Container。
3.  找到了相应的容器后，看一下低 16 位的数值 1D08，换算成十进制是 7432，因此在 Bitmap 中找到相应的位置，将改bit位置为 1 即可。

### 2.3.2 插入191037 ###

1.  191037 对应的 16 进制数为 0002EA3D， 其中高 16 位为 0002， 低16位为 EA3D。
2.  我们先用二分查找从一级索引（即 Container Array）中找到数值为 0002 的容器（如果该容器不存在，则新建一个），从图中我们可以看到，该容器是一个 Array Container。
3.  找到了相应的容器后，看一下低 16 位的数值 EA3D，换算成十进制是 59965，因此在 Array Container中使用二分查找找到相应的位置再插入即可。

## 2.4 关于性能和内存 ##

### 2.4.1 查找 ###

*  ArrayContainer和RunContainer都需要二分查找，复杂度O(log n)
 *  BitmapContainer可根据下标直接寻址，复杂度为O(1)

### 2.4.2 内存空间 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 6]

*  ArrayContainer占用空间随着数组内元素增多而线性增长，在达到4096后空间为8KB和BitmapContainer相同，超过这一数值后内存空间就超过BitmapContainer了
 *  BitmapContainer是一条斜率为0直线，始终占用8kb
 *  RunContainer比较奇葩，因为和数据的连续性关系太大，因此只能画出一个上下限范围。不管数据量多少，下限始终是4B；上限在最极端的情况下可以达到128KB。

能方面最出众的C++版本的Roaring Bitmap，比如SIMD加速位操作，当然这不是它独有的。个人认为主要还是它的内存占用，无论数据密集与否，都能有优于Bitmap。

如果你有兴趣可以阅读一下优秀的Java版本的实现[RoaringBitmap][RoaringBitmap 1]

## 2.5 RoaringBitmap针对Container的优化策略 ##

### 2.5.1 创建时 ###

*  创建包含单个值的Container时，选用ArrayContainer
 *  创建包含一串连续值的Container时，比较ArrayContainer和RunContainer，选取空间占用较少的

### 2.5.2 转换 ###

*  针对ArrayContainer：
    
     *  如果插入值后容量超过4096，则自动转换为BitmapContainer。因此正常使用的情况下不会出现容量超过4096的ArrayContainer。
     *  调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。
 *  针对BitmapContainer
    
     *  如果删除某值后容量低至4096，则会自动转换为ArrayContainer。因此正常使用的情况下不会出现容量小于4096的BitmapContainer。
     *  调用runOptimize()方法时，会比较和RunContainer的空间占用大小，选择是否转换为RunContainer。
 *  针对RunContainer  
    只有在调用runOptimize()方法才会发生转换，会分别和ArrayContainer、BitmapContainer比较空间占用大小，然后选择是否转换。

[RoaringBitmap]: https://blog.csdn.net/yizishou/article/details/78342499
[Roaring Bitmap]: https://blog.csdn.net/TheLudlows/article/details/104035174
[BitSet]: https://my.oschina.net/cloudcoder/blog/294810
[Roaring Bitmaps]: https://cloud.tencent.com/developer/article/1136054?from=10680
[Roaring Bitmap 1]: https://cloud.tencent.com/developer/article/1481855
[BloomFilter]: https://blog.csdn.net/baichoufei90/article/details/84928497
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200520102850265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/2020052000160290.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200520003443630.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200520003626801.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200519233732369.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200519234004310.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200520110237633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA==,size_16,color_FFFFFF,t_70
[RoaringBitmap 1]: https://github.com/RoaringBitmap/RoaringBitmap