布隆过滤器 Bloom Filter

它主要用于解决判断一个元素是否在一个集合中，优势在于只需要占用很小的内存空间以及有着高效的查询效率。

1.原理

它是一个保存了很长的二级制向量，同时结合 Hash 函数实现的。

如上图所示：

首先需要初始化一个二进制的数组，长度设为 L（图中为 8），同时初始值全为 0 。
当写入一个 A1 = 1000 的数据时，需要进行 H 次 Hash 函数的运算（这里为 2 次）；与 HashMap 有点类似，通过算出的 HashCode 与 L 取模后定位到 0、2 处，将该处的值设为 1。
A2 = 2000 也是同理计算后将 4、7 位置设为 1。
当有一个 B1 = 1000 需要判断是否存在时，也是做两次 Hash 运算，定位到 0、2 处，此时他们的值都为 1 ，所以认为 B1 = 1000 存在于集合中。
当有一个 B2 = 3000 时，也是同理。第一次 Hash 定位到 index = 4 时，数组中的值为 1，所以再进行第二次 Hash 运算，结果定位到 index = 5 的值为 0，所以认为 B2 = 3000 不存在于集合中。

整个的写入、查询的流程就是这样，汇总起来就是：对写入的数据做 H 次 Hash 运算定位到数组中的位置，同时将数据改为 1 。

当有数据查询时也是同样的方式定位到数组中。一旦其中的有一位为 0 则认为数据肯定不存在于集合，否则数据可能存在于集合中。

2.特点

只要返回数据不存在，则肯定不存在。
返回数据存在，但只能是大概率存在。
同时不能清除其中的数据。

第一点应该都能理解，重点解释下 2、3 点。为什么返回存在的数据却是可能存在呢，这其实也和 HashMap 类似。

在有限的数组长度中存放大量的数据，即便是再完美的 Hash 算法也会有冲突，所以有可能两个完全不同的 A、B 两个数据最后定位到的位置是一模一样的。

这时拿 B 进行查询时那自然就是误报了。删除数据也是同理，当我把 B 的数据删除时，其实也相当于是把 A 的数据删掉了，这样也会造成后续的误报。

基于以上的 Hash 冲突的前提，所以 Bloom Filter 有一定的误报率，这个误报率和 Hash 算法的次数 H，以及数组长度 L 都是有关的。

3.自己实现一个布隆过滤

算法其实很简单不难理解，于是利用 Java 实现了一个简单的雏形：

首先初始化了一个 int 数组。
写入数据的时候进行三次 Hash 运算，同时把对应的位置置为 1。

查询时同样的三次 Hash 运算，取到对应的值，一旦值为 0 ，则认为数据不存在。

  public class BloomFilters {
  
      /**
       * 数组长度
       */
      private int arraySize;
  
      /**
       * 数组
       */
      private int[] array;
  
      public BloomFilters(int arraySize) {
          this.arraySize = arraySize;
          array = new int[arraySize];
      }
  
      /**
       * 写入数据
       * @param key
       */
      public void add(String key) {
          int first = hashcode_1(key);
          int second = hashcode_2(key);
          int third = hashcode_3(key);
  
          array[first % arraySize] = 1;
          array[second % arraySize] = 1;
          array[third % arraySize] = 1;
  
      }
  
      /**
       * 判断数据是否存在
       * @param key
       * @return
       */
      public boolean check(String key) {
          int first = hashcode_1(key);
          int second = hashcode_2(key);
          int third = hashcode_3(key);
  
          int firstIndex = array[first % arraySize];
          if (firstIndex == 0) {
              return false;
          }
  
          int secondIndex = array[second % arraySize];
          if (secondIndex == 0) {
              return false;
          }
  
          int thirdIndex = array[third % arraySize];
          if (thirdIndex == 0) {
              return false;
          }
  
          return true;
  
      }

/**
* hash 算法1
* @param key
* @return
/
private int hashcode_1(String key) {
int hash = 0;
int i;
for (i = 0; i < key.length(); ++i) {
hash = 33 * hash + key.charAt(i);
}
return Math.abs(hash);
}

/*
* hash 算法2
* @param data
* @return
/
private int hashcode_2(String data) {
final int p = 16777619;
int hash = (int) 2166136261L;
for (int i = 0; i < data.length(); i++) {
hash = (hash ^ data.charAt(i)) * p;
}
hash += hash << 13;
hash ^= hash >> 7;
hash += hash << 3;
hash ^= hash >> 17;
hash += hash << 5;
return Math.abs(hash);
}

/*
* hash 算法3
* @param key
* @return
*/
private int hashcode_3(String key) {
int hash, i;
for (hash = 0, i = 0; i < key.length(); ++i) {
hash += key.charAt(i);
hash += (hash << 10);
hash ^= (hash >> 6);
}
hash += (hash << 3);
hash ^= (hash >> 11);
hash += (hash << 15);
return Math.abs(hash);
}
}

测试类：

@Test
public void bloomFilterTest(){
    long star = System.currentTimeMillis();
    BloomFilters bloomFilters = new BloomFilters(10000000) ;
    for (int i = 0; i < 10000000; i++) {
        bloomFilters.add(i + "") ;
    }
    Assert.assertTrue(bloomFilters.check(1+""));
    Assert.assertTrue(bloomFilters.check(2+""));
    Assert.assertTrue(bloomFilters.check(3+""));
    Assert.assertTrue(bloomFilters.check(999999+""));
    Assert.assertFalse(bloomFilters.check(400230340+""));
    long end = System.currentTimeMillis();
    System.out.println("执行时间：" + (end - star));
}

大概三秒就可以写入1000W的数据，并返回判断。

当数组长度缩小到 100W 时就出现了一个误报，400230340 这个数明明没在集合里，却返回了存在。

这也体现了 Bloom Filter 的误报率。我们提高数组长度以及 Hash 计算次数可以降低误报率，但相应的 CPU、内存的消耗就会提高；这就需要根据业务需要自行权衡。