大數據計數原理1+0=1這你都不會算(三)
這是本坑的第三篇，之前已經說了關于 HashSet 和 BitMap 了，這次說說 Bloom Filter 布隆過濾器，要是還不知道前面講了啥的，可以點一下下面的連接看看。
我們都知道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-樹。
【本文為51CTO專欄作者“大蕉”的原創稿件，轉載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權】
