布隆过滤器是1970年油Burton Howard Bloom提出的。它主要运用在大数据量的情况下例如数据库，不需要将全部数据加载到内存而是通过加载一个空间较小的位数组来判断某个数据是否存在，即提高了效率（在内存直接判断）又节省了空间；但是由此带来的弊端是它得出的结论并不是百分百正确，而是有一定的概率。

更精确一点说：

1. 当布隆过滤器判断某个数据不存在的时候，它肯定不存在。
2. 当布隆过滤器判断某个数据存在的时候，它有可能不存在。

实现原理

布隆过滤器内部是通过一个位数组和若干个哈希函数实现的，下图中表示我们的系统中有x,y,z和w四个数，每个数通过三个哈希函数生成哈希数值后更新到位数组上（将位数组相应位置的设置为1）。

数x生成的三个哈希值（蓝色线指向）为1、5、13，因此将位数组的相应索引位置的值设置为1；y，z和w也是如此。

假设此时我们要判断数u在不在系统中，数u生成的三个哈希值分别为1、3、4，虽然此时位数组索引位置1、3、4的值都是1，布隆过滤器判断可能存在，但是u并不在数据集合中，所有布隆过滤器存在着一定的误判。

假设此时另一个数v生成的三个哈希值分别为0、3、4，此时索引0位置的值为0，我们可以肯定v不在系统中。

理论支持

如何提高布隆过滤器的效率归根结底就是降低它的误判率（false positive probability），假设给定了系统中数的个数以及误判率，Burton Howard Bloom已经给我们推导出了如下公式：（具体推到逻辑可以参考文末维基百科链接）

m = - n * lnp / (ln2) ^ 2
k = m * ln2 / n;

其中：m表示位数组的长度，k表示哈希函数的个数，n表示系统中数的个数，p表示false positive probability

典型例子

google的guava工具包中提供了BloomFilter的实现，并且默认是采用了128位murmer3哈希算法逻辑：

// 默认采用128位murmer3哈希算法
public static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp) {
    return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}

//计算位数组长度
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)));
}

注意点

布隆过滤器不支持删除，当系统中的数据删除后，布隆过滤器是无法判断并清除内部位数组的标记，所以一般需要定期的进行重建来维持较低的false positive probability。

参考文章

https://en.wikipedia.org/wiki/Bloom_filter

Tags：math.max()

微信扫一扫：分享

微信里点“发现”，扫一下

二维码便可将本文分享至朋友圈。