数据结构之BloomFilter

Bloom Filter
先看名字Filter,过滤器，说明这个数据结构主要是作为过滤器使用的。它可以判断一个元素是否在一个数据集里，如果它判断为否那么就一定不在，如果判断为是那么就可能存在。

Bloom Filter判断不存在是一定准确的，而判断在就可能不准确。所以它的使用场景是作为一个过滤器，可以把数据过滤为一定不存在的和可能存在的（存在一个错判率f,即有f的概率把不存在的判断为存在的）。

BloomFilter原理

我的理解是相较于hashSet, bloomFilter相当于只做了hash而不去做equals比较（所以判断否是一定准确的因为hash都不相同，判断为是那么还要进一步比较但是bloomFilter不会把原值存下来，所以没办法比较equal那么就存在误判了），一次hash函数的误判率还是比较高的，bloomFilter支持设置K个Hash函数。

下面看一个例子来说明其原理
定义一个n位的数组和k个hash函数(n=8,k=2)，两个hash函数分别为K1,K2

image
image

从上图我们就可以看出bloomFilter的特点了

1. 占用空间小（只要一个位数组记录0和1）
2. 查找的效率高,时间复杂度位O(k),k为上述说的哈希函数个数.

缺点：

1. 判断存在不可信（有误判的概率）
2. 不可删除（因为数组中的每一个1都可能是好几个元素共用的）

公式
参数
m:bit数组长度
n:加入bloomFilter的元素个数
k:hash函数个数
p（fpp）:误判率

image

最优k:
    

image

代入最优K后

image

Guava的BloomFilter
create方法

 // 如果只设置n,会默认设置f=0.03
 public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
    return create(funnel, expectedInsertions, 0.03); // FYI, for 3%, we always get 5 hash functions
  }
  
  public static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp) {
    return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
  }
  
   @VisibleForTesting
  static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    ... //some check
    if (expectedInsertions == 0) {
      expectedInsertions = 1;
    }
    // 计算m
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    // 计算k
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

通常我们只需要指定预定放入的元素数量n，和误判率f。 会算出要达到这个误判率需要设置的m和k。

  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)));
  }

 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)));
  }
  

BloomFilter可以节省大量的空间，但会带来一定的误判率，通常用于数据量较大的时候。