Skip to main content

什么是布隆过滤器？

作者：程序员马丁

在线博客：https://open8gu.com

note

大话面试，技术同学面试必备的八股文小册，以精彩回答应对深度问题，助力你在面试中拿个offer。

回答话术​

布隆过滤器是一种数据结构，用于快速判断一个元素是否存在于一个集合中。它以牺牲一定的准确性为代价，换取了存储空间的极大节省和查询速度的显著提升。

具体来说，布隆过滤器包含一个位数组和一组哈希函数。位数组的初始值全部置为 0。在插入一个元素时，将该元素经过多个哈希函数映射到位数组上的多个位置，并将这些位置的值置为 1。

image.png

因为每个元素存储都是以位来存储，而不是字节，所以元素的占用空间非常小。

1 字节（Byte）= 8 位（Bit）在计算机科学中，数据存储的最小单位是位（Bit），而字节（Byte）则是一个常用的数据存储单位，通常由 8 个位组成。

在查询一个元素是否存在时，会将该元素经过多个哈希函数映射到位数组上的多个位置，如果所有位置的值都为 1，则认为元素存在；如果存在任一位置的值为 0，则认为元素不存在。

布隆过滤器的优点在于它可以高效地判断一个元素是否属于一个大规模集合，且具有极低的存储空间要求。如果存储 1 亿元素，误判率设置为 0.001 也就是千分之一，仅需要占用 171M 左右的内存。

缺点在于可能会存在一定的误判率。

它在实际应用中常用于缓存场景下缓存穿透问题，对访问请求做一个快速判断机制。使用布隆过滤器能够有效减轻对底层存储系统的访问以及缓存系统的存储压力。

但是布隆过滤器本身也存在一些“弊端”，那就是不支持删除元素。因为它是一种基于哈希的数据结构，删除元素会涉及到多个哈希函数之间的冲突问题，这样会导致删除一个元素可能会影响到其他元素的正确性。

总的来说，布隆过滤器是一种非常高效的数据结构，适用于那些可以容忍一定的误判率的场合。

问题详解​

布隆过滤器内存占用预估参考网站：Bloom Filter Calculator sourl.cn/ZJdP9W

image.png

如何判断这个数据的真实性？很简单，你在设置好参数初始化布隆过滤器时，它会初始化一个位数组，这个容量是固定的且一次性申请对应容量的内存。

经过实际测试，基本与上述网站评估一致。另外和大家说个小 Tips，Redisson 布隆过滤器在 Redis 中是以字符串方式存储的，底层数据结构是 Redis 中的 BitSet（位图）。

image.png

网上布隆过滤器有很多种，比如 Guava 的内存布隆过滤器以及 Redisson 分布式（基于 Redis）布隆过滤器，从实际场景实战上来说，本地内存相对来说更宝贵些，一般都是基于 Redisson 的分布式布隆过滤器。

备注：Redisson 和 Redis 之间的关系。Guava 操作的布隆过滤器是基于 JVM 内存，每次新增都是在 JVM 加一条数据，而 Redisson 则是操作 Redis 进行存储以及查询。

image.png

为了更好了解布隆过滤器，我们就以 SpringBoot 项目整合 Redisson 布隆过滤器来演示。

1. 引入 Redisson SpringBoot Starter 依赖包​

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.21.3</version>
</dependency>

<dependency>
    <groupId>org.springframework.boot</groupId>
    <artifactId>spring-boot-starter-data-redis</artifactId>
    <!-- 默认从SpringBoot父版本中传递依赖 -->
</dependency>

2. 配置文件中填充 Redis 相关参数​

spring:
  data:
    redis:
      host: 127.0.0.1
      port: 6379

3. 创建布隆过滤器实例​

假设我们布隆过滤器场景用来防止检查用户是否重复时查询数据库，创建示例如下所示：

import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

/**
 * 布隆过滤器配置
 */
@Configuration
public class RBloomFilterConfiguration {

    /**
     * 防止检查用户是否重复时查询数据库的布隆过滤器
     */
    @Bean
    public RBloomFilter<String> userRegisterCachePenetrationBloomFilter(RedissonClient redissonClient) {
        RBloomFilter<String> cachePenetrationBloomFilter = redissonClient.getBloomFilter("userRegisterCachePenetrationBloomFilter");
        cachePenetrationBloomFilter.tryInit(100000000L, 0.001);
        return cachePenetrationBloomFilter;
    }
}

比较核心的就是 tryInit 方法，在这里我们不过多分析，详情参考：✅ 布隆过滤器容量如何评估？

以及系统使用过程中，布隆过滤器容量不够了怎么办？详情参考：✅ 布隆过滤器容量不够用如何解决？

4. 代码中如何使用布隆过滤器​

因为已经把布隆过滤器声明成 Spring 的 Bean 对象了，所以我们可以通过依赖注入的方式将 Bean 引入到我们的业务类中即可。

@Service
public class AService {

    @Autowired
    private RBloomFilter<String> userRegisterCachePenetrationBloomFilter;

    public void testBloomFilter() {
        // 新增数据到布隆过滤器中
        userRegisterCachePenetrationBloomFilter.add("公众号@马丁玩编程");
        // 判断元素是否存在布隆过滤器
        boolean hasUsername = userRegisterCachePenetrationBloomFilter.contains("公众号@马丁玩编程");
    }
}

Table of Contents