作者 l 會點代碼的大叔（CodeDaShu）

有一道流傳廣泛的面試題：

給你一臺 4G 內存的機器，一組 20 億個無序正整數，如何快速地判斷一個正整數 N 是否在這組數字中？或者如何快速地對這組數據排重后排序？

讓我們先算算 20 億個整數會占用多大的內存空間，Java 的 int 類型占用 4 個字節(jié)，那么 20 億 * 4 再換算成 G 大約是 7.5G，大于題目中 4G 內存的限制，無法一次性地放到內存中；

這時候有些伙伴會說：“把數據放到磁盤上，然后分批將數據讀取到內存中就行查詢”，但是這種方法會導致多次磁盤 IO，而且只能解決第一個查找的問題，排序就沒有辦法做到了。

01

BitMap 的概念

BitMap 能夠很好地解決這個問題；它是用一個 Bit 位來標記某個元素對應的 Value， 而 Key 即是該元素，比如我們初始化一個類型為 bit、長度為 8 的數組，數組下標 0-7，數組中的內容 1 表示存在，0 表示不存在，那么：

00000001 下標為 0 的位置，對應值是1，那么表示 0；同理：

00000010 表示 1；

00000100 表示 2；

00001000 表示 3；

...

10000000 表示 7；

如果一組數據 {2,3,4,7} 放到同一個數組中的話，就是 10011100：

如果按照 int 數組存儲，{2,3,4,7} 需要 4 * 4 * 8 個 bit 才能存儲的數據，但是現(xiàn)在 BitMap 只需要 8 個 bit 就可以存儲，很大地節(jié)省了存儲空間，并且排重后的排序也變的非常簡單了；如果用 byte 實現(xiàn)的話，只需要 1 個 byte 就可以（1 byte = 8 bits）。

如果增加了一個數字 10 呢，那么 1 個 byte 就不夠了：

02

數據結構及初始化

我們可以得知，BitMap 的容量大小取決于最大的那個數值，比如要存儲 {2,3,4,7,10}：

• 如果用 bit 數組實現(xiàn)（假如有的話），那么需要 10 + 1 個長度；

• 如果是用 byte 數組實現(xiàn)，那么需要 10/8 + 1 個長度；

• 如果是用 int 數組實現(xiàn)，那么就需要 10/32 + 1 個長度（1 個 int 等于 4 個 bytes，等于 32 個 bits）；

明白了這點之后，一個簡單的 BitMap 數據結構也就可以確定了：

public class BitMap { //數據 private byte[] bits;  //最大值 private int max_value; //容量 private int capacity;  /** * 初始化 * @param capacity */ public BitMap(int max_value){ this.max_value = max_value; //1bit存儲8個數據，存儲最大值為 max_value 的數組需要 max_value/8+1 個 byte，除以8就是右移3位 this.capacity = (max_value >> 3 ) + 1; bits = new byte[capacity]; }}

03

添加數據

添加數據，需要快速地定位到這個元素要存到整個數組中的哪個位置，這里有兩個概念：

索引號 index：數據保存在整個數組的哪個下標中；

位置號 position：數據在這個下標元素的哪個位置；

比如 10 保存在 index = 1，position = 2（從 0 開始） 這個位置中，經推算可得：

index = N / 8position = N % 8

知道了 10 保存的位置之后，怎么把對應位置的數據更改成 1 呢？可以用“位或”運算。將 10 添加到 BitMap 中的完整步驟如下：

• 計算 index = 10/8 = 1 ；

• 計算 position = 10%8 = 2 ；

• 將 byte[1] 的數據與 0000100 做“位或”運算，其中 0000100 是通過對 1 左移 2 得到。

完整的代碼如下：

public void add(int num){ //數據保存在整個數組的哪個下標中 int index = num / 8; //數據在這個下標元素的哪個位置 int position = num % 8;  bits[index] |= 1<}

04

判斷數字是否存在

知道了如何判斷數字的索引號和位置號之后，判斷數字是否存在也就容易了，直接使用“位與”運算，代碼如下：

public boolean contains(int num){ if(num > max_value){ return false; } //數據保存在整個數組的哪個下標中 int index = num / 8; //數據在這個下標元素的哪個位置 int position = num % 8; return (bits[index] & 1<0;}

05

測試

讓我們做一下測試吧：

public class BitMapTest { public static void main(String[] agrs){ BitMap bm = new BitMap(100);  bm.add(1); bm.add(12); bm.add(14); bm.add(51); bm.add(71); bm.add(100);  System.out.println("12:" + (bm.contains(12)?"存在":"不存在")); System.out.println("13:" + (bm.contains(13)?"存在":"不存在")); System.out.println("51:" + (bm.contains(51)?"存在":"不存在")); System.out.println("66:" + (bm.contains(66)?"存在":"不存在")); System.out.println("100:" + (bm.contains(100)?"存在":"不存在")); }}

運行結果：

12:存在13:不存在51:存在66:不存在100:存在

從結果可以看到，判斷的都很準確，當然這只是一個最簡單的BitMap實現(xiàn)，它還存在著很多問題，比如我們必須知道數據中最大的那個數字是多少，這個可以采用動態(tài)擴容的方式解決；

在 JDK 中，已經有對應實現(xiàn)的數據結構類 java.util.BitSet，我們可以不用強擼 BitMap，直接使用 BitSet 就好了，或者使用谷歌封裝的 EWAHCompressedBitmap。

06

優(yōu)缺點

優(yōu)點：

• 占用內存空間低，可以極大地節(jié)約空間；

• 運算效率高，查找、去重都不需要遍歷全部數據；

缺點：

• 所有的數據不能重復，相當于直接就是排重過的；

• 如果數據只有兩個：1 和 10000000，使用 BitMap 得不償失，只有當數據比較密集時才有優(yōu)勢。

本章節(jié)介紹了 BitMap 的概念和基本實現(xiàn)，后續(xù)會介紹 BitMap 在實際開發(fā)中的應用。

特別推薦一個分享架構+算法的優(yōu)質內容，還沒關注的小伙伴，可以長按關注一下：
			

		

		

			
		

長按訂閱更多精彩▼
		

			
如有收獲，點個在看，誠摯感謝