BloomFilter布隆过滤器的使用

布隆过滤器适合大数据判重的场景，如网络爬虫中判断一个URL是否已经爬取过，判断一个用户是否在黑名单中，判断一个邮件是否是垃圾邮件，等等。
优点：占用空间小，效率高，简而言之，就是以正确率换空间和时间。
缺点：有一定的误判率，一个URL经过布隆过滤器判断没爬取过，那么一定没爬取过，一个URL经过布隆过滤器判断爬取过，可能并没有爬取过，这种情况会有误判。
布隆过滤器本身是基于位图的，是对位图的一种改进，位图在java中的实现就是BitSet。

场景场景：

假设我们要写一个爬虫程序。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”，爬虫就会进入一个无限怪圈，找不到出路，程序出现崩溃。

所以为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL，也就是如何判重。

给一个URL，怎样知道蜘蛛是否已经访问过呢？按照我们的常识，就会有如下几种方案：

    将访问过的URL保存到数据库，数据库管理系统可以为你去重。用Set将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。URL经过MD5或SHA-1等单向哈希后再保存到Set或数据库。Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。

    方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。

以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。

    方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？
    方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，至少需要5GB内存，还不包括Set数据结构中的内存浪费。
    方法3的缺点：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。
    方法4的缺点：消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。

若要降低冲突发生的概率到1%，有种办法就是就要将BitSet的长度设置为URL个数的100倍。

假设一亿条URL，就得把BitSet长度设为100亿，过于稀疏也是很费内存的

    实质上上面的算法都忽略了一个重要的隐含条件：允许小概率的出错，不一定要100%准确！
    也就是说少量url实际上没有没网络爬虫访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。

Bloom Filter 算法原理

方法四的致命缺点是冲突概率高，为了降低冲突的概念，Bloom Filter使用了多个哈希函数，而不是一个。

为什么可以降低呢？我们知道Hash函数有一定几率出现冲突，概率假设为 p1，我们知道p1是一个很小的几率，但是在数据量大之后冲突就会变多，也就是上面第四种方法的问题。
BoomFilter使用 多个Hash函数 分别冲突概率为 p2 p3 p4 p5 .... pn ，我们知道不同 Hash函数处理同一个字符串彼此独立，所以冲突概率通过乘法公式得到为: p1p2p3p4p5p6.....pn，是相当相当小的了


预操作


创建一个m位BitSet（C++自带，Python为bitarray），先将所有位初始化为0，然后选择k个不同的哈希函数。第i个哈希函数对字符串str哈希的结果记为h（i，str），且h（i，str）的范围是0到m-1 。



Add操作

下面是每个字符串处理的过程，首先是将字符串str“记录”到BitSet中的过程：

对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后将BitSet的第h（1，str）、h（2，str）…… h（k，str）位设为1。


CHeck操作

根据上图，我们对每个字符串采用同样的算法。

下面是检查字符串str是否被BitSet记录过的过程：

    对于字符串str，分别计算h（1，str），h（2，str）…… h（k，str）。然后检查BitSet的第h（1，str）、h（2，str）…… h（k，str）位是否为1，若其中任何一位不为1则可以判定str一定没有被记录过。若全部位都是1，则“认为”字符串str存在。
    若一个字符串对应的Bit不全为1，则可以肯定该字符串一定没有被Bloom Filter记录过。（这是显然的，因为字符串被记录过，其对应的二进制位肯定全部被设为1了）


    但是若一个字符串对应的Bit全为1，实际上是不能100%的肯定该字符串被Bloom Filter记录过的。（因为有可能该字符串的所有位都刚好是被其他字符串所对应）这种将该字符串划分错的情况，称为wrong position。


Delete操作

字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用Counting bloomfilter(CBF)，这是一种基本Bloom Filter的变体，CBF将基本Bloom Filter每一个Bit改为一个计数器，这样就可以实现删除字符串的功能了。

考虑到BoomFilter上面的指标，总结一下有以下几个

    m ： BitSet 位数
    n ： 插入字符串个数
    k ：hash函数个数
    当然，哈希函数也是影响的重要因素

从表格来看 m/n越大越准，k越大越准。


BloomFilter的实现


java中的Guava工具包提供了BloomFilter的实现。

<dependency>
  <groupId>com.google.guava</groupId>
  <artifactId>guava</artifactId>
  <version>27.1-jre</version>
</dependency>

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.ArrayList;
import java.util.List;

public class Client {

  public static void main(String[] args) {
    int size = 1_000_000;
    BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size);
    for (int i = 0; i < size; i++) {
      bloomFilter.put(i);
    }
    for (int i = 0; i < size; i++) {
      if (!bloomFilter.mightContain(i)) {
        System.out.println("有坏人逃脱了");
      }
    }
    List<Integer> list = new ArrayList<>(1000);
    for (int i = size + 10000; i < size + 20000; i++) {
      if (bloomFilter.mightContain(i)) {
        list.add(i);
      }
    }
    System.out.println("有误伤的数量：" + list.size());
  }

}