什么是布隆过滤器？你学会了吗？

2023-01-31 51CTO

前言

如果要判断一个元素是否在集合中，一般的思路是保存集合中的所有元素，然后通过比较来确定。链表、树、哈希表（也叫哈希表、哈希表）等数据结构都是这种方式，存储位置要么是磁盘，要么是内存。很多时候，要么时间换空间，要么空间换时间。

在对响应时间要求比较严格的情况下，如果我们有里面，那么随着集合中元素数量的增加，我们需要的存储空间越来越大，检索时间也越来越长，导致内存过多开销和时间效率变低。

这时候需要考虑的问题是，在数据量比较大的情况下，既能满足时间要求，又能满足空间要求，所以我们需要一种时间和空间消耗都比较小的数据结构和算法。布隆过滤器是一种解决方案。

什么是布隆过滤器？

Bloom Filter, 布隆过滤器由 Bloom于 1970 年提出。它实际上是一个长二进制向量和一系列随机映射函数, 布隆过滤器可用于检索元素是否在集合中。其优点是空间效率和查询时间远超一般算法，缺点是存在一定的误识别率和删除难度。根据它的特性，应用场景有如下：

爬虫过滤。
邮箱垃圾邮件过滤。
黑名单过滤。
大数据去重。
防止缓存穿透。

布隆过滤器原理

布隆过滤器的原理是当一个元素加入到集合中时，通过K个哈希函数将该元素映射到一个位数组中的K个点，并将它们置为1。检索时，我们只需要看这些点是否都为1，就可以（大概）知道它是否存在于集合中。如果这些点中的任何一个有0，则检查的元素一定不存在。如果它们都是1，则被选中的元素很可能在那里。

Bloom Filter与单一哈希函数Bit-Map的区别在于，Bloom Filter使用k个哈希函数，每个字符串对应k个bits，从而降低碰撞概率。

由于Bloom filter只存储0和1而不存储具体值，所以在一些机密场合具有先天优势。位图的每一位都是一个位，所以通过位图有10亿个位置，位图的大小为0.12G，插入和查询的时间复杂度为O(k),k是哈希函数的个数。

布隆过滤器的问题

布隆过滤器之所以能够在时间和空间上取得比较高的效率，是因为它牺牲了判断的准确性和删除的便利性。

判断错误

有可能要找的元素不在容器中，但是散列后得到的k个位置都是1。如果布隆过滤器中存储了黑名单，则可以通过创建白名单来存储可能被误判的元素。

对于这个问题，可以通过增加位图数组的大小（位图数组越大，占用的内存越大）和减少哈希冲突来解决。但缺点是会增加占用的内存空间。

另一种解决方案是增加散列函数的数量并减少散列冲突。如果同一个键值等于一个函数，经过两个或多个哈希函数得到相等结果的概率自然会降低。然而，这会导致计算效率的降低，因为时间复杂度退化为O(hash times)。

难以去除

放置在容器中的元素映射到位数组的 k 个位置中的 1。删除的时候不能简单的直接设置为0，这样可能会影响其他元素的判断。你可以使用Counting Bloom Filter来解决这个问题。

JAVA中如何使用布隆过滤器

google的guava就提供了这样的API.

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

编写测试代码

import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
 
public class GuavaBloomFilter {
    public static void main(String[] args) {
        int total = 1000000;
        // default false positive ratefpp0.03
        // fpp:There will always be a false positive rate in a Bloom filter
        // Because hash collisions are impossible to avoid 100%.
        // Bloom filter calls this misjudgment rate false positive probability，abbreviated as fpp
        BloomFilter<CharSequence> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
        // Initialize the total bar data into the filter
        for (int i = 0; i < total; i++) {
            bf.put("" + i);
        }
        // Determine whether the value exists in the filter
        int count = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bf.mightContain("" + i)) {
                count++;
            }
        }
        System.out.println("Matched quantity " + count);
 
        // Specified misjudgment rate: 1/10,000 to improve matching accuracy
        BloomFilter<CharSequence> bfWithFpp = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);
        for (int i = 0; i < total; i++) {
            bfWithFpp.put("" + i);
        }
        int countFpp = 0;
        for (int i = 0; i < total + 10000; i++) {
            if (bfWithFpp.mightContain("" + i)) {
                countFpp++;
            }
        }
        //The smaller the value of the false positive rate fpp
        // the higher the matching accuracy.
        // When the value of the false positive rate fpp is reduced
        // the storage space required is also larger
        // Therefore, in actual use, 
        // a trade-off needs to be made between the false positive rate and the storage space.
        System.out.println("The specified false positive rate has matched the number " + countFpp);// (1000001 - 1000000)/(1000000 + 10000) * 100 ≈ 0.0001
    }
}