簡介

bitmap是一個十分有用的結構。所謂的Bit-map就是用一個bit位來標記某個元素對應的Value， 而Key即是該元素。由于采用了Bit為單位來存儲數據，因此可以大大節省存儲空間。

 

基本思想

這此我用一個簡單的例子來詳細介紹BitMap算法的原理。假設我們要對0-7內的5個元素(4,7,2,5,3)進行排序(這里假設元素沒有重復)。我們可以使用BitMap算法達到排序目的。要表示8個數，我們需要8個byte。

　　1.首先我們開辟一個字節(8byte)的空間，將這些空間的所有的byte位都設置為0

　　2.然后便利這5個元素，第一個元素是4，因為下邊從0開始，因此我們把第五個字節的值設置為1

　　3.然后再處理剩下的四個元素，最終8個字節的狀態如下圖

　　

　　4.現在我們遍歷一次bytes區域，把值為1的byte的位置輸出(2,3,4,5,7)，這樣便達到了排序的目的

　　從上面的例子我們可以看出，BitMap算法的思想還是比較簡單的，關鍵的問題是如何確定10進制的數到2進制的映射圖

為什么要有BitMap
舉個例子，有一個無序有界int數組{1,2,5,7},初步估計占用內存4*4=16字節，這倒是沒什么奇怪的；但是假如有10億個這樣的數呢，10億4/(102410241024)=3.72G左右。如果這樣的一個大的數據做查找和排序，那估計內存也崩潰了，有人說，這些數據可以不用一次性加載，那就是要存盤了，存盤必然消耗IO。

如果用BitMap思想來解決的話，就好很多。一個byte是占8個bit，如果每一個bit的值就是有或者沒有，也就是二進制的0或者1，如果用bit的位置代表數組值有還是沒有，那么0代表該數值沒有出現過，1代表該數組值出現過。也可以描述數據。具體如下圖：

現在假如10億的數據所需的空間就是3.72G/32，一個占用32bit的數據現在只占用了1bit，節省了不少的空間，排序就更不用說了，一切顯得那么順利。這樣的數據之間沒有關聯性，要是讀取的，你可以用多線程的方式去讀取。時間復雜度方面也是O(Max/n)，其中Max為byte[]數組的大小，n為線程大小。

BitMap的映射

我們使用java的int類型（總共32位）來作為基本類型，一個int能夠對應32個數（一位對應一個數），然后組成一個int類型的數組，長度為n，總共能對應32*n個數

假設需要排序或者查找的最大數MAX=10000000（lz:這里MAX應該是最大的數而不是int數據的總數！），那么我們需要申請內存空間的大小為int a[1 + MAX/32]。

其中：a[0]在內存中占32為可以對應十進制數0-31，依次類推： 
bitmap表為： 
a[0]--------->0-31 
a[1]--------->32-63 
a[2]--------->64-95 
a[3]--------->96-127 
..........

我們要把一個整數N映射到Bit-Map中去，首先要確定把這個N Mapping到哪一個數組元素中去，即確定映射元素的index。我們用int類型的數組作為map的元素，這樣我們就知道了一個元素能夠表示的數字個數(這里是32)。于是N/32就可以知道我們需要映射的key了。所以余下來的那個N%32就是要映射到的位數。

求十進制數對應在數組a中的下標
先由十進制數n轉換為與32的余可轉化為對應在數組a中的下標。

如十進制數0-31，都應該對應在a[0]中，比如n=24,那么 n/32=0，則24對應在數組a中的下標為0。又比如n=60,那么n/32=1，則60對應在數組a中的下標為1，同理可以計算0-N在數組a中的下標。

結果就是N/(2^K)

用int，就是n/32=n/(2^5)=n>>5

Note: map的范圍是[0, 原數組最大的數對應的2的整次方數-1]。

求十進制數對應數組元素a[i]在0-31中的位m
m = n & ((1 << K) - 1) 結果就是n%(2^K)

十進制數,0在a[0]的下標為0,1在a[0]的下標為1，十進制數31在a[0]中下標為31，十進制數32在a[1]中下標為0。 在十進制0-31就對應0-31，而32-63則對應也是0-31，即給定一個數n可以通過模32求得在對應數組a[i]中的下標。

m=

n%32=

n的最后5位與31（二進制11111）進行與運算=

n&31=

n&((1<<5)-1)=  n & 0x1F 保留n的后五位 相當于 n % 32 求十進制數在數組a[i]中的下標

 

可以看到在int對應的位0對應0,1對應1，是從右往左開始的，就是總共32格 ，左邊第一格對應31，右邊第一格對應0（其實反過來也可以，但是下面的置0和1的m要變成31-m，因為下面置1的位置是 1<<余數）

 

使得對應第m個bit位為1
對于一個十進制數n,對應在數組a[n/32][n%32]中，但數組a畢竟不是一個二維數組，我們通過或運算作實現置1

比如說下面的第一行

01100100 ，讓從右邊第5位置1

只需=001100100  |  10000  對這一位與1進行或運算即可

如a[i]的第m位置1：a[i] = a[i] | (1<<m)

如：將當前4對應的bit位置1的話，只需要1左移4位與B[0] | 即可。

其實最后置1的操作就是 a[n>>5] |= 1 << (n & 0x1F)

使得對應第m個bit位為0

同理將int型變量a的第k位清0，即a=a&~(1<<k)

就是與 1111101111進行與運算，其他位不變，只有0那位，一定會變成0

 

java實現

內部元素

    /**
	 * bitMap中可以加入的最大數字（范圍是從0到MAX_VALUE）
	 */
	public static final int MAX_VALUE=10000;
	
	/**
	 * 存放bitmap的數組，每個int有32位，對應32個數字
	 */
	private int[] a=new int[MAX_VALUE/32+1];

 

加入

    /**在bitmap中加入元素n
	 * @param n 范圍為[0,MAX_VALUE]
	 */
	public void addValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，不能加入");
			return;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//在n對應的int，對應的位置，置1
		a[row] |=1<<index;				
	}

查找

    /**查找bitmap中是否有元素n
	 * @param n
	 * @return 如果存在，返回true  不存在，返回false
	 */
	public boolean existValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，一定沒有");
			return false;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//result為哪個位置上現在保存的值（為10000(index個0)或者0）
		int result=a[row] & (1<<index);
		//如果不為0，則那個位置一定為1
		return result!=0;
		
	}

刪除

    /**在bitmap中刪除元素n
	 * @param n
	 */
	public void removeValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，一定沒有");
			return;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//對應位置0，與 111101111進行與運算，那位一定變0
		a[row] &=~(1<<index);
	}

展示

    /** 展示第row行的情況，元素的二進制情況，和有的元素
	 * @param row
	 */
	public void displayRow(int row){
		System.out.print("bitmap展示第"+row+"行:"+Integer.toBinaryString(a[row])+" 有：");
		//對應row：32*row到32*row+31
		int now=row<<5;
		//temp為與對應位進行與運算的數字
		int temp=1;
		for(int i=0;i<32;i++){
			int result=a[row] & temp;
			if(result!=0){
				System.out.print("  "+now+"  ");
			}
			now++;
			temp=temp<<1;
		}
		System.out.println();
		
	}

測試

package datastructure.bitmap;
 
public class Main {
 
	public static void main(String[] args) {
 
		BitMap bitMap=new BitMap();
		bitMap.addValue(0);
		bitMap.addValue(31);
		bitMap.displayRow(0);
		System.out.println(bitMap.existValue(1));
		System.out.println(bitMap.existValue(31));
		bitMap.removeValue(0);
		System.out.println(bitMap.existValue(0));
		bitMap.displayRow(0);
		
		bitMap.addValue(34);
		bitMap.displayRow(1);
	}
 
}

完整代碼

package datastructure.bitmap;
 
public class BitMap {
	
	
	/**
	 * bitMap中可以加入的最大數字（范圍是從0到MAX_VALUE）
	 */
	public static final int MAX_VALUE=10000;
	
	/**
	 * 存放bitmap的數組，每個int有32位，對應32個數字
	 */
	private int[] a=new int[MAX_VALUE/32+1];
	
	
	/**在bitmap中加入元素n
	 * @param n 范圍為[0,MAX_VALUE]
	 */
	public void addValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，不能加入");
			return;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//在n對應的int，對應的位置，置1
		a[row] |=1<<index;				
	}
	
	/**查找bitmap中是否有元素n
	 * @param n
	 * @return 如果存在，返回true  不存在，返回false
	 */
	public boolean existValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，一定沒有");
			return false;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//result為哪個位置上現在保存的值（為10000(index個0)或者0）
		int result=a[row] & (1<<index);
		//如果不為0，則那個位置一定為1
		return result!=0;
		
	}
	
	/**在bitmap中刪除元素n
	 * @param n
	 */
	public void removeValue(int n){
		if(n<0||n>MAX_VALUE){
			System.out.println("不再0到"+MAX_VALUE+"的范圍內，一定沒有");
			return;
		}
		//n對應數組的哪個元素，是n/32
		int row=n>>5;
		//n對應的int中的位置，是n mod 32
		int index=n & 0x1F;
		//對應位置0，與 111101111進行與運算，那位一定變0
		a[row] &=~(1<<index);
	}
	
	
	/** 展示第row行的情況，元素的二進制情況，和有的元素
	 * @param row
	 */
	public void displayRow(int row){
		System.out.print("bitmap展示第"+row+"行:"+Integer.toBinaryString(a[row])+" 有：");
		//對應row：32*row到32*row+31
		int now=row<<5;
		//temp為與對應位進行與運算的數字
		int temp=1;
		for(int i=0;i<32;i++){
			int result=a[row] & temp;
			if(result!=0){
				System.out.print("  "+now+"  ");
			}
			now++;
			temp=temp<<1;
		}
		System.out.println();
		
	}
 
}

復雜度

時間
每次操作顯然是O(1), 對n個數的速度為O(n)  這個其實類似與計數排序

空間
如果插入元素的范圍為0-maxValue  那么空間復雜度就是O(maxValue)  與插入元素的多少無關

如果為minValue-maxValue ，那么復雜度就是O(maxValue-minValue) 

 

算法評價

優點
    1. 運算效率高，不進行比較和移位；
    2. 占用內存少，比如最大的數MAX=10000000；只需占用內存為MAX/8=1250000Byte=1.25M。

缺點
    1. 所有的數據不能重復，即不可對重復的數據進行排序。（少量重復數據查找還是可以的，用2-bitmap）。

    2. 當數據類似（1，1000，10萬）只有3個數據的時候，用bitmap時間復雜度和空間復雜度相當大，只有當數據比較密集時才有優勢。

 

應用

1 使用位圖法判斷整形數組是否存在重復
判斷集合中存在重復是常見編程任務之一，當集合中數據量比較大時我們通常希望少進行幾次掃描，這時雙重循環法就不可取了。
位圖法比較適合于這種情況，它的做法是按照集合中最大元素max創建一個長度為max+1的新數組，然后再次掃描原數組，遇到幾就給新數組的第幾位置上1，如遇到 5就給新數組的第六個元素置1，這樣下次再遇到5想置位時發現新數組的第六個元素已經是1了，這說明這次的數據肯定和以前的數據存在著重復。這種給新數組初始化時置零其后置一的做法類似于位圖的處理方法故稱位圖法。它的運算次數最壞的情況為2N。如果已知數組的最大值即能事先給新數組定長的話效率還能提高一倍。

2 在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數

解法一：將bit-map擴展一下，采用2-Bitmap（每個數分配2bit，00表示不存在，01表示出現一次，10表示多次，11無意義）進行，共需內存2^32 * 2 bit=1 GB內存，還可以接受。然后掃描這2.5億個整數，查看Bitmap中相對應位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應位是01的整數輸出即可。

或者我們不用2bit來進行表示，我們用兩個bit-map即可模擬實現這個2bit-map，都是一樣的道理。

解法二：也可采用與第1題類似的方法，進行劃分小文件的方法。然后在小文件中找出不重復的整數，并排序。然后再進行歸并，注意去除重復的元素。

解法三：類似解法2，只是劃分時按照快排partition一樣劃分，直到劃分到每個塊都可以放入內存中。

2.1 一個序列里除了一個元素，其他元素都會重復出現3次，設計一個時間復雜度與空間復雜度最低的算法，找出這個不重復的元素。

3  已知某個文件內包含一些電話號碼，每個號碼為8位數字，統計不同號碼的個數。

8位最多99 999 999，大概需要99m個bit，大概10幾m字節的內存即可。 （可以理解為從0-99 999 999的數字，每個數字對應一個Bit位，所以只需要99M個Bit==1.2MBytes，這樣，就用了小小的1.2M左右的內存表示了所有的8位數的電話）

lz覺得這個是應該用計數排序類似的算法吧，而不是bitmap?

4 給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中？

 解析:bitmap算法就好辦多了。申請512M的內存，一個bit位代表一個unsigned int值，讀入40億個數，設置相應的bit位；讀入要查詢的數，查看相應bit位是否為1，為1表示存在，為0表示不存在。

Note: unsigned int最大數為2^32 - 1，所以需要2^32 - 1個位，也就是(2^32 - 1) / 8 /10 ^ 9G = 0.5G內存。

    逆向思維優化：usinged int只有接近43億（unsigned int最大值為232-1=4294967295,最大不超過43億），所以可以用某種方式存沒有出現過的3億個數（使用數組{大小為3億中最大的數/8 bytes}存儲），如果出現在3億個數里面，說明不在40億里面。3億個數存儲空間一般小于40億個。（xx存儲4294967296需要512MB， 存儲294967296只需要35.16MBxx）

5 給定一個數組a，求所有和為SUM的兩個數。

如果數組都是整數（負數也可以，將所有數據加上最小的負數x，SUM += 2x就可以了）。如a = [1,2,3,4,7,8]，先求a的補數組[8,7,6,5,2,1]，開辟兩個數組b1,b2（最大數組長度為SUM/8/2{因為兩數滿足和為SUM，一個數<SUM/2，另一個數也就知道了}，這樣每個b數組最大內存為SUM/(8*2*1024*1024) = 128M）,使用bitmap算法和數組a分別設置b1 b2對應的位為1，b1 b2相遇就可以得到和為SUM的兩個數其中一個數了。

BloomFilter和BItMap的區別

其實主要的區別在于兩者，一個value對應位圖的位置不同

bitmap，是一一對應，保證一個value對應一個格，所以只需對應一格，還十分準確

BloomFilter 是hashcode，不能保證一個value對應一格，所以要有多個hash函數，還有失誤率，而且還不能刪除，但是BloomFilter節省了空間，還能面對string這種肯定不能一一對應的場景

計數排序與BitMap

計數排序

https://blog.csdn.net/xushiyu1996818/article/details/84762032

計數排序和bitmap十分相似，互為變種，都能夠在O(n)時間內排序，O(K)空間復雜度

區別在于

計數排序對每一個數字設置了一個int，能夠發現總共出現了幾次，但是相當于消耗了32個bit，浪費空間。

普通的bitmap對每個數字，只設置了一個bit，節省空間，但是只能發現這個數字有沒有出現，不能發現出現幾次。

所以對普通的排序，計數排序即可，但是對不僅僅要排序，還要去重，可以使用bitmap