一.什么是布隆过滤器

  布隆过滤器可以用于检索一个元素是否在一个集合中,主要是解决大规模数据下不需要精确过滤的场景，如检查垃圾邮件地址，爬虫URL地址去重，解决缓存穿透问题等。

 

原理讲解

1.结构

布隆过滤器底层就是一个二进制的位数组，在初始状态，所有位置的位都是0.

2.添加过程

多个哈希函数计算多个位置的值用来减少hash冲突带来的误判性

1. 使用哈希函数对元素进行哈希计算得到索引值，将索引值对应的数组下标所在的值设置为1
2. 如果是多个哈希函数则进行上述同样的操作.

3.查询过程

1. 对要查询的元素同样使用哈希函数进行计算，如果存在多个哈希函数则得到多个索引值
2. 判断这些索引值对应的数组下标的值是否都为1，如果是，则判断这个元素为存在。如果这些下标的值只要有一个是0，那么判断这个元素为不存在

优点

• 空间与时间复杂度低:存储空间和插入 / 查询时间都是常数O(k) .
• 存储空间小: 不存储数据本身，而是存储hash结果取模运算后的位标记
• 支持海量数据: 支持海量数据场景下高效率判断元素是否存在.

缺点

• 无法删除: 因为可能多个元素通过哈希后，可能会产生hash碰撞，映射到布隆过滤器的同一个位置。删除该位置后，可能影响其他元素
• 误判: 由于存在hash碰撞，不同的元素经过哈希后可能映射到同一个位置，一旦产生碰撞，会被误判存在
• 碰撞概率: 让随着元素越来越大，在容量限制下，布隆过滤器被使用的位置就会越来越多，误判的几率也会越来越大

误判性及解决办法

布隆过滤器存在误判性:
  由于存在hash碰撞，不同的元素经过哈希后可能映射到同一个位置，比如如果A,B都映射到同一个位置,A存在,B不存在,对B进行判存时就会把A存在的结果返回给B,导致B误判.这就有一个特点:
不存在一定不存在,存在不一定存在

解决办法:
  1.采用多个hash函数计算出多个位置,所有位置的值都为1才判断为存在,否则不存在.

  2.在布隆过滤器判断存在时在数据库中查询相关数据是否真实存在.

 
 

二.springboot整合redisson布隆过滤器组件

1.添加依赖

在pom.xml文件中添加

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

2.定义布隆过滤器属性配置

application.yml里面添加redis配置和布隆过滤器配置:

spring:
  data:
    redis:
      database: 0
      host: 127.0.0.1
      port: 6379
      password: 123456
      timeout: 3000
      
bloom-filter:
  name: bloom-filter
  expectedInsertions: 1000
  falseProbability: 0.01

定义配置属性类:

@Data
@ConfigurationProperties(prefix = BloomFilterProperties.PREFIX)
public class BloomFilterProperties {

    public static final String PREFIX = "bloom-filter";
    /**
    * 布隆过滤器名字
    */
    private String name;
    /**
    * 布隆过滤器的容量
    */
    private Long expectedInsertions = 20000L;
    /**
    * 布隆过滤器碰撞率
    */
    private Double falseProbability = 0.01D;
}

3.将布隆过滤器注册到Bean中

/**
 * 布隆过滤器 配置
 **/
@EnableConfigurationProperties(BloomFilterProperties.class)
public class BloomFilterAutoConfiguration {
    /**
     * 布隆过滤器
     */
    @Bean
    public RBloomFilter<String> rBloomFilterUtil(RedissonClient redissonClient, BloomFilterProperties bloomFilterProperties) throws Exception {

        RBloomFilter<String> rBloomFilter = redissonClient.getBloomFilter(
                "自定义布隆过滤器前缀" + "-" + bloomFilterProperties.getName());
        boolean initialized  = rBloomFilter .tryInit(bloomFilterProperties.getExpectedInsertions(),
                bloomFilterProperties.getFalseProbability());
        if (!initialized) {
            throw new Exception("Failed to initialize Bloom Filter" );
        }
        return rBloomFilter ;
    }
}

4.使用布隆过滤器

将布隆过滤器注册到Bean之后就可以通过依赖注入获取到它了.

// 直接注入Redisson布隆过滤器
@Autowired
private RBloomFilter<String> rBloomFilter;

 

5.常用API

添加元素:boolean isSuceess = rBloomFilter.add(data);
检查是否包含某个元素:boolean isContained = rBloomFilter.getExpectedInsertions();
获取当前已插入的元素数量:long count = rBloomFilter.count();
获取误判率:double falseProbability = rBloomFilter.getFalseProbability();
获取位数组大小:long size = rBloomFilter.getSize();
 

  老铁觉得有用就点个赞吧😊💓🤪