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

大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(一)

大數(shù)據(jù)計數(shù)原理1+0=1這你都不會算(二)

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

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

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

怎么辦呢?空間時間已經(jīng)使用到***了，hash算法也選擇了能盡量平均分配到整個數(shù)組的 bit 里面了。大神Burtom Bloom 發(fā)明了一個布隆算法。

這個算法的存儲結(jié)構(gòu)跟 BitMap 是相同的，區(qū)別在于它使用了多個 Hash 算法，一個字符串經(jīng)過N個 Hash 算法會生成多個 Hash 值，如果N個值的 bit位 都為1 ，才判定該字符串已經(jīng)存在。

比如字符串 “小蕉寫得這么給力你不點個贊嗎”，經(jīng)過 Hash 算法1、Hash 算法2、Hash 算法3，生成了數(shù)字，1、11、21。

這時候又來了一個字符串 “小蕉寫得這么給力你不點個贊”，經(jīng)過 Hash 算法1、Hash 算法2、Hash 算法3、生成了數(shù)字，1，11，19。

發(fā)現(xiàn)，咦，沒有全部出現(xiàn)，所以該字符串沒有出現(xiàn)過。

就這樣，一個 Bloom Filter 就構(gòu)造完了，每次只需要生成N個值就可以判定該字符串有沒有存在過了，經(jīng)過嚴(yán)格的數(shù)學(xué)推導(dǎo)，只需要 8 個 Hash 函數(shù)，就可以把Bloom Filter 的錯誤率降低到一個非常低的值，非?？煽俊?/p>

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

好啦，今天就聊到這里啦，下次跟大家聊一個大家聽得比較多，在非常多索引系統(tǒng)里面使用的的數(shù)據(jù)結(jié)構(gòu)，B-樹。

【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】

戳這里，看該作者更多好文