1. Bit Map算法簡介

? ? ? ??來自于《編程珠璣》。所謂的Bit-map就是用一個(gè)bit位來標(biāo)記某個(gè)元素對(duì)應(yīng)的Value， 而Key即是該元素。由于采用了Bit為單位來存儲(chǔ)數(shù)據(jù)，因此在存儲(chǔ)空間方面，可以大大節(jié)省。

2、 Bit Map的基本思想

? ? ? ? 我們先來看一個(gè)具體的例子，假設(shè)我們要對(duì)0-7內(nèi)的5個(gè)元素(4,7,2,5,3)排序（這里假設(shè)這些元素沒有重復(fù)）。那么我們就可以采用Bit-map的方法來達(dá)到排序的目的。要表示8個(gè)數(shù)，我們就只需要8個(gè)Bit（1Bytes），首先我們開辟1Byte的空間，將這些空間的所有Bit位都置為0，如下圖：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

然后遍歷這5個(gè)元素，首先第一個(gè)元素是4，那么就把4對(duì)應(yīng)的位置為1（可以這樣操作 p+(i/8)|(0x01<<(i%8)) 當(dāng)然了這里的操作涉及到Big-ending和Little-ending的情況，這里默認(rèn)為Big-ending）,因?yàn)槭菑牧汩_始的，所以要把第五位置為一（如下圖）：
?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

然后再處理第二個(gè)元素7，將第八位置為1,，接著再處理第三個(gè)元素，一直到最后處理完所有的元素，將相應(yīng)的位置為1，這時(shí)候的內(nèi)存的Bit位的狀態(tài)如下：?
?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

然后我們現(xiàn)在遍歷一遍Bit區(qū)域，將該位是一的位的編號(hào)輸出（2，3，4，5，7），這樣就達(dá)到了排序的目的。

?

優(yōu)點(diǎn)：

1.運(yùn)算效率高，不許進(jìn)行比較和移位；

2.占用內(nèi)存少，比如N=10000000；只需占用內(nèi)存為N/8=1250000Byte=1.25M。?
缺點(diǎn)：

? ? ? ?所有的數(shù)據(jù)不能重復(fù)。即不可對(duì)重復(fù)的數(shù)據(jù)進(jìn)行排序和查找。 ? ?

?

算法思想比較簡單，但關(guān)鍵是如何確定十進(jìn)制的數(shù)映射到二進(jìn)制bit位的map圖。

3、 Map映射表

假設(shè)需要排序或者查找的總數(shù)N=10000000，那么我們需要申請(qǐng)內(nèi)存空間的大小為int a[1 + N/32]，其中：a[0]在內(nèi)存中占32為可以對(duì)應(yīng)十進(jìn)制數(shù)0-31，依次類推：?
bitmap表為：?
a[0]--------->0-31?
a[1]--------->32-63?
a[2]--------->64-95?
a[3]--------->96-127?
..........?
那么十進(jìn)制數(shù)如何轉(zhuǎn)換為對(duì)應(yīng)的bit位，下面介紹用位移將十進(jìn)制數(shù)轉(zhuǎn)換為對(duì)應(yīng)的bit位。?

如題：

給你一個(gè)文件，里面包含40億個(gè)整數(shù)，寫一個(gè)算法找出該文件中不包含的一個(gè)整數(shù)， 假設(shè)你有1GB內(nèi)存可用。

如果你只有10MB的內(nèi)存呢？

一個(gè)位代表一個(gè)數(shù)據(jù)，那40一個(gè)數(shù)據(jù)大概要40*10^8*bit = 0.5GB,滿足內(nèi)存要求。

首先我們用int來表示：int ?bmap[1+N/32]; //N是總數(shù)，N=40億，一個(gè)int32bit

然后我們插入一個(gè)整數(shù)val，要先計(jì)算val位于數(shù)組bmap中的索引:index = val/32;

比如整數(shù)33，index=33/32=1,第33位于數(shù)組中的index=1

比如整數(shù)67，index=67/32=2,位于數(shù)組中index=2

然后在計(jì)算在這個(gè)index中的位置，因?yàn)閿?shù)組中的每個(gè)元素有32位

33，index=1，在1中的位置為33%32=1

67，index=2，在2中的位置為67%32=3

然后就是標(biāo)識(shí)這個(gè)位置為1：

bmap[val/32] ?|= (1<<(val%32));

33: bmap[1] ? ?!= (1<<1);//xxxxxx1x,紅絲位置被置為1

67: bmap[2] ? != ?(1<<3);//xxxx1xxx

void setVal(int val) {bmap[val/32] |= (1<<(val%32));//bmap[val>>5] != (val&0x1F);//這個(gè)更快？ }

?

怎樣檢測(cè)整數(shù)是否存在？

比如我們檢測(cè)33，同樣我們需要計(jì)算index，以及在index元素中的位置

33: index = 1, 在bmap[1]中的位置為 1，只需要檢測(cè)這個(gè)位置是否為1

bmp[1] &(1<<1),這樣是1返回true，否側(cè)返回false

67:bmp[2]&(1<<3)

127:bmp[3]&(1<<31)

bool testVal(int val) {return bmap[val/32] & (1<<(val%32));//return bmap[val>>5] & (val&0x1F); }

?

現(xiàn)在我們來看如果內(nèi)存要求是10MB呢？

?

這當(dāng)然不能用bitmap來直接計(jì)算。因?yàn)閺?0億數(shù)據(jù)找出一個(gè)不存在的數(shù)據(jù)，我們可以將這么多的數(shù)據(jù)分成許

多塊， 比如每一個(gè)塊的大小是1000，那么第一塊保存的就是0到999的數(shù)，第2塊保存的就是1000 到1999的數(shù)……

實(shí)際上我們并不保存這些數(shù)，而是給每一個(gè)塊設(shè)置一個(gè)計(jì)數(shù)器。 這樣每讀入一個(gè)數(shù)，我們就在它所在的塊對(duì)應(yīng)的計(jì)數(shù)器加1。

處理結(jié)束之后，?我們找到一個(gè)塊，它的計(jì)數(shù)器值小于塊大小(1000)， 說明了這一段里面一定有數(shù)字是文件中所不包含的。然后我們單獨(dú)處理
這個(gè)塊即可。接下來我們就可以用Bit Map算法了。我們?cè)俦闅v一遍數(shù)據(jù)， 把落在這個(gè)塊的數(shù)對(duì)應(yīng)的位置1(我們要先把這個(gè)數(shù)
歸約到0到blocksize之間)。 最后我們找到這個(gè)塊中第一個(gè)為0的位，其對(duì)應(yīng)的數(shù)就是一個(gè)沒有出現(xiàn)在該文件中的數(shù)。)

4、 Bit-Map的應(yīng)用

? ? ??1）可進(jìn)行數(shù)據(jù)的快速查找，判重，刪除，一般來說數(shù)據(jù)范圍是int的10倍以下。

?????? 2）去重?cái)?shù)據(jù)而達(dá)到壓縮數(shù)據(jù)

5、 具體實(shí)現(xiàn)（JAVA）

【問題實(shí)例】

1）已知某個(gè)文件內(nèi)包含一些電話號(hào)碼，每個(gè)號(hào)碼為8位數(shù)字，統(tǒng)計(jì)不同號(hào)碼的個(gè)數(shù)。

8位最多99 999 999，大概需要99m個(gè)bit，大概10幾m字節(jié)的內(nèi)存即可。

位圖法需要的空間很少（依賴于數(shù)據(jù)分布，但是我們也可以通過一些放啊發(fā)對(duì)數(shù)據(jù)進(jìn)行處理，使得數(shù)據(jù)變得密集），在數(shù)據(jù)比較密集的時(shí)候效率非常高。例如：8位整數(shù)可以表示的最大十進(jìn)制數(shù)值為99999999，如果每個(gè)數(shù)組對(duì)應(yīng)于一個(gè)bit位，那么把所有的八進(jìn)制整數(shù)存儲(chǔ)起來只需要：99Mbit = 12.375MB.

實(shí)際上，Java?jdk1.0已經(jīng)提供了bitmap的實(shí)現(xiàn)BitSet類，不過其中的某些方法是jdk1.4之后才有的。

分別使用自己實(shí)現(xiàn)的BitMap和jdk的BitSet類：

1 //去除重復(fù)并排序2 import java.util.Arrays;3 import java.util.BitSet;4 import java.util.Random;5 6 /**7 * @author 8 * @date Time: 9 * @des: 10 */ 11 public class BitMap { 12 int ARRNUM = 800; 13 int LEN_INT = 32; 14 int mmax = 9999; 15 int mmin = 1000; 16 int N = mmax - mmin + 1; 17 18 public static void main(String args[]) { 19 new BitMap().findDuplicate(); 20 new BitMap().findDup_jdk(); 21 } 22 23 public void findDup_jdk() { 24 System.out.println("*******調(diào)用JDK中的庫方法--開始********"); 25 BitSet bitArray = new BitSet(N); 26 int[] array = getArray(ARRNUM); 27 for (int i = 0; i < ARRNUM; i++) { 28 bitArray.set(array[i] - mmin); 29 } 30 int count = 0; 31 for (int j = 0; j < bitArray.length(); j++) { 32 if (bitArray.get(j)) { 33 System.out.print(j + mmin + " "); 34 count++; 35 } 36 } 37 System.out.println(); 38 System.out.println("排序后的數(shù)組大小為：" + count ); 39 System.out.println("*******調(diào)用JDK中的庫方法--結(jié)束********"); 40 } 41 //下面是自己實(shí)現(xiàn)的方法： 42 public void findDuplicate() { 43 int[] array = getArray(ARRNUM); 44 int[] bitArray = setBit(array); 45 printBitArray(bitArray); 46 } 47 48 public void printBitArray(int[] bitArray) { 49 int count = 0; 50 for (int i = 0; i < N; i++) { 51 if (getBit(bitArray, i) != 0) { 52 count++; 53 System.out.print(i + mmin + "\t"); 54 } 55 } 56 System.out.println(); 57 System.out.println("去重排序后的數(shù)組大小為：" + count); 58 } 59 60 public int getBit(int[] bitArray, int k) {// 1右移 k % 32位 與上 數(shù)組下標(biāo)為 k/32 位置的值 61 return bitArray[k / LEN_INT] & (1 << (k % LEN_INT)); 62 } 63 64 public int[] setBit(int[] array) {// 首先取得數(shù)組位置下標(biāo) i/32, 然后 或上 65 // 在該位置int類型數(shù)值的bit位：i % 32 66 int m = array.length; 67 int bit_arr_len = N / LEN_INT + 1; 68 int[] bitArray = new int[bit_arr_len]; 69 for (int i = 0; i < m; i++) { 70 int num = array[i] - mmin; 71 bitArray[num / LEN_INT] |= (1 << (num % LEN_INT)); 72 } 73 return bitArray; 74 } 75 76 public int[] getArray(int ARRNUM) { 77 78 @SuppressWarnings("unused") 79 int array1[] = { 1000, 1002, 1032, 1033, 6543, 9999, 1033, 1000 }; 80 81 int array[] = new int[ARRNUM]; 82 System.out.println("數(shù)組大小：" + ARRNUM); 83 Random r = new Random(); 84 for (int i = 0; i < ARRNUM; i++) { 85 array[i] = r.nextInt(N) + mmin; 86 } 87 88 System.out.println(Arrays.toString(array)); 89 return array; 90 } 91 }

?

2)2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。?
將bit-map擴(kuò)展一下，用2bit表示一個(gè)數(shù)即可，0表示未出現(xiàn)，1表示出現(xiàn)一次，2表示出現(xiàn)2次及以上，在遍歷這些數(shù)的時(shí)候，如果對(duì)應(yīng)位置的值是0，則將其置為1；如果是1，將其置為2；如果是2，則保持不變?；蛘呶覀儾挥?bit來進(jìn)行表示，我們用兩個(gè)bit-map即可模擬實(shí)現(xiàn)這個(gè)2bit-map，都是一樣的道理。

給你一個(gè)文件，里面包含40億個(gè)整數(shù)，寫一個(gè)算法找出該文件中不包含的一個(gè)整數(shù)， 假設(shè)你有1GB內(nèi)存可用。

如果你只有10MB的內(nèi)存呢？原文地址：https://www.cnblogs.com/protected/p/6626447.html

?

轉(zhuǎn)載于:https://www.cnblogs.com/jstarseven/p/9444451.html

總結(jié)

以上是生活随笔為你收集整理的BitMap位图与海量数据的理解与应用的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。