布隆過(guò)濾器

不安全網(wǎng)頁(yè)的黑名單包含100億個(gè)黑名單網(wǎng)頁(yè)，每個(gè)網(wǎng)頁(yè)的URL最多占用64字節(jié)，現(xiàn)在想要實(shí)現(xiàn)一種網(wǎng)頁(yè)過(guò)濾系統(tǒng)，可以根據(jù)網(wǎng)頁(yè)的URL判斷該網(wǎng)頁(yè)是否在黑名單上，請(qǐng)?jiān)O(shè)計(jì)該系統(tǒng)。
要求該系統(tǒng)允許有萬(wàn)分之一以下的判斷失誤率，并且使用的額外空間不要超過(guò)30G。

解決方法采用布隆過(guò)濾器

黑名單----存入>哈希表或者數(shù)據(jù)庫(kù)
數(shù)量：100億
單個(gè)url：64kB    那么應(yīng)該需要640G的空間，不
符合要求。

生成布隆過(guò)濾器的過(guò)程：

布隆過(guò)濾器的生成過(guò)程.png