在一些海量數(shù)據(jù)的場景中，做一些查重、去重、排序，一般的方法難以實(shí)現(xiàn)，因?yàn)閮?nèi)存占用太大了，比如以下問題：
問題一：10億個正整數(shù)，給定一個數(shù)值，如何快速判定該數(shù)值是否在10億個正整數(shù)當(dāng)中？假如機(jī)器只有1G內(nèi)存？
問題二：比如說是一組數(shù)字，它是保存在一個很大的文件中。它總體的個數(shù)為400億個，里面有大量重復(fù)的數(shù)據(jù)，如果去除重復(fù)的元素之后，大概的數(shù)據(jù)有40個億，那么，假定我們有一臺內(nèi)存為2GB的機(jī)器。我們該如何來消除其中重復(fù)的元素呢？再進(jìn)一步考慮，如果我們消除了重復(fù)的元素之后，怎么統(tǒng)計(jì)里面元素的個數(shù)并將去重后的元素保存到另外的一個結(jié)果文件里呢？
我們來估計(jì)一下上面所需要用到的內(nèi)存，1G 約等于 10^9(10的9次方)個字節(jié)，上面的數(shù)字都是int型，一個int 占用4字節(jié)，所以問題一可能需要占用4G內(nèi)存，而問題二中，需要占用16G內(nèi)存，顯然需要的內(nèi)存太大了，傳統(tǒng)的方法是不能用了，這時候就需要引出今天的主角了——BitMap位圖法。
1、思想
位圖法的思想類似于hash尋址，首先初始化一個int數(shù)組，每個元素對應(yīng)32位比特（一個int 占用4字節(jié)，1字節(jié)8個比特位），將10億個元素分別讀入內(nèi)存，對int數(shù)組中的元素比特位進(jìn)行標(biāo)記，如果存在，標(biāo)記為1即可。標(biāo)記完之后，即可快速判定某個元素是否在10億個正整數(shù)當(dāng)中，時間復(fù)雜度為O（1）。
原先一個int類型只能表示一個整數(shù)，現(xiàn)在一個int能表示32個整數(shù)，相當(dāng)于是節(jié)省了32倍的內(nèi)存。
那么具體我們是怎么操作？？
- 尋址
比如元素 119，如何確定其對應(yīng)的數(shù)組比特位 index ？
1）確定數(shù)組 arrayIndex ：119/32 = 3，也就是第 4 個數(shù)組元素，a[3] 的位置?！猲um >> 5（num右移5位，相當(dāng)于是除以2的5次方）;
2）確定比特位 bitIndex：119%32 = 23，第23個比特位。—— num & 31
- 設(shè)置比特位
- 將比特位設(shè)置為1
bigArray[arrayIndex] |= 1 << bitIndex（1左移到目標(biāo)位置，然后進(jìn)行或運(yùn)算）; - 將比特位設(shè)置為0
bigArray[arrayIndex] &= ~(1 << bitIndex);（1左移到目標(biāo)位置，然后取反，然后再進(jìn)行與運(yùn)算）;
- 將比特位設(shè)置為1
- 判斷某一元素是否存在
只需將 1 左移bitIndex位數(shù)，然后與原來的值進(jìn)行與運(yùn)算。只要與運(yùn)算結(jié)果中有1，即表示元素存在。所以可以用運(yùn)行結(jié)果是不為0作為元素是否存在依據(jù)。
2、實(shí)現(xiàn)
2.1 自定義實(shí)現(xiàn)
import java.util.BitSet;
public class bitMap {
private int[] bigArray;
public bitMap(long size){
bigArray = new int[(int) (size/ 32 + 1)];
}
public void set1(int num){
//確定數(shù)組 index
int arrayIndex = num >> 5;
//確定bit index
int bitIndex = num & 31;
//設(shè)置0
bigArray[arrayIndex] |= 1 << bitIndex;
}
public void set0(int num){
//確定數(shù)組 index
int arrayIndex = num >> 5;
//確定bit index
int bitIndex = num & 31;
//設(shè)置0
bigArray[arrayIndex] &= ~(1 << bitIndex);
System.out.println(get32BitBinString(bigArray[arrayIndex]));
}
public boolean isExist(int num){
//確定數(shù)組 index
int arrayIndex = num >> 5;
//確定bit index
int bitIndex = num & 31;
//判斷是否存在
return (bigArray[arrayIndex] & (1 << bitIndex))!=0 ? true : false;
}
/**
* 將整型數(shù)字轉(zhuǎn)換為二進(jìn)制字符串，一共32位，不舍棄前面的0
* @param number 整型數(shù)字
* @return 二進(jìn)制字符串
*/
private static String get32BitBinString(int number) {
StringBuilder sBuilder = new StringBuilder();
for (int i = 0; i < 32; i++){
sBuilder.append(number & 1);
number = number >>> 1;
}
return sBuilder.reverse().toString();
}
public static void main(String[] args) {
int[] arrays = new int[]{1, 2, 35, 22, 56, 334, 245, 2234, 54};
bitMap bigMapTest = new bitMap(2234-1);
for (int i : arrays) {
bigMapTest.set1(i);
}
System.out.println(bigMapTest.isExist(36));
}
}
2.1 jdk實(shí)現(xiàn)
在java.util包中有個BitSet類也是用同樣的思想實(shí)現(xiàn)的，不過BitSet的底層實(shí)現(xiàn)是long數(shù)組（long是64位，占用8個字節(jié)）。
public class BitSetTest {
public static void main(String[] args) {
int [] array = new int [] {1,2,3,22,0,3,63};
BitSet bitSet = new BitSet(1);
System.out.println(bitSet.size()); //64
bitSet = new BitSet(65);
System.out.println(bitSet.size()); //128
bitSet = new BitSet(23);
System.out.println(bitSet.size()); //64
//將數(shù)組內(nèi)容組bitmap
for(int i=0;i<array.length;i++)
{
bitSet.set(array[i], true);
}
System.out.println(bitSet.get(22));
System.out.println(bitSet.get(60));
System.out.println("下面開始遍歷BitSet：");
for ( int i = 0; i < bitSet.size(); i++ ){
System.out.println(bitSet.get(i));
}
}
}
3、優(yōu)缺點(diǎn)
- 優(yōu)點(diǎn)：是海量數(shù)據(jù)下去重時，用這種數(shù)據(jù)結(jié)構(gòu)可以大量的節(jié)省空間；
- 缺點(diǎn)：
- 空間占用大小是根據(jù)最大值來的，如果數(shù)據(jù)量本身不多，但是最大值特別大，那不但不會節(jié)省空間，反而會浪費(fèi)空間
- 功能有限，由于bit位只能是0和1，所以只能用于去重和查重，如果要統(tǒng)計(jì)每個元素出現(xiàn)的個數(shù)，就不能實(shí)現(xiàn)了。
