什么是布隆过滤器？原理及JAVA用法

terry 2年前 (2023-09-27) 阅读数 85 #数据结构与算法

当想要判断某个元素是否在集合中时，一般的思路就是存储集合中的所有元素，然后通过比较来判断。链表、树、哈希表（也称散列表、散列表）等数据结构都是这样，存储位置是磁盘或者内存。通常要么用时间换取空间，要么用空间换取时间。

在响应时间要求严格的情况下，当我们在的时候，随着集合中元素数量的增加，我们需要的存储空间越来越大，检索时间也越来越长，导致内存溢出。更多的开销和更低的时间效率。

此时要考虑的问题是，当数据量比较大时，能够同时满足时间和空间的要求。所以我们需要一种占用更少时间和空间的数据结构和算法。布隆过滤器是一种解决方案。

什么是布隆过滤器？

布隆过滤器，布隆过滤器是由Bloom于1970年提出的。它基本上是一个长二进制向量和一系列任意映射函数，允许使用布隆过滤器来检索元素是否在集合中。优点是空间效率和搜索时间比一般算法大很多，缺点是存在一定程度的误识别和删除问题。根据特性的不同，应用场景如下：

爬虫过滤。
邮箱垃圾邮件过滤。
黑名单过滤。
大数据重复删除。
防止缓存渗透。

布隆过滤器原理

布隆过滤器的原理是，当一个元素被添加到集合中时，该元素通过K个哈希函数被分配到一个位数组中的K个点，并且这些点被设置为1。在检索时，我们只需要检查这些点是否全为 1，我们就可以（粗略地）知道它是否存在于集合中。如果这些点中的任何一个为 0，则所检查的元素不应存在。如果它们都为 1，则所选元素很可能存在。

Bloom Filter 与单一哈希函数的 Bit-Map 的区别在于，Bloom Filter 使用了 k 个哈希函数，每个字符串对应 k 位，减少了冲突的机会。

由于布隆过滤器只存储0和1，不存储具体值，因此在一些保密情况下具有先天的优势。位图的每一位都是一个位，因此位图中有 10 亿个位置。位图的大小为0.12G。插入和检索的时间复杂度是O(k)，k是哈希函数的数量。。

布隆过滤器的问题

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

判断错误

有可能你要找的元素不在容器中，但是哈希后得到的k个位置全是1。如果布隆过滤器中存储了黑名单，可以创建白名单保存可能误判的元素。

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

另一个解决方案是增加哈希函数的数量，减少哈希冲突。如果相同的键值等于一个函数，那么通过两个或多个哈希函数获得相同结果的概率会明显降低。然而，随着时间复杂度退化为 O（哈希时间），这会导致计算效率降低。

难以移除

放置在容器中的元素在位数组的k个位置上被分配为1。删除时不能直接将其设置为0，否则可能会影响其他元素的评估。可以使用计数布隆过滤器来解决这个问题。

在Java中使用Bloom Filter

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
    }
}