布隆过滤器

面对的问题：网页黑名单系统，垃圾邮件过滤系统，爬虫的网址判重系统，系统有一定程度的失误率，但是对空间要求比较严格。

1，建立一个长度为m的bit类型的数组，长度由公式 

2，创建k个哈希函数，

哈希函数要好好设计，并且相互独立。

3，对我们所拥有的100亿个黑名单逐个用这些哈希函数处理，每一个黑名单处理之后都会生成k个值，在m位的bit类型数组上，把对应的值涂黑，标为1.

4，对新输入的值进行判别，用k个哈希函数进行处理，然后查看这k个结果在m位的bit类型数组上是否都为黑色（1），如果都为黑，则就是黑名单中的地址。

5，布隆过滤器会有误报，对已发现的误报样本可以通过建立白名单来防止误报。比如，已经发现“aaaa5”这个样本不在布隆过滤器中，但是每次计算后的结果都显示其在布隆过滤器中，那么就可以把这个样本加入到白名单中，以后就可以知道这个样本确实不在布隆过滤器中。