不得不掌握的三种BitMap

BitMap

Bitmap 是大数据里面常见的数据结构，简单来说就是按位存储，为了解决在去重场景里面大数据量存储问题，目前在Druid/Spark等使用。在Java中一个字节占用8位，那么就代表可以存储8个数字，存储结构如下：

现在需要存储1与5这两个数字：

只需要将对应的bit的下标置为1即可，每个bit位对应的下标就表示存储的数据。Java中一个int类型占用4个字节32位，假如说现在有一亿的数据量，使用普通的存储模式需要:100000000*4/1024/1024 约为381.5M的存储；使用bitmap存储模式需要：100000000/8/1024/1024 约为11.9M 的存储，可以看到存储减少了一个量级。

java.util包中提供了BitSet类型，其内部包含了一个long类型的数组，通过位运算实现bitmap功能，简单看下其使用方式：

val bitSet:util.BitSet=new util.BitSet()
bitSet.set(0)
bitSet.set(1)
bitSet.get(1) //true

bitSet.clear(1) //删除
bitSet.get(1) //false
bitSet.cardinality()//2
bitSet.size() //64/8=8 字节

接下来存储一个10000的数字：

bitSet.set(10000)
bitSet.cardinality()//2
bitSet.size() //1.22kb

实际上只存储了两个数字，但是最后使用的存储大小确实1.22k, 比2*4=8字节要大很多，这也是bitmap的一个弊端，对于稀疏数据来说会占用很大存储。对此需要使用压缩bitmap,也就是roaringbitmap。

RoaringBitmap

RoaringBitmap 是一种压缩bitmap，其思想就是采用高低位存储方式，将一个Int类型的数据转换为高16位与低16位，也就是两个short类型的数据，高位存储在一个short[] 里面，低位存储在Container[]中，short[] 下标与Container[]下标是一一对应关系。

RoaringBitmap引入：

<dependency>
    <groupId>org.roaringbitmap</groupId>
    <artifactId>RoaringBitmap</artifactId>
    <version>0.8.6</version>
</dependency>

RoaringBitmap 内部包含一个RoaringArray类型的highLowContainer变量，RoaringArray 包含一个short[] 类型的keys变量与Container[]类型的values变量。

数据x写入流程：

1. 通过(short) (x >>> 16) 操作得到高16位，也就是x对应的key, 将其存放在keys中

2. 通过(short) (x & 0xFFFF)操作得到低16位，得到value 存放在与keys下标对应的values中

数据x查找流程：

1. 通过(short) (x >>> 16) 操作得到key, 通过二分查找法从keys中查询出其对应的下标，由此可见keys是从小到大顺序排序的

2. 通过(short) (x & 0xFFFF)操作得到value, 根据获取到的key对应下标从values里面查询具体的值

到目前为止还未介绍Container，也就是其低16位的处理方式，它是一个抽象类，有三个不同的实现类ArrayContainer、BitmapContainer、RunContainer。

1. ArrayContainer

ArrayContainer是初始选择的Container, 内部包含一个short[]类型的content变量，short[]的长度限制是4096，存储原始数据，不做任何处理，同样其也是有序存储方便查找，由于其最大存储4096个数据，一个short 类型占用2个字节，也就是其最大限制是8kb的数据。并且其大小是呈线性增长的。

2. BitmapContainer

当一个ArrayContainer的存储大小超过4096就会自动转换为BitmapContainer，其内部包含一个long[] 类型的bitmap变量，其大小是1024个，使用long[] 进行按位存储，那么可以存储1024*8*8=65536个数据，需要占用的空间大小也就是8kb, 其在初始化的时候就初始化了长度为1024的long[], 也就是其占用固定大小8kb。

3. RunContainer

Run指的是Run Length Encoding，也就是按照行程长度压缩，对于连续数据有比较好的压缩效果，例如：1，2，3，4，5，6，7，8 会压缩成为1，8， 1代表起始数据，8表示长度,在RunContainer中包含一个short[]类型的valueslength的变量，valueslength中存储压缩的数据1,8。使用RunContainer需要主动调用roaringBitmap.runOptimize()，其会比较使用RunContainer与使用ArrayContainer、BitmapContainer的所消耗的存储大小，优先会选择较小存储的Container。

使用示例：

RoaringBitmap roaringBitmap = new RoaringBitmap();
for (int i = 1; i <= 4096; i++) {
    roaringBitmap.add(i);
}

此时内部存储是一个ArrayContainer：

接下来继续添加一个数据：

roaringBitmap.add(4097);

此时内部存储是一个BitmapContainer：

接着执行：

roaringBitmap.runOptimize();

此时内部存储是一个RunContainer

这时候可能又出现了另外一个问题，RoaringBitmap处理的是int类型的数据，但是在实际中我们使用的都是long类型的，可以使用Roaring64NavigableMap。

Roaring64NavigableMap

Roaring64NavigableMap也是使用拆分模式，将一个long类型数据，拆分为高32位与低32位，高32位代表索引，低32位存储到对应RoaringBitmap中，其内部是一个TreeMap类型的结构，会按照signed或者unsigned进行排序，key代表高32位，value代表对应的RoaringBitmap。示意图如下：

使用示例：

Roaring64NavigableMap roaring64NavigableMap=new Roaring64NavigableMap();
roaring64NavigableMap.addLong(1233453453345L);
roaring64NavigableMap.runOptimize();
roaring64NavigableMap.getLongCardinality();