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

有一道流傳廣泛的面試題：
給你一臺 4G 內(nèi)存的機器翘地，一組 20 億個無序正整數(shù)浑玛，如何快速地判斷一個正整數(shù) N 是否在這組數(shù)字中甲锡？或者如何快速地對這組數(shù)據(jù)排重后排序？
讓我們先算算 20 億個整數(shù)會占用多大的內(nèi)存空間中燥，Java 的 int 類型占用 4 個字節(jié)蝙眶，那么 20 億 * 4 再換算成 G 大約是 7.5G，大于題目中 4G 內(nèi)存的限制褪那，無法一次性地放到內(nèi)存中幽纷；
這時候有些伙伴會說：“把數(shù)據(jù)放到磁盤上，然后分批將數(shù)據(jù)讀取到內(nèi)存中就行查詢”博敬，但是這種方法會導致多次磁盤 IO友浸，而且只能解決第一個查找的問題，排序就沒有辦法做到了偏窝。

BitMap 的概念

BitMap 能夠很好地解決這個問題收恢；它是用一個 Bit 位來標記某個元素對應的 Value，而 Key 即是該元素祭往，比如我們初始化一個類型為 bit伦意、長度為 8 的數(shù)組，數(shù)組下標 0-7硼补，數(shù)組中的內(nèi)容 1 表示存在驮肉，0 表示不存在，那么：

下標 5 對應的位置是 1已骇，表示 5

00000001 下標為 0 的位置离钝，對應值是1，那么表示 0褪储；同理：
00000010 表示 1卵渴；
00000100 表示 2；
00001000 表示 3鲤竹；
...
10000000 表示 7浪读；

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

下標 2,3,4,7 對應的位置是 1，表示了這 4 個數(shù)字

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

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

image.png

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

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

如果用 bit 數(shù)組實現(xiàn)（假如有的話）折联，那么需要 10 + 1 個長度；
如果是用 byte 數(shù)組實現(xiàn)识颊，那么需要 10/8 + 1 個長度诚镰；
如果是用 int 數(shù)組實現(xiàn)，那么就需要 10/32 + 1 個長度（1 個 int 等于 4 個 bytes祥款，等于 32 個 bits）清笨；

明白了這點之后，一個簡單的 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存儲8個數(shù)據(jù)刃跛，存儲最大值為 max_value 的數(shù)組需要 max_value/8+1 個 byte抠艾，除以8就是右移3位
        this.capacity = (max_value >> 3 ) + 1;
        bits = new byte[capacity];
    }
}

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

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

索引號 index：數(shù)據(jù)保存在整個數(shù)組的哪個下標中检号；
位置號 position：數(shù)據(jù)在這個下標元素的哪個位置；

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

index = N / 8
position = N % 8

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

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

計算 index = 10/8 = 1 ；
計算 position = 10%8 = 2 藐俺；
將 byte[1] 的數(shù)據(jù)與 0000100 做“位或”運算炊甲，其中 0000100 是通過對 1 左移 2 得到。

完整的代碼如下：

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

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

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

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

測試

讓我們做一下測試吧：

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

運行結(jié)果：

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

從結(jié)果可以看到菱父，判斷的都很準確，當然這只是一個最簡單的BitMap實現(xiàn)，它還存在著很多問題浙宜，比如我們必須知道數(shù)據(jù)中最大的那個數(shù)字是多少官辽，這個可以采用動態(tài)擴容的方式解決；
在 JDK 中粟瞬，已經(jīng)有對應實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet同仆，我們可以不用強擼 BitMap，直接使用 BitSet 就好了裙品，或者使用谷歌封裝的 EWAHCompressedBitmap俗批。

優(yōu)缺點

優(yōu)點：

占用內(nèi)存空間低，可以極大地節(jié)約空間市怎；
運算效率高岁忘，查找、去重都不需要遍歷全部數(shù)據(jù)区匠；

缺點：

所有的數(shù)據(jù)不能重復干像，相當于直接就是排重過的；
如果數(shù)據(jù)只有兩個：1 和 10000000驰弄，使用 BitMap 得不償失麻汰，只有當數(shù)據(jù)比較密集時才有優(yōu)勢。

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