Bpazy
commented
1 year ago 布隆过滤器的误判
误判率的近似公式:
其中 k 为 hash 函数个数，n 为数字个数。
如何确定最优的m和k？
知道原理后再来了解下怎么去实现，我们在决定使用Bloomfilter之前，需要知道两个数据，一个是要存储的数量n和预期的误判率p。bitmap的大小m决定了存储空间的大小，hash函数个数k决定了计算量的大小，我们当然都希望m和k都越小越好，如何计算二者的最优值，我们大概来推导下。（备注：推导过程来自Wikipedia）
由上文可知，误判率p为
对于给定的m和n我们想让误判率p最小，就得让
把(2)式代入(1)中可得
对(3)两边同时取ln并简化后，得到
最后可以计算出m的最优值为
因为误判率p和要插入的数据量n是已知的，所以我们可以直接根据上式计算出m的值，然后把m和n的值代回到(2)式中就可以得到k的值。至此我们就知道了实现一个bloomfilter所需要的所有参数了，接下来让我们看下Google guava包中是如何实现BloomFilter的。
guava中的BloomFilter
BloomFilter无法通过new去创建新对象，而它提供了create静态方法来生成对象，其核心方法如下。
static <T> BloomFilter<T> create(
Funnel<? super T> funnel, long expectedInsertions, double fpp, Strategy strategy) {
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);
checkNotNull(strategy);
if (expectedInsertions == 0) {
expectedInsertions = 1;
}
long numBits = optimalNumOfBits(expectedInsertions, fpp);
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);
}
}从代码可以看出，需要4个参数，分别是：
- funnel 用来对参数做转化,方便生成hash值
- expectedInsertions 预期插入的数据量大小，也就是上文公式中的n
- fpp 误判率，也就是上文公式中的误判率p
- strategy 生成hash值的策略，guava中也提供了默认策略，一般不需要你自己重新实现
从上面代码可知，BloomFilter创建过程中先检查参数的合法性，之后使用n和p来计算bitmap的大小m（optimalNumOfBits(expectedInsertions, fpp)），通过n和m计算hash函数的个数k（optimalNumOfHashFunctions(expectedInsertions, numBits)）,这俩方法的具体实现如下。
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)));
}
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)));
}参考：
miximixi2
布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在 1970 年提出的，它实际上是由一个很长的二进制向量和一系列随机hash映射函数组成（说白了，就是用二进制数组存储数据的特征）。
譬如下面例子：有三个hash函数，那么“陈六”就会被三个hash函数分别hash，并且对位数组的长度，进行取余，分别hash到三个位置。