0 布隆过滤器
布隆过滤器由Burton Howard Bloom于1970年提出。一个布隆过滤器代表一个集合，可以判断一个元素是否在集合中，但这种判断不是精准的判断，即存在误判率，具体误判率是多少取决布隆过滤器结构的设计。
1 哈希函数
哈希函数的输入域可以是非常大的范围，比如，任意一个字符串，但是输出域得范围是固定的，假设为S。哈希函数具有以下性质：
- 理论上哈希函数的输入域是无限的。
- 当哈希函数的输入值相同时，其输出值也是相同的。
- 当哈希函数的输入值不同时，其输出值可能相同也可能不同。
一个好的哈希函数应尽量使输入域的输出域均匀分布在S上。
2 布隆过滤器
假设有一个长度为m的bit类型的数组（记为bitarr，数组的每个位置只占一个bit的空间）。如下图所示：
再假设一共有k个哈希函数，这些函数的输出域S都大于或等于m，并且这些哈希函数都足够优秀，彼此之间也完全独立。那么对同一个输入对象（假设是一个字符串），经过此k个哈希函数计算出来的结果也是独立的。对计算出来的k个结果都对m取余，然后在bitarr上把相应的位置设为1（涂黑）。如下图所示：
将所有的输入对象都按照上述同样方式映射到bitarr中，这样一个布隆过滤器就建立完成了。
在检查阶段如何判断一个对象是否之前已经存在呢？假设待判断的对象为a，首先用k个哈希函数分别计算a的输出值；然后对这k个输出值取余（对m取余），将输出值映射到区间[0, m - 1]范围内；接着检查bitarr上k个对应的位置是不是都为黑，如果有一个不为黑，说明a肯定不在这个集合内；如果k个位置全为黑，表明a有可能在这个集合中，也可能不在。易知如果bitarr的容量m远小于输入数据的大小n时，布隆过滤器判断出错的概率就会很大，因此如何根据输入数据的大小n以及期望的误判率p设计合适的bitarr和哈希函数的数量是布隆过滤器性能好坏的关键。
3 布隆过滤器的大小
我们称bitarr的大小为布隆过滤器的大小。布隆过滤器大小由下面的公式确定：
哈希函数的个数由一下公式确定：
关于上述两个公式的分析一般不用掌握，有兴趣的可参考书籍《程序员代码面试指南：IT名企算法与数据结构题目最优解》左程云著。
4 布隆过滤器的应用
题目
不安全网页的黑名单包含100亿个黑名单网页，每个网页的URL最多占64B。现在想要实现一种网页过滤系统，可以根据网页的URL判断该网页是否在黑名单上，请设计该系统。
要求
- 该系统允许有万分之一以下的误判率
- 使用的额外空间不要超过30GB
分析
如果把黑名单上的所有URL通过数据库或哈希表保存下来，就可以对每条URL进行查询，但是本题的数据所占的内存大约是640GB的空间，因此该方法是不可行的。
解决方案——布隆过滤器
黑名单中样本个数为10亿，记为n；假定误判率不超过0.01%，记为p；根据公式，布隆过滤器的大小m为19.9n，向上取整为20n，即需要2000亿个比特位，大约为25GB，空间限制满足题目要求。哈希函数的个数为14个。当布隆过滤器建立完成后，查询一个对象是否已经存在的时间复杂度为\(O(k)\)
5 参考
- 《程序员代码面试指南：IT名企算法与数据结构题目最优解》，左程云著。