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不到的内存。