20 億個(gè)數(shù)字在 4G 內(nèi)存中如何去重排序：快來(lái)試一試 BitMap

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

給你一臺(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)有辦法做到了。

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 就不夠了：

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

明白了這點(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];    }}

添加數(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<}

知道了如何判斷數(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;}

讓我們做一下測(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。

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

缺點(diǎn)：

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