题目描述：

不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占用64字节。现在想要实
现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统，要求该系
统允许有万分之一以下的判断失误率，并且使用的额外空间不超过30G。

布隆过滤器

简介

布隆过滤器可以精确的代表一个集合，可精确判断某一元素是否在此集合中。
精确程度由用户的具体设计决定，不能做到100%准确。
-布隆过滤器的优势在于，利用很少的空间，可以做到精确率较高

构建布隆过滤器

首先定义一个bitarray数组，下标从0到m-1，每个位置为一个bit，默认为0.然后利用k个哈希函数（输出与>=m，函数各自独立）。将某一URL依次分别输入到k个哈希函数中，得到k个结果，全部对m取余。然后将bitarray相应的位置上的值设置为1.这样便得到了此URL在数组中的记录。依次将100亿个URL全部进行如上操作，最终得到了黑名单布隆过滤器。

查询集合中是否含有指定元素

拿到一个新的URL，将其作为输入依次输入到k个哈希函数中，得到的结果对m取余，最终得到k个值，然后去bitarray数组中查看这k个值的位置是否为1，如果有一个不为1，则说明集合中不存在该URL，如果全部为1，则认为集合中含有该URL。

参数选择

bitarray大小为m，样本数量为n，失误率为p

m相对于n越大，验证结果越准确，单个样本大小不影响过滤器大小，只影响哈希函数的实现细节。

计算m公式

计算哈希函数的数量k：

计算k公式

求得m之后，计算p的公式如下：

计算p公式