何为布隆过滤器
問(wèn)題的提出
我們有一個(gè)不安全網(wǎng)頁(yè)的黑名單，包含了100億個(gè)黑名單網(wǎng)頁(yè)的URL,每個(gè)網(wǎng)頁(yè)URL最多占用64B.。
現(xiàn)在我們要設(shè)計(jì)一個(gè)網(wǎng)頁(yè)過(guò)濾系統(tǒng)，這個(gè)系統(tǒng)要判斷該網(wǎng)頁(yè)是否在黑名單里，但是我們的空間有限，只有30GB.
允許有萬(wàn)分之一的判斷失誤
布隆過(guò)濾器
我們可以把所有的URL保存起來(lái)，比如放到hashmap里，但是64B*100億=640GB，不符合要求。
布隆過(guò)濾器（Bloom Filter）是1970年由布隆提出的。它實(shí)際上是一個(gè)很長(zhǎng)的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。布隆過(guò)濾器可以用于檢索一個(gè)元素是否在一個(gè)集合中。它的優(yōu)點(diǎn)是空間效率和查詢時(shí)間都遠(yuǎn)遠(yuǎn)超過(guò)一般的算法，缺點(diǎn)是有一定的誤識(shí)別率和刪除困難。?
如果遇到網(wǎng)頁(yè)黑名單系統(tǒng)、垃圾郵件過(guò)濾、爬蟲網(wǎng)址判重等問(wèn)題，如果可以容忍一定程度的失誤率，那么我們就可以用布隆過(guò)濾器來(lái)解決。
哈希函數(shù)
我們先來(lái)認(rèn)識(shí)一下哈希函數(shù)（或者說(shuō)是復(fù)習(xí)）
1）
哈希函數(shù)的輸入可以認(rèn)為是無(wú)窮大或者是非常大的范圍，比如任意一個(gè)整數(shù)（字符串），而輸出域是有范圍的
（這就意味著不同的輸入可能是相同的輸出）
2）
當(dāng)輸入相同的值時(shí)，返回值也相同（確定性）
3)
所有不同的輸入值得到的輸出，均勻地分布在輸出域內(nèi)，并且與輸入值出現(xiàn)的規(guī)律無(wú)關(guān)。（這也是評(píng)價(jià)一個(gè)哈希函數(shù)是否優(yōu)秀的兩個(gè)重要標(biāo)準(zhǔn)）比如：1和2相差很近，但是經(jīng)過(guò)優(yōu)秀的哈希函數(shù)計(jì)算后，他們應(yīng)該差距較大。
4）
速度快：可以認(rèn)為哈希函數(shù)的計(jì)算時(shí)間是O(1)的。
布隆過(guò)濾器輸入
下面就開始介紹布隆過(guò)濾器啦。
1）
我們準(zhǔn)備k個(gè)哈希函數(shù)，并且他們之間沒(méi)有什么關(guān)系，彼此獨(dú)立。
那么對(duì)于同一個(gè)輸入對(duì)象（你想的沒(méi)錯(cuò)就是一個(gè)URL），經(jīng)過(guò)計(jì)算出來(lái)的結(jié)果也是完全獨(dú)立的沒(méi)有規(guī)律的。
2）
我們準(zhǔn)備一個(gè)數(shù)組，長(zhǎng)度為m，只有兩種狀態(tài)，所以我們選用bit數(shù)組名為bitmap。
3）
我們輸入一個(gè)黑名單里的URL時(shí)：把URL用每一個(gè)哈希函數(shù)計(jì)算出來(lái)，結(jié)果%數(shù)組長(zhǎng)度（目的是能存下呀。。。。。），把對(duì)應(yīng)位置的bit變?yōu)?，記錄下來(lái)。
處理完所有URL，我們的布隆過(guò)濾器就準(zhǔn)備好啦。
布隆過(guò)濾器檢查
我們?nèi)绾斡貌悸∵^(guò)濾器檢查某個(gè)URL是否是黑名單中的呢？
同樣的方法，把這個(gè)值用k個(gè)哈希函數(shù)算出結(jié)果，每一個(gè)結(jié)果都去bitmap里找有沒(méi)有存在過(guò)，只要有一個(gè)結(jié)果不存在，那這個(gè)URL就肯定不是黑名單了。（因?yàn)橹坝猛瑯拥姆椒?#xff0c;bitmap變?yōu)?的那些位置和現(xiàn)在應(yīng)該是一樣的）
接下來(lái)就是比較佛性的事了，既然有一個(gè)答案不存在，這個(gè)URL就不是黑名單里的，那。。。所有答案都存在，就能確定它在黑名單里嗎？
不是的。
因?yàn)榭赡苁瞧渌黆RL算出的答案恰好把本URL的答案全都算出來(lái)過(guò)。
想到這就不禁要問(wèn)了：那這個(gè)數(shù)據(jù)結(jié)構(gòu)有啥用？不是坑爹呢？
其實(shí)是有用的，他的失誤率是很低很低的。
他的原則就是：“寧可錯(cuò)殺三千，不可放過(guò)一個(gè)”
如何設(shè)計(jì)空間和哈希函數(shù)
?
首先我們應(yīng)該想到：數(shù)組太小的話肯定是不準(zhǔn)確的，比如：
就這么小個(gè)數(shù)組，存了幾個(gè)URL，十個(gè)地方全算出來(lái)過(guò)，全成1了。
那后面判斷的時(shí)候就比較坑了，隨便來(lái)什么URL,隨便什么哈希函數(shù)，算出的答案全都出現(xiàn)過(guò)，這顯然不是我們想要的。
所以，我們應(yīng)該知道，數(shù)組過(guò)小會(huì)影響準(zhǔn)確性。
那么我們?nèi)绾胃鶕?jù)數(shù)據(jù)量來(lái)設(shè)計(jì)數(shù)組大小和哈希函數(shù)個(gè)數(shù)呢？
以本題為例：
樣本數(shù)：100億
失誤率：不超過(guò)0.01%，記為p
每個(gè)樣本大小：64B（這個(gè)其實(shí)不影響布隆過(guò)濾器大小，因?yàn)檫@是和哈希函數(shù)有關(guān)的，一般的哈希函數(shù)都能接受64B的數(shù)據(jù)，并且輸出，bitmap只需記錄答案是否出現(xiàn)過(guò)即可）
布隆過(guò)濾器大小m由以下公式?jīng)Q定：
根據(jù)公式算出m=19.19n，向上取整20，所以需要2000億bit=25GB
哈希函數(shù)的個(gè)數(shù)由以下公式?jīng)Q定：
k=14
布隆過(guò)濾器的失誤率為：
計(jì)算出為0.006%，符合要求，此題可解。
公式分析
?
白名單
過(guò)濾器會(huì)用錯(cuò)誤，對(duì)已經(jīng)發(fā)現(xiàn)的錯(cuò)誤樣本可以建立白名單防止錯(cuò)誤。
其他使用場(chǎng)景
- 網(wǎng)頁(yè)爬蟲對(duì)URL的去重，避免爬去相同的URL地址
- 垃圾郵件過(guò)濾，從數(shù)十億個(gè)垃圾郵件列表中判斷某郵箱是否是殺垃圾郵箱
- 解決數(shù)據(jù)庫(kù)緩存擊穿，黑客攻擊服務(wù)器時(shí)，會(huì)構(gòu)建大量不存在于緩存中的key向服務(wù)器發(fā)起請(qǐng)求，在數(shù)據(jù)量足夠大的時(shí)候，頻繁的數(shù)據(jù)庫(kù)查詢會(huì)導(dǎo)致掛機(jī)。
總結(jié)
- 上一篇： 链表相交问题
- 下一篇： leetcode181. 超过经理收入的