bitmap严格意义上来说不是一种算法，而是一种使用bit位进行数据存储表示的数据结构。通常当我们遇到需要对海量的整数进行去重，排序，而内存又无法同时存放全量数据的时候，可以考虑使用bitmap来解决。bitmap最主要的目的是用来降低存储空间，例如在Java中，int类型占用4个Byte，也就是4 * 8 = 32位，而在bitmap中，仅需要1bit就可以表示一个整数，因此使用bitmap进行整数存储，可以节约32倍的内存。例如，假设现在有1~10亿范围内乱序的10亿不同整数，对这十亿个整数进行排序，这种情况下，使用bitmap即可以大大降低存储的使用，还可以降低不必要的比较和移动次数，提升排序时间。这十亿整数如果不使用bitmap，在Java中需要占用的存储约为1000000000 * 4 /1024/1024/1024 = 3.73G。如果使用bitmap则需要占用的存储空间位为：1000000000/8/1024/1024 = 0.1164G，占用的存储高下立判。
计算机中内存分配的最小单位是字节，因此我们可以使用字节来存储数据，每个字节是8位，可以用来表示8个数字是否存在。假设我们存在如下的bitmap，则我们需要4个字节就可以存储下面的8个数据（这里我们假设起点0是从左向右的，其实真是情况下是从右边向左的，这里是为了看起来更直观。后续的代码实现也是基于这种高位往低位移动的方式）。
bitmap
构造bitmap
本文中的bitmap的构造是基于byte进行存储的，当然也可以使用int或者long进行存储。首先我们需要构建一个可以容纳所有数字的byte数组。
//默认构造最大的存储整数的Byte数组
BitMap(){
bitmap = new byte[(Integer.MAX_VALUE >> 3) + 1];
}
//根据最大值构造存储整数的Byte数组
BitMap(int max){
bitmap = new byte[(max >> 3) + 1];
}
向bitmap中插入数据
向bitmap中插入数据，首先需要找到这个整数num属于哪个byte中，然后再去计算它在这个byte的位置。对于一个num，它对应的byte数组中的位置为num >> 3，在当前byte中的位置为num % 8，需要将当前位置置为1，实现代码如下。
//向bitmap中插入一批整数
public void insert(int[] nums){
for (int num : nums) {
insert(num);
}
}
//向bitmap中插入一个整数
public void insert(int num){
bitmap[num >> 3] |= (128 >> (num % 8));
}
从bitmap中删除数据
从bitmap中删除数据和插入数据一样，需要先找到这个所在的位置，然后将这个位置置为0即可，实现代码如下：
//从bitmap中移除一批整数
public void remove(int[] nums){
for (int num : nums) {
remove(num);
}
}
//从bitmap中移除一个整数
public void remove(int num){
bitmap[num >> 3] &= ~(128 >> (num % 8));
}
从bitmap中查找一个数
查找一个数在bitmap中是否存在，需要先定位到这个数在哪个byte的哪个位置上，然后判断这个位置是否为0，如果为0则不存在，否则存在。
//判断某个数是否存在
public boolean find(int num){
return (bitmap[num >> 3] & (128 >> (num % 8))) == 0 ? false : true;
}
从bitmap顺序提取所有数据
我们可以从第一个byte开始，每次移动一位，判断当前位是否为空，如果不为空，则将该数加入到结果集合中，最终我们能够得到排序和去重好的整数集合。实现代码如下：
//顺序获取bitmap中的所有整数
public List<Integer> collect(){
List<Integer> set = new LinkedList<>();
int count = 0;
for (byte b : bitmap) {
for (int j = 128; j > 0 ; j >>= 1, count++) {
if ((b & j) != 0){
set.add(count);
}
}
}
return set;
}
示例
根据以上的实现，我们可以使用下面的代码演示一下bitmap的操作过程。
public static void main(String[] args) {
BitMap bitMap = new BitMap(100000);
bitMap.insert(22);
bitMap.insert(7);
System.out.println(bitMap.find(3) + " " + bitMap.find(7));
bitMap.remove(13);
System.out.println(bitMap.find(3) + " " + bitMap.find(7));
bitMap.insert(3);
bitMap.insert(15);
System.out.println(bitMap.find(13) + " " + bitMap.find(15));
bitMap.insert(21);
bitMap.insert(16);
System.out.println(bitMap.find(22) + " " + bitMap.find(16));
for ( int i: bitMap.collect()) {
System.out.println("----" + i);
}
}
结果如下：
false true
false true
false true
true true
----3
----7
----15
----16
----21
----22
总结
bitmap的应用场景通常为：大量数据的快速排序、查找、去重。针对数据排序，适用场景为：数据量大，数据不重复，且数据较密集；优点为：运算效率高，不需要进行比较和数据移动，占用内存少。而bitmap天然具有查找和去重的优势，因此在海量密集数据上进行去重，优势比较明显。
网友评论