不得不掌握的三种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) //falsebitSet.cardinality()//2bitSet.size() //64/8=8 字节

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

bitSet.set(10000)bitSet.cardinality()//2bitSet.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

 2. BitmapContainer

 3. RunContainer

使用示例：

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

此时内部存储是一个ArrayContainer：

roaringBitmap.add(4097);

接着执行：

roaringBitmap.runOptimize();

这时候可能又出现了另外一个问题，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();