作者 l 會(huì)點(diǎn)代碼的大叔（CodeDaShu）

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

給你一臺(tái) 4G 內(nèi)存的機(jī)器，一組 20 億個(gè)無(wú)序正整數(shù)，如何快速地判斷一個(gè)正整數(shù) N 是否在這組數(shù)字中？或者如何快速地對(duì)這組數(shù)據(jù)排重后排序？

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

這時(shí)候有些伙伴會(huì)說(shuō)：“把數(shù)據(jù)放到磁盤上，然后分批將數(shù)據(jù)讀取到內(nèi)存中就行查詢”，但是這種方法會(huì)導(dǎo)致多次磁盤 IO，而且只能解決第一個(gè)查找的問(wèn)題，排序就沒(méi)有辦法做到了。

01

BitMap 的概念

BitMap 能夠很好地解決這個(gè)問(wèn)題；它是用一個(gè) Bit 位來(lái)標(biāo)記某個(gè)元素對(duì)應(yīng)的 Value， 而 Key 即是該元素，比如我們初始化一個(gè)類型為 bit、長(zhǎng)度為 8 的數(shù)組，數(shù)組下標(biāo) 0-7，數(shù)組中的內(nèi)容 1 表示存在，0 表示不存在，那么：

00000001 下標(biāo)為 0 的位置，對(duì)應(yīng)值是1，那么表示 0；同理：

00000010 表示 1；

00000100 表示 2；

00001000 表示 3；

...

10000000 表示 7；

如果一組數(shù)據(jù) {2,3,4,7} 放到同一個(gè)數(shù)組中的話，就是 10011100：

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

如果增加了一個(gè)數(shù)字 10 呢，那么 1 個(gè) byte 就不夠了：

02

數(shù)據(jù)結(jié)構(gòu)及初始化

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

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

• 如果是用 byte 數(shù)組實(shí)現(xiàn)，那么需要 10/8 + 1 個(gè)長(zhǎng)度；

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

明白了這點(diǎn)之后，一個(gè)簡(jiǎn)單的 BitMap 數(shù)據(jù)結(jié)構(gòu)也就可以確定了：

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

03

添加數(shù)據(jù)

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

索引號(hào) index：數(shù)據(jù)保存在整個(gè)數(shù)組的哪個(gè)下標(biāo)中；

位置號(hào) position：數(shù)據(jù)在這個(gè)下標(biāo)元素的哪個(gè)位置；

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

index = N / 8position = N % 8

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

• 計(jì)算 index = 10/8 = 1 ；

• 計(jì)算 position = 10%8 = 2 ；

• 將 byte[1] 的數(shù)據(jù)與 0000100 做“位或”運(yùn)算，其中 0000100 是通過(guò)對(duì) 1 左移 2 得到。

完整的代碼如下：

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

04

判斷數(shù)字是否存在

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

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

05

測(cè)試

讓我們做一下測(cè)試吧：

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)?"存在":"不存在")); }}

運(yùn)行結(jié)果：

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

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

在 JDK 中，已經(jīng)有對(duì)應(yīng)實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet，我們可以不用強(qiáng)擼 BitMap，直接使用 BitSet 就好了，或者使用谷歌封裝的 EWAHCompressedBitmap。

06

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

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

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

• 運(yùn)算效率高，查找、去重都不需要遍歷全部數(shù)據(jù)；

缺點(diǎn)：

• 所有的數(shù)據(jù)不能重復(fù)，相當(dāng)于直接就是排重過(guò)的；

• 如果數(shù)據(jù)只有兩個(gè)：1 和 10000000，使用 BitMap 得不償失，只有當(dāng)數(shù)據(jù)比較密集時(shí)才有優(yōu)勢(shì)。

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

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
			

		

		

			
		

長(zhǎng)按訂閱更多精彩▼
		

			
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝