布隆过滤器原理简介_布隆过滤器的原理

1、基本概念

本质上是一种数据结构，比较巧妙的概率型数据结构，本身是一个很长的二进制向量，存放的不是0就是1。特点是高校的插入和查询，可以用来告诉你“某样东西一顶不存在或者可能存在”。主要用来判断某一元素在某一集合中存不存在；相比于传统的List，Set，Map等数据结构，他更高效、占中空间更少，而缺点是返回的结果不一定完全正确，具有一定的误判率。

2、示例

布隆过滤器是一个bit向量或者说bit数组，长这样：

如果我们要映射一个值到布隆过滤器种，需要使用多个hash函数生成多个hash值，并对数组长度取模，得到数组下标，并把改下标的值置为1，例如百度，三个hash函数分别生成1、4、7：

再存一个值“tencent”，如果通过hash函数计算到下标为3、4、8：

下标为4 的这个位置都被这两个值占有了。当我们查询别的值，例如“didi”，返回了1，6，7，结果发现6这个位置上为0，说明这个值不存在；当我们在查询baidu这个值是否存在的时候，三个位置都为1，那么baidu一定存在么？不一定，baidu这个值可能存在。因为随着增加的值越来越多，被置为1的位置越来越多，具有一定概率的误判性。（不同值计算出来的hash值有可能相同，hash值不同，原值一定不同）

3、影响误判的几个因素

hash函数个数k，布隆过滤器长度m，插入的元素个数n，p为误报率

4、guava实现的BloomFilter

 /** The bit set of the BloomFilter (not necessarily power of 2!)*/
  private final BitArray bits; // 底层的bit数组

  /** Number of hashes per element */
  private final int numHashFunctions; // hash函数个数

  /** The funnel to translate Ts to bytes */
  private final Funnel<T> funnel; // 将输入的过滤器其他类型的对象转换成字节
  /**
   * The strategy we employ to map an element T to {@code numHashFunctions} bit indexes.
   */
  private final Strategy strategy;// 将元素映射到bit数组上的策略
1
2
3
4
5
6
7
8
9
10
11
12
13

bits即上文讲到的长度为m的位数组，采用LockFreeBitArray类型做了封装。
numHashFunctions即哈希函数的个数k。
funnel是Funnel接口实现类的实例，它用于将任意类型T的输入数据转化为Java基本类型的数据（byte、int、char等等）。这里是会转化为byte。
strategy是布隆过滤器的哈希策略，即数据如何映射到位数组，其具体方法在BloomFilterStrategies枚举中。

BloomFilter提供了create静态方法来创建BloomFilter实例 ：

 public static <T> BloomFilter<T> create(
      Funnel<T> funnel, int expectedInsertions /* n */, double fpp) {
    checkNotNull(funnel);
    checkArgument(expectedInsertions >= 0, "Expected insertions (%s) must be >= 0",
        expectedInsertions);
    checkArgument(fpp > 0.0, "False positive probability (%s) must be > 0.0", fpp);
    checkArgument(fpp < 1.0, "False positive probability (%s) must be < 1.0", fpp);
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    /*
     * TODO(user): Put a warning in the javadoc about tiny fpp values,
     * since the resulting size is proportional to -log(p), but there is not
     * much of a point after all, e.g. optimalM(1000, 0.0000000000000001) = 76680
     * which is less than 10kb. Who cares!
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel,
          BloomFilterStrategies.MURMUR128_MITZ_32);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

该方法接受4个参数：funnel是插入数据的Funnel，expectedInsertions是期望插入的元素总个数n，fpp即期望假阳性率p，strategy即哈希策略。
由上可知，位数组的长度m和哈希函数的个数k分别通过optimalNumOfBits()方法和optimalNumOfHashFunctions()方法来估计。

计算最优值：bit数组长度和hash函数个数：

 /**
     * 根据要插入的数据量和误判率，计算数组的总长度
     * @param n
     * @param p
     * @return
     */
    static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
    
    /**
     * 根据要插入的数据量和总长度，计算hash函数个数
     * @param n
     * @param m
     * @return
     */
    static int optimalNumOfHashFunctions(long n, long m) {
        // (m / n) * log(2), but avoid truncation due to division!
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5、总结

1、布隆过滤器具有查找效率高，占用内存少的特点
2、缺点是具有一定的误判率，可以参考guava的实现确定数组长度m和hash函数个数k
3、本文只是对布隆过滤器原理和guava的实现方式做了简介，其中hash算法策略、计算m和k的算法有待深究

参考
https://www.jianshu.com/p/bef2ec1c361f
https://www.jianshu.com/p/2104d11ee0a2
https://blog.csdn.net/zc19921215/article/details/91047708