題目：不安全網頁的黑名單包含100億個黑名單網頁，每個網頁的url最多占用64b.現在想要實現一個網頁過濾系統，利用該系統可以根據網頁的URL判斷該網頁是否在黑名單上，請設計該系統

要求：

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

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

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

布隆過濾器的優勢在于使用很少的空間就可以將準確率做到很高的程度

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

處理完所有輸入對象之后，bitMap已經有很多位置被涂黑，因此一個布隆過濾器生成完畢。

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

總結

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

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。