布隆过滤器

布隆过滤器是一种由位数组和多个哈希函数组成概率数据结构，返回两种结果 可能存在 和 一定不存在。

布隆过滤器里的一个元素由多个状态值共同确定。位数组存储状态值，哈希函数计算状态值的位置。

根据它的算法结构，有如下特征：

使用有限位数组表示大于它长度的元素数量，因为一个位的状态值可以同时标识多个元素。
不能删除元素。因为一个位的状态值可能同时标识着多个元素。
添加元素永远不会失败。只是随着添加元素增多，误判率会上升。
如果判断元素不存在，那么它一定不存在。

比如下面，X,Y,Z 分别由 3个状态值共同确定元素是否存在，状态值的位置通过3个哈希函数分别计算。

面试官问：什么是布隆过滤器？

数学关系

误判概率

关于误判概率，因为每个位的状态值可能同时标识多个元素，所以它存在一定的误判概率。如果位数组满，当判断元素是否存在时，它会始终返回true，对于不存在的元素来说，它的误判率就是100%。

那么，误判概率和哪些因素有关，已添加元素的数量，布隆过滤器长度（位数组大小），哈希函数数量。

根据维基百科推理误判概率 (P_{fp}) 有如下关系：

[{ P_{fp} =left(1-left[1-{frac {1}{m}}right]^{kn}right)^{k}approx left(1-e^{{-frac {kn}{m}}}right)^{k}} ]

(m) 是位数组的大小；
(n) 是已经添加元素的数量；
(k) 是哈希函数数量；
(e) 数学常数，约等于2.718281828。

由此可以得到，当添加元素数量为0时，误报率为0；当位数组全都为1时，误报率为100%。

不同数量哈希函数下，$ P_{fp}$ 和 $ n$ 的关系如下图：

面试官问：什么是布隆过滤器？

根据误判概率公式可以做一些事

估算最佳布隆过滤器长度。
估算最佳哈希函数数量。

最佳布隆过滤器长度

当 (n) 添加元素和 (P_{fp})误报概率确定时，(m) 等于：

[{displaystyle m=-{frac {nln P_{fp}}{(ln 2)^{2}}} approx -1.44cdot nlog _{2}P_{fp}} ]

最佳哈希函数数量

当 (n) 和 (P_{fp}) 确定时，(k) 等于：

[{displaystyle k=-{frac {ln P_{fp} }{ln 2}}=-log _{2}P_{fp} } ]

当 (n) 和 (m) 确定时，(k) 等于：

[{displaystyle k={frac {m}{n}}ln 2} ]

实现布隆过滤器

使用布隆过滤器前，我们一般会评估两个因素。

预期添加元素的最大数量。
业务对错误的容忍程度。比如1000个允许错一个，那么误判概率应该在千分之一内。

很多布隆过滤工具都提供了预期添加数量和误判概率配置参数，它们会根据配置的参数计算出最佳的长度和哈希函数数量。

Java中有一些不错的布隆过滤工具包。

Guava 中 BloomFilter。
redisson 中 RedissonBloomFilter 可以redis 中使用。

看下 Guava 中 BloomFilter 的简单实现，创建前先计算出位数组长度和哈希函数数量。

 static <T> BloomFilter<T> create(
      Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
    /**
     * expectedInsertions：预期添加数量
     * fpp：误判概率
     */
    long numBits = optimalNumOfBits(expectedInsertions, fpp);
    int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    try {
      return new BloomFilter<T>(new BitArray(numBits), numHashFunctions, funnel, strategy);
    } catch (IllegalArgumentException e) {
      throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", e);
    }
  }

根据最佳布隆过滤器长度公式，计算最佳位数组长度。


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) {
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
  }

在redisson 中 RedissonBloomFilter 计算方法也是一致。

    private int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
      }

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