大數據計數原理1+0=1這你都不會算(三)No.51

02-12

這是本坑的第三篇，之前已經說了關於 HashSet 和 BitMap 了，這次說說 Bloom Filter 布隆過濾器，要是還不知道前面講了啥的，可以點一下下面的連接看看。

大數據計數原理1+0=1這你都不會算(一)No.47

大數據計數原理1+0=1這你都不會算(二)No.50

我們都知道BitMap已經非常節省空間了，一個值只需要一個 bit 就可以進行統計了，但是，對於上百億的數據來說，碰撞率即使非常低，但也不是一個可以忽視的問題了。

當時提出這個問題，一個是因為垃圾電子郵箱，每天少說都有幾十億的垃圾郵箱在發垃圾郵件，把這些郵件直接全部都存儲起來，不是一個經濟的做法。使用 BitMap 來進行存儲吧，碰撞的次數太多，很多正常的郵件都被標記為黑名單郵件，很是難受。

另外一個是因為 Google 的爬蟲，在進行鏈接抓取的時候，為了效率，都要知道哪些鏈接抓過哪些沒抓過，一開始也是用的 BitMap ，但是碰撞的鏈接太多，導致很多鏈接都無法抓到，導致很多網頁都沒法被搜錄，也很是難受。

怎麼辦呢？空間時間已經使用到極致了，hash演算法也選擇了能盡量平均分配到整個數組的 bit 裡面了。大神Burtom Bloom 發明了一個布隆演算法。

這個演算法的存儲結構跟 BitMap 是相同的，區別在於它使用了多個 Hash 演算法，一個字元串經過N個 Hash 演算法會生成多個 Hash 值，如果N個值的 bit位都為1 ，才判定該字元串已經存在。

比如字元串「小蕉寫得這麼給力你不點個贊嗎」，經過 Hash 演算法1、Hash 演算法2、Hash 演算法3，生成了數字，1、11、21。

這時候又來了一個字元串「小蕉寫得這麼給力你不點個贊」，經過 Hash 演算法1、Hash 演算法2、Hash 演算法3、生成了數字，1，11，19。

發現，咦，沒有全部出現，所以該字元串沒有出現過。

就這樣，一個 Bloom Filter 就構造完了，每次只需要生成N個值就可以判定該字元串有沒有存在過了，經過嚴格的數學推導，只需要 8 個 Hash 函數，就可以把Bloom Filter 的錯誤率降低到一個非常低的值，非常可靠。

我們這樣想，即使真的真的真的那麼巧，k-1個Hash函數的值都一樣，只要第k個不一樣，那這個演算法依然會把它當成新的元素。這樣就解決了 BitMap 誤判率高的問題了，時間複雜度也只是根據所選Hash函數的個數線性增長。

好啦，今天就聊到這裡啦，下次跟大家聊一個大家聽得比較多，在非常多索引系統裡面使用的的數據結構，B-樹。