@[TOC](【Redis】布隆过滤器(Bloom Filter))

【一】什么是布隆过滤器

【1】布隆过滤器的简单介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

可以把布隆过滤器理解为一个set集合，我们可以通过add往里面添加元素，通过contains来判断是否包含某个元素。由于本文讲述布隆过滤器时会结合Redis来讲解，因此类比为Redis中的Set数据结构会比较好理解，而且Redis中的布隆过滤器使用的指令与Set集合非常类似

【2】核心作用

（1）快速判断元素是否存在​：在常数时间内判断一个元素是否可能存在于集合中
（2）​空间效率高​：相比传统数据结构（如哈希表），布隆过滤器使用更少的内存
（3）​概率型数据结构​：可能存在误判（false positive），但不会漏判（false negative）
（4）如果布隆过滤器说元素不存在，则一定不存在
（5）如果布隆过滤器说元素存在，则可能存在（有一定概率误判）

【3】典型使用场景

（1）防止缓存穿透​：在查询缓存前先检查布隆过滤器，避免大量请求直接访问数据库
（2）URL去重​：在爬虫系统中快速判断URL是否已被爬取
（3）垃圾邮件过滤​：快速判断邮件地址是否在黑名单中
（4）分布式系统​：在分布式环境下快速判断数据是否存在
（5）推荐系统​：快速过滤用户已看过的内容

【4】布隆过滤器的优点

（1）时间复杂度低，增加和查询元素的时间复杂为O(N)，（，每个哈希函数的时间复杂度为O(1)，N为哈希函数的个数，通常情况比较小）
（2）保密性强，布隆过滤器不存储元素本身，只在数组中存储二进制数据0或者1来证明数据是否存在
（3）存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的（相比其他数据结构如Set集合）

【5】布隆过滤器的缺点

（1）有点一定的误判率，但是可以通过调整参数来降低
（2）无法获取元素本身
（3）很难删除元素

【二】布隆过滤器的使用场景

【1】判断某个元素是否存在

很多会后想到的是HashMap，确实可以把值映射到HashMap的Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。但是HashMap的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，而一旦数据量达到上亿的时候，那HashMap占据的内存大小就很大了。

如果想判断一个元素是不是在一个集合里，一般想到的是把集合中所有元素保存起来，然后通过比较确定。链表、树、哈希表等等数据结构都是这种思路。但是随着集合中元素的数量增加，我们需要的存储空间越来越大。同时检索速度也越来越慢，上述十年后总结构的检索时间复杂度分别为O(n)，O(log n)，O(1)。

【2】布隆过滤器的不同之处

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数把这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大概）知道集合中有没有这个元素了。如果这些点有任何一个0，则被检索的元素一定不存在。如果都是1，则被检索的元素很可能在。
本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构（probabilistic data structure）高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

当你往简单数组或列表中插入新数据时，将不会根据插入项的值来确定该插入项的索引值。这意味着新插入项的索引值与数据值之间没有直接关系。这样的话，当你需要在数组或列表中搜索相应值的时候，你必须遍历已有的集合。若集合中存在大量的数据，就会影响数据查找的效率。

针对这个问题，你可以考虑使用哈希表。利用哈希表你可以通过对 “值” 进行哈希处理来获得该值对应的键或索引值，然后把该值存放到列表中对应的索引位置。这意味着索引值是由插入项的值所确定的，当你需要判断列表中是否存在该值时，只需要对值进行哈希处理并在相应的索引位置进行搜索即可，这时的搜索速度是非常快的。

布隆过滤器可以告诉我们 “某样东西一定不存在或者可能存在”，也就是说布隆过滤器说这个数不存在则一定不存，布隆过滤器说这个数存在可能不存在（误判），**利用这个判断是否存在的特点可以做很多有趣的事情。

（1）解决Redis缓存穿透问题（面试重点）
（2）邮件过滤，使用布隆过滤器来做邮件黑名单过滤
（3）对爬虫网址进行过滤，爬过的不再爬
（4）解决新闻推荐过的不再推荐(类似抖音刷过的往下滑动不再刷到)
（5）HBase\RocksDB\LevelDB等数据库内置布隆过滤器，用于判断数据是否存在，可以减少数据库的IO请求

【3】布隆过滤器解决redis缓存穿透的问题

（1）问题描述

例如一个请求到达redis时，发现redis没有这个值，那么这个请求就会去访问数据库。但是如果是恶意的大量的请求一个根据不应该存在的值，那么就会有大量的请求直接到打到数据库上，则就是redis的缓存穿透问题。

（2）解决思路

（1）直接用redis存一个过期时间就可以，当通过某一个key去查询数据的时候，如果对应在数据库中的数据都不存在，我们将此key对应的value设置为一个默认的值，比如“NULL”，并设置一个缓存的失效时间，这时在缓存失效之前，所有通过此key的访问都被缓存挡住了。后面如果此key对应的数据在DB中存在时，缓存失效之后，通过此key再去访问数据，就能拿到新的value了。

（2）解决的目的就是防止大量的请求直接到数据库请求一些不存在的数据，那么就在redis和数据库之间加一个布隆过滤器，在过滤器中保存数据库经常被查询的数据，请求到这里会先在过滤器里判断是否存在请求的值，如果存在才会去访问数据库

【三】布隆过滤器的原理

【1】数据结构

（1）基本数据结构
布隆过滤器它实际上是一个很长的二进制向量和一系列随机映射函数。以Redis中的布隆过滤器实现为例，Redis中的布隆过滤器底层是一个大型位数组（二进制数组）+多个无偏hash函数。
一个大型位数组（二进制数组）：
（2）多个无偏hash函数
无偏hash函数就是能把元素的hash值计算的比较均匀的hash函数，能使得计算后的元素下标比较均匀的映射到位数组中。

如下就是一个简单的布隆过滤器示意图，其中k1、k2代表增加的元素，a、b、c即为无偏hash函数，最下层则为二进制数组。

（3）使用布隆过滤器的过程
二进制数组中使用0和1表示是否存在。

例如在存放”你好“这个字段的时候，会通过多个hash函数分别计算出多个不同的哈希值，不同的哈希值对应数组的下标值，并且把对应下标的二进制数据改为1。
在查找数据的时候，依然通过多个hash函数分别计算出多个不同的哈希值，如果所有哈希值对应数组中下标中的二进制值都为1，那么就可以证明存在”你好“这个数据，如果有至少一个二进制值为0， 就证明不存在。

【2】空间计算

在布隆过滤器增加元素之前，首先需要初始化布隆过滤器的空间，也就是上面说的二进制数组，除此之外还需要计算无偏hash函数的个数。布隆过滤器提供了两个参数，分别是预计加入元素的大小n，运行的错误率f。布隆过滤器中有算法根据这两个参数会计算出二进制数组的大小l，以及无偏hash函数的个数k。

计算关系：
（1）错误率越低，位数组越长，控件占用较大
（2）错误率越低，无偏hash函数越多，计算耗时较长

在线布隆过滤器计算的网址：https://krisives.github.io/bloom-calculator/

【3】增加元素

往布隆过滤器增加元素，添加的key需要根据k个无偏hash函数计算得到多个hash值，然后对数组长度进行取模得到数组下标的位置，然后将对应数组下标的位置的值置为1
（1）通过k个无偏hash函数计算得到k个hash值
（2）依次取模数组长度，得到数组索引
（3）将计算得到的数组索引下标位置数据修改为1

例如，key = Liziba，无偏hash函数的个数k=3，分别为hash1、hash2、hash3。三个hash函数计算后得到三个数组下标值，并将其值修改为1.
如图所示：

【4】查询元素

布隆过滤器最大的用处就在于判断某样东西一定不存在或者可能存在，而这个就是查询元素的结果。其查询元素的过程如下：
（1）通过k个无偏hash函数计算得到k个hash值
（2）依次取模数组长度，得到数组索引
（3）判断索引处的值是否全部为1，如果全部为1则存在（这种存在可能是误判），如果存在一个0则必定不存在

（1）为何产生误判
关于误判，其实非常好理解，hash函数在怎么好，也无法完全避免hash冲突，也就是说可能会存在多个元素计算的hash值是相同的，那么它们取模数组长度后的到的数组索引也是相同的，这就是误判的原因。

例如”hello“和”你好“的哈希值是相同的，那么对应的就是同一个下标的二进制值，如果此时已经存入了”你好“而没有存”hello“，其实在查询的时候也会得到存在”hello“的结果，这样也就产生了误判。所有能查到的不一定存在，查不到的一定不存在。

（2）如果减小误判的概率
调用guava包中的BloomFilter，设置参数，下面有案例

【5】修改元素

【6】删除元素

布隆过滤器对元素的删除不太支持，目前有一些变形的特定布隆过滤器支持元素的删除！关于为什么对删除不太支持，其实也非常好理解，hash冲突必然存在，删除肯定是很难的！

【四】redis中布隆过滤器指令使用

【1】bf.add：添加单个元素，成功返回1

127.0.0.1:6379> bf.add name liziba
(integer) 1

【2】bf.madd：添加多个元素

127.0.0.1:6379> bf.madd name liziqi lizijiu lizishi
1) (integer) 1
2) (integer) 1
3) (integer) 1

【3】bf.exists：判断元素是否存在，存在则返回1，不存在返回0

127.0.0.1:6379> bf.mexists name liziba
1) (integer) 1

【4】bf.mexists：判断多个元素是否存在，存在的返回1，不存在的返回0

127.0.0.1:6379> bf.mexists name liziqi lizijiu liziliu
1) (integer) 1
2) (integer) 1
3) (integer) 0

【五】Java集成redis使用布隆过滤器

Redis经常会被问道缓存击穿问题，比较优秀的解决办法是使用布隆过滤器，也有使用空对象解决的，但是最好的办法肯定是布隆过滤器，我们可以通过布隆过滤器来判断元素是否存在，避免缓存和数据库都不存在的数据进行查询访问！在如下的代码中只要通过bloomFilter.contains(xxx)即可，这里演示的还是误判率！

【1】引入pom依赖

        <!-- redis -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>
        <!-- 可选：Redis客户端使用Lettuce（默认）或Jedis，此处用Lettuce -->
        <dependency>
            <groupId>io.lettuce</groupId>
            <artifactId>lettuce-core</artifactId>
        </dependency>

【2】布隆过滤器config

package com.allen.study.common.config;

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

/**
 * @ClassName: BloomFilterConfig
 * @Author: AllenSun
 * @Date: 2025/8/24 01:15
 */
@Configuration
public class BloomFilterConfig {

    // 布隆过滤器名称常量
    private static final String BLOOM_FILTER_NAME = "productBloomFilter";
    // 预期插入数量，用于计算布隆过滤器所需大小
    private static final long EXPECTED_INSERTIONS = 1000000L;
    // 误判率，即布隆过滤器错误判断元素存在的概率
    private static final double FALSE_PROBABILITY = 0.01;

    /**
     * 创建布隆过滤器的Bean配置方法
     * @param redissonClient Redisson客户端，用于操作Redis
     * @return 配置好的布隆过滤器实例
     */
    @Bean
    public RBloomFilter<String> productBloomFilter(RedissonClient redissonClient) {
        // 使用Redisson创建布隆过滤器实例
        RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter(BLOOM_FILTER_NAME);
        // 初始化布隆过滤器，设置预期插入数量和误判率
        bloomFilter.tryInit(EXPECTED_INSERTIONS, FALSE_PROBABILITY);
        return bloomFilter;
    }
}

【3】布隆过滤器工具类

package com.allen.study.common.utils.redis;


import org.redisson.api.RBloomFilter;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Component;

/**
 * @ClassName: BloomFilterUtil
 * @Author: AllenSun
 * @Date: 2025/8/24 01:17
 */
@Component
public class BloomFilterUtil {

    private final RBloomFilter<String> bloomFilter;

    @Autowired
    public BloomFilterUtil(RBloomFilter<String> bloomFilter) {
        this.bloomFilter = bloomFilter;
    }

    /**
     * 添加元素到布隆过滤器
     */
    public void add(String element) {
        bloomFilter.add(element);
    }

    /**
     * 批量添加元素到布隆过滤器
     */
    public void addAll(Iterable<String> elements) {
        for (String element : elements) {
            bloomFilter.add(element);
        }
    }

    /**
     * 检查元素是否可能存在
     */
    public boolean mightContain(String element) {
        return bloomFilter.contains(element);
    }

    /**
     * 获取布隆过滤器的误判率
     */
    public double getFalseProbability() {
        return bloomFilter.getFalseProbability();
    }

    /**
     * 获取布隆过滤器的预期插入数量
     */
    public long getExpectedInsertions() {
        return bloomFilter.getExpectedInsertions();
    }

    public long count() {
        return bloomFilter.count();
    }

    public long getSize() {
        return bloomFilter.getSize();
    }
}

【4】布隆过滤器业务使用

    @Autowired
    private BloomFilterUtil bloomFilterService;

    private static final String CACHE_KEY_PREFIX = "employee:info:";
    private static final String RED_LOCK_PREFIX = "employee:lock:";

    @Override
    public EmployeeInfo queryById(String employeeInfoId) {
        // 根据主键查询用户信息表
        // 1. 检查布隆过滤器
        if (!bloomFilterService.mightContain(employeeInfoId)) {
            log.info("布隆过滤器中不存在该用户信息表，id:{}", employeeInfoId);
            return null;
        }
        log.info("布隆过滤器中存在该用户信息表，id:{}", employeeInfoId);

        // 1-先从 Redis 缓存中获取用户信息
        String cacheKey = CACHE_KEY_PREFIX + employeeInfoId;
        EmployeeInfoPO employeeInfoPO = (EmployeeInfoPO) redisTemplate.opsForValue().get(cacheKey);
        if (employeeInfoPO == null) {
            // 2-如果缓存中没有，则从数据库中获取
            employeeInfoPO = super.getById(employeeInfoId);
            if (employeeInfoPO != null) {
                // 3-将从数据库中获取的用户信息存入 Redis 缓存
                redisTemplate.opsForValue().set(cacheKey, employeeInfoPO, 60, TimeUnit.MINUTES);
            }
        }
        // 用户信息表持久化对象 转 用户信息表响应对象
        return employeeInfoPOAssembler.toEntity(employeeInfoPO);
    }

    @Override
    public void create(EmployeeInfo employeeInfo) {
        // 用户信息表实体转用户信息表持久化对象
        EmployeeInfoPO employeeInfoPO = employeeInfoPOAssembler.assembler(employeeInfo);

        long id = new SnowflakeGenerator().next().longValue();
        employeeInfoPO.setId(id);
        // 1. 创建用户信息表
        super.save(employeeInfoPO);
        log.info("用户信息存库成功：id：{}",id);
        // 2. 添加到布隆过滤器
        bloomFilterService.add(String.valueOf(id));
        log.info("用户信息存布隆过滤器成功：id：{}",id);
        // 3. 将用户信息存入 Redis 缓存
        String cacheKey = CACHE_KEY_PREFIX + id;
        redisTemplate.opsForValue().set(cacheKey, employeeInfoPO, 60, TimeUnit.MINUTES);
        log.info("用户信息存redis成功：id：{}",id);
    }

    @Override
    public void createBatch(List<EmployeeInfo> employeeInfos) {
        // 用户信息表实体转用户信息表持久化对象
        List<EmployeeInfoPO> employeeInfoPOs = employeeInfoPOAssembler.assembler(employeeInfos);
        for (EmployeeInfoPO employeeInfo : employeeInfoPOs) {
            long id = new SnowflakeGenerator().next().longValue();
            employeeInfo.setId(id);
        }
        // 1. 创建用户信息表
        super.saveBatch(employeeInfoPOs);
        // 2. 添加到布隆过滤器
        List<String> allEmpIdList = employeeInfoPOs.stream().map(it -> it.getId().toString()).collect(Collectors.toList());
        bloomFilterService.addAll(allEmpIdList);
        // 3. 将用户信息存入 Redis 缓存
        for (EmployeeInfoPO employeeInfoPO : employeeInfoPOs) {
            String cacheKey = CACHE_KEY_PREFIX + employeeInfoPO.getId();
            redisTemplate.opsForValue().set(cacheKey, employeeInfoPO, 60, TimeUnit.MINUTES);
        }

    }

【5】初始化布隆过滤器

package com.allen.study.application.api;

import com.allen.study.common.base.ApiResponse;
import com.allen.study.common.utils.redis.BloomFilterUtil;
import com.allen.study.domain.repository.IEmployeeInfoRepo;
import io.swagger.v3.oas.annotations.tags.Tag;
import lombok.AllArgsConstructor;
import lombok.extern.slf4j.Slf4j;
import org.springframework.web.bind.annotation.*;

import java.util.List;

/**
 * 用户信息表测试布隆过滤器接口
 *
 * @author AllenSun
 * @since 2025-02-26 23:58
 */
@RequestMapping(value = "/4.2.0/testbloom")
@RestController
@AllArgsConstructor
@Tag(name = "用户信息表测试布隆过滤器接口", description = "用户信息表测试布隆过滤器接口")
@Slf4j
public class EmployeeInfoTestBloomApi {

    private final BloomFilterUtil bloomFilterService;
    private final IEmployeeInfoRepo employeeInfoRepo;

    /**
     * 批量初始化用户数据
     */
    @PostMapping("/batch_init_emp")
    public ApiResponse<String> batchInitEmps(@RequestBody Iterable<String> ids) {
        // 添加到布隆过滤器
        bloomFilterService.addAll(ids);
        return ApiResponse.ok("批量初始化完成");
    }

    @GetMapping("/batch_init_emp")
    public ApiResponse<String> batchInitEmps() {
        // 添加到布隆过滤器
        List<String> queryAllIdList = employeeInfoRepo.queryAllIdList();
        bloomFilterService.addAll(queryAllIdList);
        long count = bloomFilterService.count();
        return ApiResponse.ok("用户信息批量初始化完成："+count+" 条");
    }
}

【6】测试效果

（1）没初始化布隆过滤器之前，根据id查询，都会返回null，数据不存在
（2）初始化布隆过滤器后，先判断布隆过滤器是否存在id，再判断redis数据是否存在，最后才会判断mysql中数据是否存在

【六】实践总结

【1】合理设置参数​：
预期插入数量：应略大于实际数量
误判率：根据业务需求设置（通常0.01-0.05）
【2】防止缓存穿透​：
查询前先检查布隆过滤器
如果不存在直接返回，避免查询数据库
数据库新增数据时，同步添加到布隆过滤器
【3】​数据预热​：
系统启动时，将已有数据批量添加到布隆过滤器
【4】处理误判​：
布隆过滤器说"可能存在"时，继续后续查询
布隆过滤器说"不存在"时，直接返回
【5】​不支持删除​：
标准布隆过滤器不支持删除操作
需要删除功能时，考虑使用Counting Bloom Filter
【6】内存占用
100万元素，误判率1%：约958,505字节（约0.96MB）
1000万元素，误判率1%：约11,480,817字节（约11.5MB）
【7】性能
添加操作：O(k)，k为哈希函数数量
查询操作：O(k)，常数时间复杂度
【8】误判率
随着元素数量增加，误判率会上升
当实际插入数量超过预期时，误判率会显著增加