速了解及使用布隆过滤器

科技前沿 • 2025-03-04 22:33 • 阅读 30

大家好，我是讯享网，很高兴认识大家。

布隆过滤器

介绍

概念：是一种高效查询的数据结构

作用：判断某个元素是否在一个集合中。（但是会出现误判的情况）

实现原理

加入元素：

当一个元素需要加入到布隆过滤器中时，会使用一组哈希函数对该元素进行计算，得到多个哈希值。

每个哈希值对应到位数组的一个特定位置，将这些位置的值设置为1。

查询元素：

对给定的元素再次进行相同的哈希计算，得到一组哈希值。

检查位数组中对应的每个位置是否都为1。如果所有位置都是1，那么认为这个元素可能在布隆过滤器中；如果有任何一个位置不为1，那么可以确定该元素不在布隆过滤器中。

误判和不可删除

下面是一个插入元素的图：

讯享网

模拟插入：

先插入“你好”
1. 计算“你好”的hash值
2. 插入到2的位置
插入“hello”
1. 计算“hello”的hash值
2. 插入到2的位置

误判：如果计算出“hello”和“你好”的hash值是一样的，这个时候就会出现误判的情况。
不能删除：当发现“你好”和“hello”的值都在2位置，如果要删除“你好”的hash值在布隆过滤器中，那么“hello”也会同时被删除。

使用场景

使用在缓存穿透场景。

可以利用布隆过滤器先看看数据是否存在，再进行下一步的判断，可能可以减少很多次的数据库访问请求。

if(!bloomFilter.contains(data)){    //..... }

讯享网

一般采用上述这种方式进行布隆过滤器的判断。

原因：布隆过滤器可能存在误判

当布隆过滤器中不存在一个数据的时候，那么这个数据肯定不存在。
当布隆过滤器存在一个数据的时候，可能这个数据还是存在的。

补充缓存穿透：

讯享网前端请求要查询一个数据，但是Redis中没有这个数据，所以要将请求打到数据库中。如果是大量请求情况，这个大的流量，可能导致数据库直接挂了。（一般可以采用布隆过滤器+分布式锁防止缓存穿透）

布隆过滤器使用

Guava的布隆过滤器
Redis实现的布隆过滤器

这里以Redis的布隆过滤器作示例：

1、引入依赖

<dependency>   <groupId>org.springframework.boot</groupId>   <artifactId>spring-boot-starter-data-redis</artifactId> </dependency>  <dependency>   <groupId>org.redisson</groupId>   <artifactId>redisson-spring-boot-starter</artifactId> </dependency>

2、配置Redis参数

讯享网spring: data:   redis:     host: 127.0.0.1     port: 6379 #     password:  #密码

3、布隆过滤器的配置类：

import org.redisson.api.RBloomFilter; import org.redisson.api.RedissonClient; import org.springframework.boot.context.properties.EnableConfigurationProperties; 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("xxx");        cachePenetrationBloomFilter.tryInit(0, 0);        return cachePenetrationBloomFilter;   } }

tryInit 有两个核心参数：

expectedInsertions：预估布隆过滤器存储的元素长度。
falseProbability：运行的误判率

这里是一个计算误判率和大小的网站：Bloom Filter Calculator

4、代码中的使用

讯享网private final RBloomFilter<String> userRegisterCachePenetrationBloomFilter;

add方法添加
contains方法判断是否存在