? 思路：從簡單的排序談到BitMap算法，再談到數據去重問題，談到大數據量處理利器：布隆過濾器。

情景1：對無重復的數據進行排序

@給定數據（2，4，1，12，9，7，6）如何對它排序？

? ? ?方法1：基本的排序方法包括冒泡，快排等。

? ? ?方法2：使用BitMap算法

? ? ?方法1就不介紹了，方法2中所謂的BitMap是一個位數組，跟平時使用的數組的唯一差別在于操作的是位。

首先是開辟2個字節大小的位數組，長度為16（該長度由上述數據中最大的數字12決定的）如圖

?
? ? ??然后，讀取數據，2存放在位數組中下標為1的地方，值從0改為1，4存放在下標為3的地方，值從0改為1....結果如圖

? ?

? ? ? 最后，讀取該位數組，得到排好序的數據是：（1，2，4，6，7，9，12）

? ? ??比較方法1和方法2的差別：方法2中，排序需要的時間復雜度和空間復雜度很依賴與數據中最大的數字比如12，因此空間上講需要開2個字節大小的內存，時間上需要遍歷完整個數組。當數據類似（1，1000，10萬）只有3個數據的時候，顯然用方法2，時間復雜度和空間復雜度相當大，但是當數據比較密集時該方法就會顯示出來優勢。

情景2：對有重復的數據進行判重

? ?數據（2，4，1，12，2，9，7，6，1，4）如何找出重復出現的數字？

? ? ? ?首先是開辟2個字節大小的位數組，長度為16（該長度由上述數據中最大的數字12決定的）如圖

? ?

? ? ? 當讀取完12后，數組中的數據如下圖：

? ? ? 當讀取2的時候，發現數組中的值是1，則判斷出2是重復出現的。

應用

? ? ? 應用1：某文件中包含一些8位的電話號碼，統計出現的號碼的個數？（判斷有誰出現）

? ? ? 8為最大是99 999 999，大約是99M的bit，12.5MB的內存，就可以統計出來出現的號碼。

?

? ? ? 應用2：某文件中包含一些8位的電話號碼，統計只出現一次的號碼？（判斷有誰出現并且指出現1次）

? ? ? 需要擴展一下，可以用兩個bit表示一個號碼，0代表沒有出現過，1代表只出現過1次，2代表至少出現2次。?

?

? ? ? 應用3：有兩個文件，文件1中有1億個10位的qq號碼，文件2中有5千萬個10位qq號碼，判斷兩個文件中重復出現的qq號。

? ? ?首先建立10的10次方個大小的位數組（占用內存大約是1.25G），全部初始化為0，讀取第一個文件，對應的qq號存放到對應的未知，數值改為1，如果重復出現仍是1.讀取完畢第一個文件后，讀取第二個文件，對應的位置為1則表示重復出現。

?

? ? ?應用4：有兩個文件，文件1中有1億個15位的qq號碼，文件2中有5千萬個15位的qq號碼，判斷兩個文件中重復出現的qq號。?

? ??應用4中，qq號碼上升為15位的時候，顯然內存是不夠用了，這個時候怎么辦？使用Bloom Filter（布隆過濾器）

?

Bloom Filter（布隆過濾器）：

? ? ? 對于Bit-Map分析一下，每次都會開辟一塊表示最大數值大小的bit數組，比如情景1中的16，將對應的數據經過映射到bit數組的下標，這其實是一種最簡單的hash算法，對1去模。在上述應用4中，當qq號碼改為15位的時候，Bit-Map就不太好用了，如何改進呢？解決辦法：減少bit數組的長度，但是增加hash函數的個數

對于每一個qq號碼，我用K個hash函數，經過k次映射，得到k個不同位置，假設k=3，那么對于一個qq號碼，映射到位數組中3個不同的位置

?

當讀取第二個包含5千萬個qq號碼的文件的時候，使用同樣的3個hash函數進行映射，當3個位置全部是1的時候才表示出現過，否則表示沒有出現過。

有什么疑問嗎？

? ? ? 顯然，對于一個qq號碼，如果它在第一個文件中沒有出現過，但是它映射的3個位置已經全部是1的情況會有嗎？答案是會的，但是這種概率是可控的，可控的意思是：這種誤差跟hash函數的個數和質量是有關系的，可以通過控制hash函數的個數和位數組的大小來控制誤差概率。至于表示3者之間的關系精確的數學公式就不再詳細研究了。

可以這樣講，布隆過濾器是Bit-Map的進一步擴展，對于大數據量判重，布隆過濾器可以在內存中進行判斷，避免了對磁盤的讀寫，效率是很高的。以上是自己關于兩者的理解，有錯誤望指教。