由散列表到BitMap的概念與應用（三）：面試中的海量資料處理
在面試軟體開發工程師時，經常會遇到海量資料排序和去重的面試題，特別是大資料崗位。
例1：給定a、b兩個檔案，各存放50億個url，每個url各佔64位元組，記憶體限制是4G，找出a、b檔案共同的url?
- 首先我們最常想到的方法是讀取檔案a，建立雜湊表，然後再讀取檔案b，遍歷檔案b中每個url，對於每個遍歷，我們都執行查詢hash表的操作，若hash表中搜索到了，則說明兩檔案共有，存入一個集合。
- 但上述方法有一個明顯問題，載入一個檔案的資料需要50億*64bytes = 320G遠遠大於4G記憶體，何況我們還需要分配雜湊表資料結構所使用的空間，所以不可能一次性把檔案中所有資料構建一個整體的hash表。
如何解答
針對上述問題，我們分治演算法的思想。
step1
遍歷檔案a，對每個url求取hash(url)%1000，然後根據所取得的值將url分別儲存到1000個小檔案(記為a0,a1,...,a999，每個小檔案約300M)，為什麼是1000？主要根據記憶體大小和要分治的檔案大小來計算，我們就大致可以把320G大小分為1000份，每份大約300M。
step2
遍歷檔案b，採取和a相同的方式將url分別儲存到1000個小檔案(記為b0,b1,...,b999)。
檔案a的hash對映和檔案b的hash對映函式要保持一致，這樣的話相同的url就會儲存在對應的小檔案中。比如，如果a中有一個url記錄data1被hash到了a99檔案中，那麼如果b中也有相同url，則一定被hash到了b99中。
所以現在問題轉換成了：找出1000對小檔案中每一對相同的url（不對應的小檔案不可能有相同的url）
step3
因為每個小檔案大約300M，所以我們再可以採用上面解答中的想法。
解題思路
常見的高效解答思路有：堆排序法、分治策略和BitMap(點陣圖法)。
堆排序法
堆排序是4種平均時間複雜度為nlogn的排序方法之一，其優點在於當求M個數中的前n個最大數，和最小數的時候效能極好。所以當從海量資料中要找出前m個最大值或最小值，而對其他值沒有要求時，使用堆排序法效果很好。
從1億個整數裡找出100個最大的數
- 讀取前100個數字，建立最大值堆。
- 依次讀取餘下的數，與最大值堆作比較，維持最大值堆。可以每次讀取的數量為一個磁碟頁面，將每個頁面的資料依次進堆比較，這樣節省IO時間。
- 將堆進行排序，即可得到100個有序最大值。
這裡採用堆排序將空間複雜度講得很低，要排序1億個數，但一次性只需讀取100個數字，或者設定其他基數，不需要一次性讀完所有資料，降低對記憶體要求。
分治策略
總體思想：分而治之。通過分治將大資料變成小資料進行處理，再合併。
首先區分內部排序和外部排序：
- 內部排序：內部排序是指待排序序列可以全部裝入記憶體的排序過程，適用於規模較小的元素序列。
- 外部排序：外部排序是指大檔案的排序，即待排序的記錄儲存在外儲存器上，待排序的檔案無法一次裝入記憶體，需要在記憶體和外部儲存器之間進行多次資料交換，才能達到排序整個檔案的目的。
步驟：
- 從大資料中抽取樣本，將需要排序的資料切分為多個樣本數大致相等的區間
- 將大資料檔案切分為多個小資料檔案，這裡要考慮IO次數和硬體資源問題，例如可將小資料檔案數設定為1G（要預留記憶體給執行時的程式使用）
- 使用最優的演算法對小資料檔案的資料進行排序，將排序結果按照步驟1劃分的區間進行儲存
- 對各個資料區間內的排序結果檔案進行處理，最終每個區間得到一個排序結果的檔案
- 將各個區間的排序結果合並
其次要注意待排序資料的特點。如果待排序資料具有某些特點，往往能夠有更加有效的方法解決。 同時，這種思想也更加貼近大資料應用的思維方式。
BitMap(點陣圖法)
32位機器上，一個整形，比如int a; 在記憶體中佔32bit位，可以用對應的32bit位對應十進位制的0-31個數，BitMap演算法利用這種思想處理大量資料的排序與查詢.
其優點是運算效率高，不許進行比較和移位，且佔用記憶體少，比如N=10000000；只需佔用記憶體為N/8=1250000Byte=1.25M。
解答示例
例2：在特定的場合下：
對10億個不重複的整數進行排序。
找出10億個數字中重複的數字。
如上的題目一般會限制記憶體。
我們換一個與上面示例相似的題目進行演示解答過程。
例3：一臺主機，2G記憶體，40億個不重複的沒排過序的unsigned int的整數的檔案，然後再給一個整數，如何快速判斷這個整數是否在那40億個數當中？
我們可以有幾種方法解答如上的題目。
遍歷法
如果記憶體足夠將40億個數全部放到記憶體中，逐個遍歷，此時時間複雜度為O(N)。可是現在在記憶體不足，需要分批讀一部分資料到記憶體然後在做判斷，加上I/O操作的時間，時間複雜度遠遠大於O(N)。
這時，效能問題主要集中在I/O操作，和遍歷陣列上。那麼有沒有降低時間複雜度的方法呢？答案是肯定的，如果我們假定記憶體是足夠的，只去優化時間，可以得到下面的方法。
直接定址表法
申請一個4G超大陣列char a[0~2^32-1]，將檔案中出現的數字置為1，沒有出現的置為0。 例如檔案存在一個整數1000022，就將a[100002211]=1。
| a | 0 | 1 | 2 | ... | 2^32-1 |
|---|---|---|---|---|---|
| value | 1 | 0 | 1 | 0 | 0 |
這時時間複雜度為O(1)，可是空間問題還沒有解決。分析下我們的演算法，以所需判斷的整數為陣列下標，用0/1來區分整數是否在。一共用了一個位元組來作為標記位，而事實上1Bit就足夠標記了。如果能把這部分空間優化掉，4G/8 < 2G 那麼就可以解決問題了。看下面的方法。
BitMap
在前面兩篇文章中，我們講過BitMap的概念和應用。
將整數對映到bit上，例如整數10，10/8=1，10%8=2，那麼就將a[1]的b[2]置為1。這樣時間複雜度即是O(1)，記憶體也得到了壓縮。
| a | 0 | 1 | 2 | ... | 2^32/8-1 |
|---|---|---|---|---|---|
| bit | 0 1 2 3 4 5 6 7 | 0 1 2 3 4 5 6 7 | 0 1 2 3 4 5 6 7 | 0 1 2 3 4 5 6 7 | 0 1 2 3 4 5 6 7 |
| flag | 0 0 0 0 0 0 0 0 | 0 0 1 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 | 0 0 0 0 0 0 0 0 |
逆向思維優化
unsinged int只有接近43億（unsigned int最大值為2^32-1=4294967295,最大不超過43億），我們還可以用某種方式儲存沒有出現過的3億個數（使用陣列{大小為3億中最大的數/8 bytes}儲存），如果出現在3億個數裡面，說明不在40億裡面。3億個數儲存空間 一般 小於40億個。ps：儲存4294967296（不到43億）需要512MB， 而儲存294967296只需要35.16MB。
這裡需要注意的是，BitMap排序需要的時間複雜度和空間複雜度依賴於資料中最大的數字。當資料類似（1，1000，10萬）只有3個數據的時候，用BitMap時間複雜度和空間複雜度相當大，只有當資料比較密集時才有優勢。
總結
在處理海量資料時，我們會想到這些資料的儲存結構。在所有具有效能優化的資料結構中，大家使用最多的就是hash表，是的，在具有定位查詢上具有O(1)的常量時間，多麼的簡潔優美。但是資料量大了，記憶體就不夠了。當然也可以使用類似外排序來解決問題的，由於要走IO所以時間上又不行。BitMap基於位的對映，用一個Bit位來標記某個元素對應的Value， 而Key即是該元素。由於採用了Bit為單位來儲存資料，因此BitMap在儲存空間方面，可以大大節省。
本文總結了幾種常用的海量資料處理方法，我們可以根據實際的題意（空間、時間限制）進行靈活應用。瞭解散列表和BitMap可以參見前面兩篇文章。