BitMap算法

在某公众号中看到一个比较有意思的题目,记录一下顺便学习下bitmap算法。

1
给40亿个不重复的unsigned int的整数,没排过序的,然后再给一个数,如何快速判断这个数是否在那40亿个数当中?

这道题的解题方法是采用bitmap:1个字节占8位,可以表示8个整数是否出现的情况(出现则对应的位置1,否则为0),那么表示40亿个整数的情况需要40亿/8=5亿,约62.5M的空间.空间复杂度是O(n)+O(1);

BitMap

算法思想

一个int类型的数字占四个字节,一个字节占8位。即一个int数字占32位,如果用每一位表示一个数字的话,一个int类型的整数就可以表示32个整数。bitmap算法就是利用这种思想处理大量的数据的排序和查询。

下面用一组样例来演示一下bitmap的使用:

对数列{1,7,2,5,4}进行排序

我们用一个整数的二进制形式来“存储这几个整数”

1.png

遍历数列,将数列中的数字的对应位置为1

2.png

按顺序输出该二进制中值为1的下标,即为排序后的数列。

bitmap的思想比较简单,最主要的是十进制数字与二进制位之间的映射。

map映射表

假设需要排序或者查找的数据中的最大值不超过MAX = 100000000(一亿),我们需要申请的内存空间大小为int[1+MAX/32]。

1
2
3
4
5
对应的map映射表为:
a[0] ---------> 0-31
a[1] ---------> 32-63
a[2] ---------> 64-95
a[3] ---------> 96-127

将一个整数n映射到map映射表中,首先要确定n在map映射表中的index。我们用int类型的数组a作为map映射表,n/32就可以求出n在a数组中的index。然后再通过n%32求出n所在的位就可以了。

通过上面的分析,可得出一下式子:

1
a[n>>5] |= 1<<(n & 0x1F)

n>>5 相当于 n/32(求得n在a数组中的index)

n & 0x1F 相当于 n%32 (求得n在a[index]的第几位)

|= 相当于将所在位置为1

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class BitMap {

private static final int MAX = 10000000;

private int[] a = new int[MAX/32 + 1];


// 将第i位置为0
public void clean(int i) {
a[i>>5] &= ~(1<<(i & 0x1F));
}

// 将所在的bit位为1
public void add(int n){
//row = n / 32 求十进制数在数组a中的下标
int index = n>>5;
//相当于 n % 32 求十进制数在数组a[i]中的下标
a[index] |= 1<<(n & 0x1F);
}

// 判断所在的bit为是否为1
public int exits(int n){
int index = n >> 5;
return (a[index] & ( 1 << (n & 0x1F)));
}

public static void main(String[] args){
int num[] = {1,5,30,32,64,56,159,120,21,17,35,45};
BitMap bitMap = new BitMap();
for(int i=0;i<num.length;i++){
bitMap.add(num[i]);
}

int temp = 121;
if(bitMap.exits(temp) != 0){
System.out.println("temp: " + temp + " has already exists");
} else {
System.err.println("temp: " + temp + " has not exists");
}
}
}