海量数据解决方案Bitmap

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：gudepeng.github.io/note/2019/1…

一.Bitmap简介

1：Bitmap算法又名位图算法，其原理是，使用下标代替数值或特定的意义，使用这个位为0或者1代表特性是否存在。
2：Bitmap算法具有效率高，节省空间的特点，适用于对大量数据进行去重，查询等，因为bit在计算机内只占一个bit，而int类型占用32个bit，所以空间节省了32倍。

二.使用场景

假如有一批人群信息，要给这批人群打上标签，例如你要给某些人打上会员的标签，并且要打上30天内购买过商品的人。你可能会在每个人身上打上标签，这样你在获取一个会员集合的时候需要遍历每一个人判断他是否包含会员标签，这样的计算量太大。
你可以换一种思路，我们有10个人，这样我们就会定义一个10位的数组，我们可以把人群按照自增类型设定每个人的id（从0开始），然后每一位对应一个人，用0,1去判断这个人是否有这个标签。
会员标签 |0|1|1|1|0|0|0|1|0|0|
这样我们就可以非常直观的查询到，我们id为1,2,3,7的人事会员。接下来我们继续打一个30天内购买过商品的人
30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|
可以直观的看褚30天内购买过商品的人id为0,1。那么我们想要找出30天内购买过商品的会员，我们只需要做与运算（&）。
会员标签 |0|1|1|1|0|0|0|1|0|0|
30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|
30天内购买过商品的会员 |0|1|0|0|0|0|0|0|0|0|
那么我们想要找出30天内购买过商品或者是会员，我们只需要做或运算（|）。
会员标签 |0|1|1|1|0|0|0|1|0|0|
30天内购买过商品的人 |1|1|0|0|0|0|0|0|0|0|
30天内购买过商品的会员 |1|1|1|1|0|0|0|1|0|0|
那么你一定会说，我创建一个map就可以搞定这个，为什么要使用bitmap呢。
因为在计算机中， 1个int占4字节即32位，而使用Bitmap的话，只需要1/32的内存。
你可能会说，那么我有一个10万的人群，那么我有多少个标签就需要开辟多少个10万位的bit，但是假如我只有一个人符合这个标签就会浪费很多资源，接下来我会在具体的使用方法中告诉大家这个问题是怎么解决的。

三.具体实现方法

在这里我们主要讲解两种主要的使用方法，第一个是EWAHCompressedBitmap(谷歌对Bitmap的实现)，第二个是RoaringBitmap（这个也是大多数主流应用所使用的，例如Spark，Hive，Kylin等）。

1.EWAHCompressedBitmap

EWAH是把Bitmap存褚在一个long数组中，每个元素可以看作为一个64位的二进制数，在EWAH中也叫做word，EWAH初始化是4个word，当所有word都被占用后，就会进行扩容。当添加的数据跨度很大的时候，EWAH会创建一个RLW（Running Length word）,RLW被分为两部分，低32位标识当前word跨越了多少个空word，高32位标识当前RLW后面有多少个连续的word。这样就解决了，跨度很大而开辟大量空间的问题。

2.RoaringBitmap

Roaring Bitmap是将32位的整数分割成2的16次方个整数的数据块，来共享相同的16个最高有效位。使用专门的容器来保存它们的16个最低有效位。当一个数据块整数不超过4096个时，使用一个16位整数的有序数组（在java中使用short类型数组）。当超过4096个整数时，我们使用2^16位的位图（在java中使用long类型数组）。因此我们有两种类型的容器，对于稀疏数据块的数组容器（ArrayContainer）和对于密集数据块的位图容器（BitmapContainer）。阈值4096保证容器的级别，每个整数使用不超过16比特。使用位图容器时，使用2^16来表示超过4096（=2^12）个整数，少于16比特/整数(2^16 / 2^12 = 2^4 = 16，如果值都充满long数组，最理想情况下1比特/整数)。使用数组容器时使用精确的16比特/整数。
为什么选择4096这个阈值呢？因为小于4096时，位图容器可能大于16比特/整数，大于4096时，数组容器会超过2^16（2^12 * 16 = 2^16），占用空间显然超过2^16这个低16位表示的数的容量。一句话，整数基数较小时，使用数组更省空间，基数较大时，使用bitmap更省空间。
这些容器保存在一个共享16个最高有效位的动态数组中：它们作为一级索引。使用数组保证高16位有序。我们认为一级索引一般很小。当n=1 000 000时，它至多包含16个实体。因此它应该保存在CPU缓存中。容器本身不应该使用超过8KB。
下面是一篇论性能对比论文：
db.ucsd.edu/wp-content/…

四.RoaringBitmap使用方式

1.maven引入

<dependencies>
    <dependency>
        <groupId>org.roaringbitmap</groupId>
        <artifactId>RoaringBitmap</artifactId>
        <version>0.8.12</version>
    </dependency>
</dependencies>

2.方法使用

public static void main(String[] args) {
    RoaringBitmap rb = RoaringBitmap.bitmapOf(1,2,3,4,7,33,55);
    //select 返回第几位的值
    System.out.println(rb.select(1));
    //rank 返回小于等于参数的值得个数
    System.out.println(rb.rank(55));
    //contains 是否包含参数
    System.out.println(rb.contains(56));
    //contains 是否包含参数
    System.out.println(rb.contains(5L,56L));
    //add 添加从左闭到右开区间内的值
    rb.add(10L,15L);
    System.out.println(rb);

    RoaringBitmap rb1 = RoaringBitmap.bitmapOf(2,3,4,44);
    System.out.println(rb1);
    //取两个bitmap的并集
    RoaringBitmap rb1or2=RoaringBitmap.or(rb,rb1);
    System.out.println(rb1or2);
    //取两个bitmap的交集
    RoaringBitmap rb1and2=RoaringBitmap.and(rb,rb1);
    System.out.println(rb1and2);
    rb.and(rb1);
    System.out.println(rb);
    //获取第一位
    System.out.println(rb.first());
}