不得不掌握的三种BitMap

灰太狼 2023-06-29 02:25 23阅读 0赞

![format_png][]

点击箭头处“蓝色字”，关注我们哦！！

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：

![format_png 1][]

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

roaringBitmap.add(4097);

此时内部存储是一个BitmapContainer：

![format_png 2][]

接着执行：

roaringBitmap.runOptimize();

此时内部存储是一个RunContainer

![format_png 3][]

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

Roaring64NavigableMap

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

![format_png 4][]

使用示例：

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

![format_png 5][]

关注回复Flink

获取更多系列

好看，就要点个"在看"

![format_png 6][]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6L1VDNk0xSGYwU1NFcHIxbGJiaWF0aWF4UEpjOHk5SmNPZVJ5Sk9JaHNpYndTeFdQbUhDcUp3eldYOHhUTXo5TVlMcEhLQWtSZlkyZmNNcW92eXhyUjlLcEF3LzY0MA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TN3RJdm81eFlNNjVaaWJYTGN4V0p0TzBYRnp5elA1NzltVUtwSnRPVkhZQzNZcGljSWVHMDlhcWlhZXBUdlBZSGgwaWJ6THdDMmZtR2pEMngwaWJEeGZ3cTJBLzY0MA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TN3RJdm81eFlNNjVaaWJYTGN4V0p0TzBYRnp5elA1NzlzdjUxOTBtRUZyd0VpYThJUERic1JhOURDdzZscEs1cWdZN0JnT0Z0bU5qUlU5U2ljYVBpY1MyRGcvNjQw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TN3RJdm81eFlNNjVaaWJYTGN4V0p0TzBYRnp5elA1NzlEejYwZDhOalZHQjU1YTZERDU3S1F4ZVZxYnU5RnNZczlvTXE0Nkd3V0VGbkVNVnl5SmRZbHcvNjQw?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X3BuZy9TN3RJdm81eFlNNlI1aWJSOG01WXV4TWFQZTdPRFE1MXNLdFBvY1hxZjV0eWliY1pzYnJpYmppYnNqcTNTRERMUFdxWEZqdEhFZGhiZzR5RTJzaWN1d1BsU2R3LzY0MA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9TN3RJdm81eFlNNjNhR0FoNlZmT0ZJMHBDVnFrVXRkbkJXWUYzVkFaOUVLaGNpYzhWeEtWT1JpY2MzQVFiN2d2ZkVOT1FnQ1dycFZoc2lhdXFhanR0Unc3US82NDA?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2dpZi9TN3RJdm81eFlNN01GRVJScTAzTTkwQUVIdTBJRUFSOFpEM21BVzhyZDRJQUZrSGxndEZnaWNCNll1Z014bXdCMk1TVmIyWllMc1kyaWJpYU9pYVdsNHVjUncvNjQw?x-oss-process=image/format,png