认识布隆过滤器
通过一个案例来认识布隆过滤器
题目：
不安全的网页黑名单包含100亿个黑名单网页，每个网页最多占用64B。现在想要实现一个网页过滤器系统，可根据URL判断该网页是否在黑名单上。
要求：
- 该系统允许有一定的判断失误率（不高于万分之一）
- 使用的额外空间不超过30GB
首先认识哈希函数
- 典型的哈希函数都有无限的输入值域
- 当哈希函数传入相同的输入值时，返回值一样
- 给哈希函数传入不同的输入值时，返回值可能一样也可能不一样（输出域有限S）
- 很多不同的输入值所得到的返回值会均匀分布在S上（决定哈希函数的优略）
布隆过滤器
假设有一个长度为m的bit类型的数组，即数组中的每一个位置只占一个bit，如图
假设一共有K个哈希函数，这些函数的输出域S都大于或等于m，并且这些哈希函数都足够优秀，彼此之间完全独立。那么同一个输入对象（URL），经过K个哈希函数计算出来的结果也是独立的，可能相同，也可能不相同。对算出来的每一个结果都对m取余，然后在bit array上把相应的位置设置为1
把bit array记为bitMap。至此，一个输入对象的影响就结束了，也就是bitMap的一些位置会被涂黑，如果遇到黑的位置则继续为黑即可。处理完所有的对象后，bitMap中有相当多的位置被涂黑。至此，一个布隆过滤器就完成了。
如何检查对象是否该被过滤？
将该对象通过K个哈希函数算出K个值，然后把K个值取余（% m），就得到在[0~ m-1]上的K个值。接下来在bitMap上看这些位置是不是都为黑。如果有一个不为黑，那么就不会被过滤，如果这些位置都为黑，则被过滤（存在一定失误率，和bitMap大小有关）
解决开头提出的问题
100亿样本记为n；失误率不超过0.01%，记为p；每个样本大小64B
布隆过滤器的大小由以下公式确定：
m = - (n * lnp) / (ln2)^2
得到m 约等于 20n 约为25GB
哈希函数个数由以下公式确定：
k = ln2 * (m / n) = 0.7 * (m / n)
k = 14
用25GB的bitMap，再单独实现14个哈希函数即可生成所需的布隆过滤器
失误率： (1 - e^ (-nk / m))^k 约为0.006%