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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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