布隆过滤器是一种多哈希函数映射的快速查找算法，实际由一个二进制向量和一系列hash函数组成。主要用于检索一个元素是否属于集合，但并不严格要求100%正确的场合。
- 优点：空间和时间效率上远超一般算法，适合大数据场景
- 缺点：存在一定误识别率(即假正例，False positives)，集合的元素删除困难
典型的应用场景有：
- 爬虫的url判重
- 垃圾邮件过滤
- 网页黑名单系统
算法思想
创建一个m位的BitSet，先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对元素e哈希的结果记为h(i,e)，且h(i,e)的范围是0到m-1。
加入元素的过程
先对元素e分别计算k个哈希函数h(1,e)，h(2,e)，…，h(k,e)的值，然后将BitSet的h(1,e)，h(2,e)，…，h(k,e)为置为1。最后再加入到集合中。
(图片来源于网络，侵删)检索元素是否存在
同样先对元素e分别计算k个哈希函数h(1,e)，h(2,e)，…，h(k,e)的值，然后检查BitSet的第h(1,e)，h(2,e)，…，h(k,e)是否为1。若其中任何一位不为1则判定该元素没有被记录过，若全部都为1则可认为元素存在。
注意：若元素对应的bit全为1，实际上不能100%肯定该元素被布隆过滤器记录，因为有可能该元素对于的所有bit刚好被其他元素覆盖。
- 删除过程
布隆过滤器是不支持删除操作的，因为删除会影响到其他元素的检索。但有一种Bloom Filter的变体Counting Bloomfilter支持删除操作，CBF实际是将Bloom Filter的每一位Bit改为一个计数器，添加时将对于位加1，删除时减1。
注意：删除时必须保证元素是在集合中的，这点单凭布隆过滤器无法判断，需要到集合中检索。
参数选择
如何根据预测输入元素n的级别和期望失误率p确定布隆过滤器bitSet的大小m和哈希函数的个数k。它们之间存在最优解的情况，直接给出公式
$$ m=-\frac{(n \times \ln p)} {(\ln2)^2} $$
$$ k=\ln 2 \times \frac {m} {n} $$
布隆过滤器的真实失误率为：
$$ p=(1-e^{-\frac {nk} {m}}) $$
源码实现
这是一个用Java简单实现的布隆过滤器Github。该实现能根据期望失误率和预测输入元素级别，计算最优参数构造布隆过滤器。