布隆过滤器

杨大大...大约 6 分钟

布隆过滤器

概述

**布隆过滤器（Bloom Filter）**是一种空间高效的数据结构，用于判断一个元素是否在集合中。它由布隆在1970年提出，因此得名。

布隆过滤器的基本思想是，利用多个不同的哈希函数将一个元素映射到多个不同的位（或桶）上，并将这些位设置为1。当查询一个元素是否在布隆过滤器中时，将这个元素进行哈希操作，得到多个哈希值，并检查这些哈希值对应的位是否都为1。如果有任意一个位为0，则可以确定该元素不在布隆过滤器中；如果所有位都为1，则不能确定该元素一定在布隆过滤器中，因为可能存在哈希冲突，即不同的元素被映射到了相同的位上。

可以简单地将布隆过滤器理解为Set集合（其实他们之间差别还是很大的），可以向里边存放元素，然后判断元素是否存在。

布隆过滤器的优点：

  • 时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
  • 保密性强，布隆过滤器不存储元素本身
  • 存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）（存在一种叠加）

布隆过滤器的缺点：

  • 有一定的误判率，但是可以通过调整参数来降低

  • 无法获取元素本身，只能判断是否存在

  • 很难删除元素

适用场景

  • 解决Redis缓存穿透问题
  • 网络爬虫的网址去重
  • 数据库中的数据查询优化
  • 内容推荐，推荐过的不重复推荐

布隆过滤器的原理

如上图，同一个数据经过三个不同的哈希函数获得不同的存储位置，然后将对应索引里的值改为1，只有三个索引对应的值都为1才能说明值已存在，有其中一个不为1都不行。可以试想，当哈市算法为1时，一个数据只对应一个索引，只要那个索引值为1就说明存在，由于哈希冲突的存在，出现误判的可能性是较大的，随着哈希函数数量增多，所需要的储存空间也越多，一个数值需要判断的索引也越多，自然出现误判的几率就小了。（存储01的为二进制数组）

当有多个数值存储时，就是下图的叠加情况

所以这也是为什么很难删除的原因，因为多个数值可能会用到同一索引，一旦删除其中一个就会导致严重误删。

小结：

  • 哈希函数越多，所需存储空间越大，计算时间越长，误判率越低

空间计算

布隆过滤器提供两个参数，一个是预计存储元素个数n，一个是误判率。在添加元素之前，布隆过滤器有着初始的存储空间，也就是二进制数组的长度。当添加元素时，布隆过滤器会根据我们填入的这两个参数计算出二进制数组的大小以及hash函数的个数，既要满足我们的要求，又要使空间和计算量的开销都减到最小。

在SpringBoot中使用

添加依赖

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>30.1-jre</version>
</dependency>
<dependency>
   <groupId>com.github.mgunlogson.cuckoofilter</groupId>
   <artifactId>cuckoofilter</artifactId>
   <version>0.3.2</version>
</dependency>

guava是Google开发的一个Java工具库，提供了许多实用的工具类和方法，包括布隆过滤器。cuckoofilter是一个开源的Java布隆过滤器实现。（cuckoofilter是布谷鸟过滤器）

创建布隆过滤器

import com.google.common.hash.Hashing;
import com.google.common.hash.Funnels;
import com.github.mgunlogson.cuckoofilter4j.CuckooFilter;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;

@Component
public class BloomFilter {
    @Value("${bloomfilter.expectedInsertions}")
    private int expectedInsertions; //期望插入数量

    @Value("${bloomfilter.fpp}")
    private double fpp; //误判率，这里都是在配置文件中配置了

    private CuckooFilter<String> filter;//布谷鸟过滤器

    @PostConstruct
    public void init() {
        filter = new CuckooFilter.Builder<>(Funnels.stringFunnel())
                .withFalsePositiveProbability(fpp)
                .withExpectedInsertions(expectedInsertions)
                .build();
    }
//判断是否存在
    public boolean mightContain(String element) {
        return filter.mightContain(element);
    }
//添加元素
    public void add(String element) {
        filter.put(element);
    }
}

这里使用CuckooFilter实现了布隆过滤器（准确来说这里应该布叫谷鸟过滤器），使用guava提供的Hashing和Funnels类来计算元素的哈希值和将元素转换为字节数组。在init方法中，我们初始化了布隆过滤器，设置了期望的插入数量和误判率。在mightContain方法中，我们检查元素是否可能存在于布隆过滤器中。在add方法中，我们将元素添加到布隆过滤器中。

在使用布隆过滤器时，需要根据实际情况来选择合适的误判率和期望插入数量。误判率越低，布隆过滤器的大小就越大，且添加元素的时间也越长。期望插入数量越大，布隆过滤器的大小也就越大，但误判率会减小。

简单使用

实现布隆过滤器的示例代码：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        int expectedInsertions = 1000000;//期望插入元素数量
        double fpp = 0.01;//期望误差率

        BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(), expectedInsertions, fpp);

        // 添加元素到布隆过滤器中
        bloomFilter.put("apple");
        bloomFilter.put("banana");
        bloomFilter.put("orange");

        // 判断元素是否在布隆过滤器中
        System.out.println(bloomFilter.mightContain("apple"));   // true
        System.out.println(bloomFilter.mightContain("pear"));    // false
        System.out.println(bloomFilter.mightContain("banana"));  // true
        System.out.println(bloomFilter.mightContain("orange"));  // true
    }
}

解决Redis缓存穿透逻辑

创建布隆过滤器（布谷鸟过滤器）

import com.google.common.hash.Hashing;
import com.google.common.hash.Funnels;
import com.github.mgunlogson.cuckoofilter4j.CuckooFilter;
import org.springframework.beans.factory.annotation.Value;
import org.springframework.stereotype.Component;
import javax.annotation.PostConstruct;

@Component
public class BloomFilter {
    @Value("${bloomfilter.expectedInsertions}")
    private int expectedInsertions;

    @Value("${bloomfilter.fpp}")
    private double fpp;

    private CuckooFilter<String> filter;

    @PostConstruct
    public void init() {
        filter = new CuckooFilter.Builder<>(Funnels.stringFunnel())
                .withFalsePositiveProbability(fpp)
                .withExpectedInsertions(expectedInsertions)
                .build();
    }

    public boolean mightContain(String element) {
        return filter.mightContain(element);
    }

    public void add(String element) {
        filter.put(element);
    }
}

缓存查询时的逻辑

在缓存查询时，我们首先使用布隆过滤器过滤掉不存在的数据，如果数据可能存在于缓存中，我们再去查询缓存。

@Autowired
private RedisTemplate<String, Object> redisTemplate;

@Autowired
private BloomFilter bloomFilter;

public Object getValue(String key) {
    // 先检查布隆过滤器中是否存在该key
    if (!bloomFilter.mightContain(key)) {
        return null;
    }

    // 查询缓存
    ValueOperations<String, Object> ops = redisTemplate.opsForValue();
    Object value = ops.get(key);

    // 如果缓存中不存在该key，将其添加到布隆过滤器中
    if (value == null) {
        bloomFilter.add(key);
    }

    return value;
}

参考：https://blog.csdn.net/2301_79205460/article/details/131916961open in new window

© 2023-present 鲁ICP备19028049号
Copyright © 2024 杨大大