BloomFilter

Bloom Filter是由Bloom在1970年提出的一种多哈希函数映射的快速查找算法。通常应用在一些需要快速判断某个元素是否属于集合,但是并不严格要求100%正确的场合。

简介

Bloom Filter是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

原理

初始状态

下面我们来看Bloom Filter是如何用位素组来表示集合的。初始状态下,Bloom Filter是一个包含m位的位数组Bit Vector,每一位都是0。

添加元素

往数组中添加一个元素x时,用k个独立的、均匀分布的哈希函数

$$h_1(),h_2(), \cdots h_k()$$

对元素x进行哈希,假设得到k个结果如下

$$h_1(x)=8,h_2(x)=11, \cdots h_k(x)=3$$

则把位数组上对应的位置为1,这样就把元素x映射到位数组中的k个二进制位了。(当某个位被重复置为1时,以第一次置1为准)

检查元素是否存在

当需要判断元素y是否属于这个集合时,同样用上面的k个哈希函数对y进行哈希,得到结果

$$h_1(y),h_2(y), \cdots h_k(y)$$

然后检查位数组中对应的位是否为1,若其中任何一位不为1,则表示不存在。若全部为1,怎表示“可能”存在,这里之所以是“可能”是因为若一个元素对应的Bit全为1,实际上是不能100%的肯定该字符串被Bloom Filter记录过的,因为有可能该字符串的所有位都刚好是被其他字符串所对应。这种将该字符串划分错的情况就称为false positive。

注意:Bloom Filter中的元素是不能被删除的,因为如果把该元素对应的位置为0,会影响集合中的其他元素。针对删除功能有一个简单的改进,即Counting Bloom Filter。

错误率估计

由于存在false positive,因此我们需要选择合适得数组大小及哈希函数个数,来使得我们的Bloom Filter的错误率尽可能的低。这里我们省去负责的数学公式推导过程,直接给出结论:

  • m  Bit Vector位数
  • n  元素数量
  • k  哈希函数个数
  • f  False Positive比率(错判率)

以上参数满足下面的公式:

$$(1-(1-\frac{1}{m})^{kn})^k \approx (1-e^{\frac{-kn}{m}})^k$$

当给定m和n时,能够使f最小化的k值为:

$$ \frac{m}{n}ln(2) \approx 0.7\frac{m}{n} $$

此时f的值为:

$$(\frac{1}{2})^k \approx 0.6185^\frac{m}{n} $$

根据以上公式,对于任意给定的f,可以得到:

$$n = m\frac{ln(0.6185)}{ln(f)} $$

同时k的值为:

$$k = -\frac{ln(f)}{ln(2)} $$

其中k必须为整数,最后可以得到实际f值为:

$$f = (1 - e^{-\frac{kn}{m}})^k $$

以上三个公式是Bloom Filter的关键公式。

实际应用

Bloom Filter在很多地方都有实现,如redis,python,guava等。这次是一个线上项目需求,不需要长久运行,数据量大概千万级别,最后决定选择guava来实现。在其源码中有一个类叫BloomFilter,可以看出BloomFilter的使用非常简单,create接口如下:

1
2
3
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp) {
return create(funnel, expectedInsertions, fpp, BloomFilterStrategies.MURMUR128_MITZ_64);
}

第一个参数funnel,在Funnels类中已经选择自己需要的实例(你可以简单的理解为类型过滤器)。如元素是long型时就选择Funnels.longFunnel()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static Funnel<Long> longFunnel() {
return LongFunnel.INSTANCE;
}
private enum LongFunnel implements Funnel<Long> {
INSTANCE;
public void funnel(Long from, PrimitiveSink into) {
into.putLong(from);
}
@Override
public String toString() {
return "Funnels.longFunnel()";
}
}

第二个参数表示元素的数量,第三个参数表示设定的错误率。创建BloomFilter之后简单的使用put()方法插入元素,使用mightContain()方法查询元素是否存在。

注:经过测试,1000万的long型数据,大约需要300m不到的内存。