这里是布隆过滤器的讲解。
首先先看以下题目：
题目
不安全网页的黑名单包含 100 亿个，每个网页的 URL 最多占用 64 字节。现在想要实现一种网页过滤系统，可以根据网页的 URL 判断该网页是否在黑名单上，请设计该系统。要求该系统允许有万分之一以下的判断失误率，并且使用的额外空间不要超过 30 G。
传统方法
使用哈希表或者数据库。
一个 URL 为 64 Byte ，100 亿个就是 6400 亿 Byte ，也就是 640G 的空间，不符合要求。
改进方法——布隆过滤器
如果遇到网页黑名单，垃圾邮件过滤系统，爬虫的网址判断重复系统，并且这些系统容忍一定程度的失误率，而且还对空间有要求，那么应该是用布隆过滤器。
布隆过滤器
什么是布隆过滤器
布隆过滤器可精确的代表一个集合，可精确的判断某一个元素是否在此集合中。值得注意的是，这里是精确不是准确，至于精确的程度，完全取决于我们对布隆过滤器的设计。
而且，布隆过滤器由于自身的局限性是不可能做到 100% 正确的。
布隆过滤器的特点
布隆过滤器的优势在于，利用很少的空间可以做到精确率较高。
布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，false positive rate(误报率)越大，但是false negative (漏报)是不可能的。
布隆过滤器原理
如图所示：
注意点
当有多个哈希函数加工后得到同一个点，则那个点最终为 1。
如果 URL 过于多，那么一定会产生，不同的 URL 最终生成的 bitarray 相同，这也是它的局限性所在。
布隆过滤器相应参数的计算
bitarray 的大小如何确定
假设 bitarray 的大小为 m ，样本数量为 n，失误率为 p。
题目中要求，n = 100 亿，p = 0.01%
单个样本的大小不影响布隆过滤器的大小，只影响了哈希函数的实现细节。（每个 URL 长度不一样。）
如下公式计算 m 。
最终 m = 19.9n，向上取整为 20n。
即为 2000亿个 bit ，约 25 G。
计算哈希函数的个数
公式如下：
最终 k = 14
失误率
因为我们在上一步有一个向上取整，所以实际失误率是比原来的万分之一更小，则实际失误率的公式如下：
最后实际的失误率为 0.006%
注意点
布隆过滤器的主体就是一个超级大的数组，而不是很多小数组的集合。
