概述
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进位制向量和一系列随机对映函式，布隆过滤器可以用于检索一个元素是否在一个集合中。如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素储存起来，然后通过比较确定。连结串列，树等等资料结构都是这种思路. 但是随着集合中元素的增加，我们需要的储存空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过还有一种叫作散列表(又叫杂凑表，Hash table)的资料结构，它可以通过一个Hash函式将一个元素对映成一个位阵列中的一个点，这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
算法
1、首先需要k个hash函式，每个函式可以把key杂凑成为1个整数；2、初始化时，需要一个长度为n位元的阵列，每个位元位初始化为0；
3、某个key加入集合时，用k个hash函式计算出k个杂凑值，并把阵列中对应的位元位置为1；
4、判断某个key是否在集合时，用k个hash函式计算出k个杂凑值，并查询阵列中对应的位元位，如果所有的位元位都是1，认为在集合中；
原理
布隆过滤器需要的是一个位数组（这个和位图有点类似）和k个对映函式（和Hash表类似），在初始状态时，对于长度为m的位阵列array，它的所有位都被置为0，如下图所示：
对于有n个元素的集合S={s1,s2......sn}，通过k个对映函式{f1,f2,......fk}，将集合S中的每个元素sj(11,g2......gk}，然后再将位阵列array中相对应的array[g1],array[g2]......array[gk]置为1：
如果要查询某个元素item是否在S中，则通过对映函式{f1,f2.....fk}得到k个值{g1,g2.....gk}，然后再判断array[g1],array[g2]......array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。
布隆过滤器优点
它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器储存空间和插入 / 查询时间都是常数O(k)。另外, 杂凑函式相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要储存元素本身，在某些对保密要求非常严格的场合有优势。
布隆过滤器缺点
但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位阵列变成整数阵列，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题
如何选择杂凑函式个数和布隆过滤器长度
过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。杂凑函式的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高
k 为杂凑函式个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。
应用场景
HTTP快取服务器、Web爬虫等主要工作是判断一条URL是否在现有的URL集合之中（可以认为这里的资料量级上亿）。对于HTTP快取服务器，当本地局域网中的PC发起一条HTTP请求时，快取服务器会先检视一下这个URL是否已经存在于快取之中，如果存在的话就没有必要去原始的服务器拉取资料了，这样既能节省流量，还能加快访问速度，以提高使用者体验。
对于Web爬虫，要判断当前正在处理的网页是否已经处理过了，同样需要当前URL是否存在于已经处理过的URL列表之中。
垃圾邮件过滤假设邮件服务器通过传送方的邮件域或者IP地址对垃圾邮件进行过滤，那么就需要判断当前的邮件域或者IP地址是否处于黑名单之中。如果邮件服务器的通讯邮件数量非常大（也可以认为资料量级上亿），那么也可以使用Bloom Filter算法。
Java实现布隆过滤器
先实现一个简单的布隆过滤器
这段程式码是构建了一个10亿位的bitSet，然后把一亿个userId加入到了我们的布隆过滤器中，最近判断5324512515这个userId是否登入，打出程式码的执行时间
