題目：不安全網(wǎng)頁的黑名單包含100億個(gè)黑名單網(wǎng)頁，每個(gè)網(wǎng)頁的url最多占用64b.現(xiàn)在想要實(shí)現(xiàn)一個(gè)網(wǎng)頁過濾系統(tǒng)，利用該系統(tǒng)可以根據(jù)網(wǎng)頁的URL判斷該網(wǎng)頁是否在黑名單上，請(qǐng)?jiān)O(shè)計(jì)該系統(tǒng)

要求：

1、該系統(tǒng)允許有萬分之一以下的判斷失誤率

2、使用額外空間不超過30GB

如果把黑名單中所有的url通過數(shù)據(jù)庫或哈希表保存下來，就可以對(duì)每條url進(jìn)行查詢，但是每個(gè)url有64b,數(shù)據(jù)量是100億個(gè)，所以至少需要640GB的空間，不滿足要求

布隆過濾器的優(yōu)勢(shì)在于使用很少的空間就可以將準(zhǔn)確率做到很高的程度

布隆過濾器：如圖1所示，假設(shè)有一個(gè)長(zhǎng)度為m的bit類型的數(shù)組，即數(shù)組中每一個(gè)位置都只占用一個(gè)bit，每個(gè)bit位置只有0和1兩種狀態(tài)，假設(shè)一共有k個(gè)哈希函數(shù)，這些函數(shù)輸出域S都大于或等于m，并且哈希函數(shù)之間相互獨(dú)立。同一個(gè)輸入對(duì)象，對(duì)算出來的每一個(gè)結(jié)果都對(duì)m取余(%m),然后在bit array相應(yīng)的位置設(shè)置為1，如圖2所示

處理完所有輸入對(duì)象之后，bitMap已經(jīng)有很多位置被涂黑，因此一個(gè)布隆過濾器生成完畢。

檢查階段：輸入一個(gè)對(duì)象如果k個(gè)位置有一個(gè)不為黑，則不再這個(gè)集合里面，布隆過濾器的失誤類型是寧可錯(cuò)殺三千，絕不放過一個(gè)

總結(jié)

以上是生活随笔為你收集整理的认识布隆过滤器的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。