Bloom Filter的使用--亿级元素查找缺失的元素

看了几篇大神的文章后，特异记录下心得

Bloom Filter 有如下几个特点：

1.只要返回数据不存在，则肯定不存在
2.返回数据存在，但只能是大概率存在
3.同时不能清除其中的数据
它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难；所以用来排查大量数据中缺少哪些数据是比较好的选择。

实现原理

下图详解：
如何去判断值是否存在数组中

bloomFilter 初始 bloomFilter

1.初始化一个长度为L的二进制的数组，值全部设为0；
2.当写入一个A1=1000的数据时，需要进行H次的hash函数运算（这里定义为两次），通过算出hashcode与L取模定位到0和2，并将值设为1。
3.A2=2000也是同理计算后定位到4和7，值设为1。
4.当一个值B1=1000需要判断是否存在时，也是需要做两次的hash运算，定位到0和2，此时他们的值都为1，那么B1=1000存在集合中。
5.当B2=3000时，也是同理，进行两次hash运算，第一次定位到4，值为1；所以进行第二次hash运算，第二次定位到5，值为0；所以B2=3000不存在集合中。

具体应用

4.网络应用

  1）P2P网络中查找资源操作，可以对每条网络通路保存Bloom Filter，当命中时，则选择该通路访问。

  2）广播消息时，可以检测某个IP是否已发包。

  3）检测广播消息包的环路，将Bloom Filter保存在包里，每个节点将自己添加入Bloom Filter。

 4）信息队列管理，使用Counter Bloom Filter管理信息流量。

5. 垃圾邮件地址过滤

    像网易，QQ这样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。

一个办法就是记录下那些发垃圾邮件的 email地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。

如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个email地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB的内存。

而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。

BloomFilter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。

简单代码实现