【数据结构】BitMap

大家好，欢迎来到IT知识分享网。

(转载请删除括号里的内容)

目录

一、BitMap介绍

二、BitMap应用场景

1、查询统计、定位查询，排序，去重

2、取两个集合的交集，并集等

三、BitMap的实现

1、自己动手实现BitMap

2、JDK中实现的BitMap —— BitSet 集合

3、谷歌实现的BitMap —— EWAHCompressedBitmap

四、BitMap总结

一、BitMap介绍

BitMap，即位图，使用每个位表示某种状态，适合处理整型的海量数据。本质上是哈希表的一种应用实现，原理也很简单，给定一个int整型数据，将该int整数映射到对应的位上，并将该位由0改为1。例如：

// 存在一个int整型数组 int[] arr = new int[]{6,2,7,14,3}; 

arr数组中最大值为14，考虑位的下标从0开始，需要长度为15的bit，因此每个bit代表着0~14的整数，如图所示：

很显然，使用 BitMap 存储这个数组只使用了使用15bit，而使用 HashSet 或 HashMap 的话，一个数组元素会存储为一个int，而一个int占4个byte，即4*8=32bit，这里有5个数组元素则需要5*32=160bit，这样的话，使用 BitMap 存储一个元素则可以节省32倍的内存空间。因此，BitMap 的优势就不言而喻了。

俗话说，结构决定功能，BitMap非常适合对整型的海量数据进行查询统计、排序、去重；适合对两个集合做交集、并集运算，但不支持非运算，如果需要进行非运算则需要提供一个全量的BitMap才行。另外，Java中的 BitSet 集合是对 BitMap 算法相对简单的实现，而谷歌开发的 EWAHCompressedBitmap 是一种更为优化的实现，后面再详细分析下。

二、BitMap应用场景

举个很常见的例子，比如我们项目的数据库表中经常会有ID列，通过该ID列可以映射我们需要统计查询的列，或需要去重的列，比如有一张订单表：

1、查询统计、定位查询，排序，去重

首先，根据order_id建立与其他列的映射关系，order_id其实就是 BitMap，如图：

如果按商家统计今日接单量：

如果按顾客或者送货地址统计接单量，也是类似，这里查询统计接单量是非常实用的。

此外，快速查找一个数据是否在订单集合里也很简单，这里 order_id 的 0~5 中 1~5 对应的位均会被修改为1，如果查找订单0是否存在，判断0对应的位是否为1即可，很明显不存在订单0。而去重的话，BitMap结构决定它具有去重的特性，如果有两个订单3，第一个订单3会将3对应的位修改为1，第二个也会修改为1，最终3对应的位仍然是1。BitMap结构也决定它具有排序特性，这个很好理解。

2、取两个集合的交集，并集等

接着上面的查询统计，如果查询十足便利店被高新区下单的情况，该如何查询呢？这里，就相当于取 十足便利店 和 高新区 的交集了，如图所示：

那如果改为查询 十足便利店 或 高新区下单的情况，该如何查询呢？这里，就相当于取 十足便利店 和 高新区 的并集了，如图所示：

三、BitMap的实现

1、自己动手实现BitMap

代码简单实现如下：

public class BitMap { private char[] bytes; // 用字符数组存储元素 private int nBits; // 指定BitMap长度 public BitMap(int nBits) { this.nBits = nBits; this.bytes = new char[nBits / 16 + 1]; // 一个字符占2个字节，也就是2*8=16bit } / * 设置int整数对应的位，修改为1 */ public void set(int k) { if (k > nBits) return; int byteIndex = k / 16; int bitIndex = k % 16; bytes[byteIndex] |= (1 << bitIndex); } / * 获取int整数对应的位是否存在，true存在，false不存在 */ public boolean get(int k) { if (k > nBits) return false; int byteIndex = k / 16; int bitIndex = k % 16; return (bytes[byteIndex] & (1 << bitIndex)) != 0; } } 

测试一下：

@SpringBootTest class MySportHealthyApplicationTests { @Test void test1() { int[] arr = new int[]{6, 2, 7, 14, 3}; int maxArr = Arrays.stream(arr).max().getAsInt(); // 指定BitMap长度 BitMap bitMap = new BitMap(maxArr + 1); // 数组的整数放进BitMap for (int i = 0; i < arr.length; i++) { bitMap.set(arr[i]); } // 判断哪些值存在 for (int i = 0; i < maxArr + 1; i++) { logger.info(i + ",是否在BitMap内-----》:" + bitMap.get(i)); } } } 

控制台输出结果：

注意：

实际上海量数据的设置和查询逻辑没有这么简单，甚至会出现一些极端情况，比如有一个整型数组[1,2,50000,]，元素间隔很大，导致2和50000，以及50000和之间存在很多空的bit，这些bit很明显占据了很大的空间，我们可以参考JDK中位集的概念，引入 word 有效解决了这类问题，感兴趣的可以去阅读 BitSet 集合源码一探究竟。

2、JDK中实现的BitMap —— BitSet 集合

下面这段是JDK对BitSet集合的描述：

总结如下：

• 一个BitSet对象可以通过logical AND、logical inclusive OR、AND logical exclusive OR操作来修改另一个BitSet对象的内容；
• 默认情况下，集合中的所有位的初始值为false。位集的每个组成部分都有一个布尔值，每个位集都有一个当前大小，即该位集当前使用的空间位数，换言之大小与位集的实现有关，因此它可能随实现而改变；
• BitSet集合对于多线程使用是不安全的。
• 另外，BitSet 可以看作是 word 组成的数组，而一个word 对应一个64位的long类型，需要6个地址位。

做下测试：

@SpringBootTest class MySportHealthyApplicationTests { @Test void test1() { int[] arr = new int[]{1, 7, 50000, }; //1到3千万 int maxArr = Arrays.stream(arr).max().getAsInt(); BitSet bitSet = new BitSet(maxArr + 1); // 存放数据 bitSet.set(1); bitSet.set(7); bitSet.set(50000); bitSet.set(); // 查找 logger.info("1000是否存在------->" + bitSet.get(1000)); //false logger.info("7是否存在------->" + bitSet.get(7)); //true logger.info("50000是否存在------->" + bitSet.get(50000)); //true logger.info("是否存在------->" + bitSet.get()); //false logger.info("是否存在------->" + bitSet.get()); //true } } 

3、谷歌实现的BitMap —— EWAHCompressedBitmap

对于一个很长的 BitMap 只存储少量的数据，比如只有第的位置为1，那么它之前的空间会造成浪费，所以谷歌的实现对这个空间进行了优化，提供了 EWAHCompressedBitmap ，要使用需要先引入依赖：

<!--EWAHCompressedBitmap--> <dependency> <groupId>com.googlecode.javaewah</groupId> <artifactId>JavaEWAH</artifactId> <version>1.1.0</version> </dependency> 

原理：

EWAHCompressedBitmap 将整个的二进制数据划分为一个个Word，一个Word需要64位 ，而一个空的 BitMap 默认拥有 4 个word ，也就是 4*64=256 位，其中 word0 存储 BitMap 的头信息，当我们改变对应位置的bit位的值时 word 会跟着变化。

Word又可以分为两种：直接存储数据的LW，存储跨度信息的RLW，EWAH有些Word存储实际数据，有些Word存储数据和数据之间的间隔个数，当节点之间跨度很大时，Bitmap不会傻傻把长度扩充到Bitmap的最高位那么多，他会由一个节点专门存储两个节点之间的跨度信息，以此达到节省空间的目的。在插入新的数据的时候，如果数据不存放在已有的Word当中，EWAH还会进行动态扩充或对存储跨度的节点进行分裂。

结构和原理可以参考：https://www.it610.com/article/1283246062009597952.htm。

四、BitMap总结

至此，介绍了BitMap的原理、常用的使用场景，自己动手写一个BitMap，顺便分析了JDK及谷歌对BitMap实现和优化。Bitmap不是万能的，如果数据量大到一定程度，如64bit类型的数据，不能用Bitmap，2^64bit=2^61Byte=2048PB=2EB。Bitmap的好处在于空间复杂度不随原始集合内元素的个数增加而增加，而它的坏处也源于这一点 —— 空间复杂度随集合内最大元素增大而线性增大。BitMap对整型的海量数据操作较为合适，而对字符型 或 非整数型的海量数据，则推考虑荐使用布隆过滤器。