当前位置： 首页 > news >正文

布隆过滤器

news 2025/7/1 16:19:04

一 基本概念

1.1 布隆过滤器是什么

布隆过滤器(Bloom Filter)是由Howard Bloom在1970年提出的二进制向量数据结构，用来高效地检测一个元素是否存在集合中；

布隆过滤器的底层数据结构是一个二进制数组(0或1)，默认值0表示元素不存在，1表示元素存在；

1.2 布隆过滤器的原理

将一个元素插入到布隆过滤器，首先这个元素对m个哈希函数依次进行计算，得到的哈希值再与二进制数组长度进行取模运算，得到的值也即是在数组中对应的索引位置，将对应索引位置的值置为1，表示元素插入到布隆过滤器完成；

查询一个元素在布隆过滤器中是否存在，首先这个元素对m个哈希函数依次进行计算，得到的哈希值再与二进制数组长度进行取模运算，得到的值也即是在数组中对应的索引位置，依次判断对应索引位置的值：

        如果元素对应的索引位置只要有一个值不为1，那就表示这个元素一定不存在过滤器中；

        如果元素对应的索引位置的值都为1，那就表示这个元素可能存在过滤器中，这是因为不同的元素的索引值有可能是一样的，这就导致了误判，布隆过滤器是允许一定程度误判的；

在布隆过滤器中删除一个元素是很难完成的，因为不同的元素可能会有相同的哈希值，这样删除一个元素，即是将这个元素对应数组索引位置的值置为0，那么其他元素也会跟着受影响，也意味着删除，还有布隆过滤器没有更新元素的操作；

1.3 布隆过滤器的优点

布隆过滤器的底层数据结构是二进制数组，占用内存空间小；

布隆过滤器操作的是二进制数组对应的数据，插入元素和查询元素的速度非常快；

布隆过滤器存储的是一组二进制数据，不存储真实数据，安全保密性好；

1.4 布隆过滤器的缺点

布隆过滤器存在误判，可以证明一个元素一定不存在过滤器中，但是不能证明一个元素一定存在过滤器中，需要根据业务场景调整布隆过滤器的误判率，尽量减少误判；

布隆过滤器删除元素和更新元素困难；

1.5 布隆过滤器的使用场景

白名单校验，布隆过滤器可以用在redis和mysql之前当作一个缓冲层，将布隆过滤器理解成一个白名单，判断请求参数是否存在白名单中，然后再决定是否走数据库，减轻数据库的压力；

黑名单校验，识别垃圾邮件、恶意IP地址的访问等，将布隆过滤器理解成一个黑名单，判断请求参数是否在黑名单中，然后再决定是否走后续代码，减轻服务器的压力；

二 基本使用

2.1 Guava实现布隆过滤器

Guava是Google开发的一个Java库，其中包含了布隆过滤器的实现，在Java项目中通过简单的API就可以方便地使用布隆过滤器。

pom文件依赖：

<dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>29.0-jre</version>
</dependency>

功能代码：

public static void main(String[] args) {// 预计插入的元素数量int expectedInsertions = 10000;// 误判率double fpp = 0.01;// 创建布隆过滤器对象, 指定布隆过滤器预计容纳的元素个数, 和误判率BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), expectedInsertions, fpp);// 添加元素到布隆过滤器bloomFilter.put("Java");bloomFilter.put("JavaScript");// 判断元素是否在布隆过滤器中, 方法返回true或falseSystem.out.println("Java result is: " + bloomFilter.mightContain("Java"));System.out.println("java result is: " + bloomFilter.mightContain("java"));System.out.println("mysql result is: " + bloomFilter.mightContain("mysql"));
}

com.google.common.hash.BloomFilter中创建布隆过滤器的源码如下：

        在创建布隆过滤器对象的时候，需要指定预计容纳元素的个数和误判率；

        由预计容纳元素的个数和误判率计算出布隆过滤器需要的二进制数组的大小；

        由预计容纳元素的个数和二进制数组的大小计算出布隆过滤器需要的哈希函数个数；

        误判率越小，所占用的空间就越大，需要的哈希函数也就越多，操作时间也就越长，性能也就越差；

@VisibleForTesting
static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions, double fpp, BloomFilter.Strategy strategy) {Preconditions.checkNotNull(funnel);Preconditions.checkArgument(expectedInsertions >= 0L, "Expected insertions (%s) must be >= 0", expectedInsertions);Preconditions.checkArgument(fpp > 0.0D, "False positive probability (%s) must be > 0.0", fpp);Preconditions.checkArgument(fpp < 1.0D, "False positive probability (%s) must be < 1.0", fpp);Preconditions.checkNotNull(strategy);if (expectedInsertions == 0L) {expectedInsertions = 1L;}// 布隆过滤器底层二进制数组的大小long numBits = optimalNumOfBits(expectedInsertions, fpp);// 布隆过滤器需要的哈希函数个数int numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);try {return new BloomFilter(new BloomFilterStrategies.LockFreeBitArray(numBits), numHashFunctions, funnel, strategy);} catch (IllegalArgumentException var10) {throw new IllegalArgumentException("Could not create BloomFilter of " + numBits + " bits", var10);}
}

2.2 Redisson实现布隆过滤器

pom文件依赖：

<dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.15.0</version>
</dependency>

功能代码：

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;public class GuavaBloomFilter {public static void main(String[] args) {Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");RedissonClient redissonClient = Redisson.create(config);RBloomFilter<Object> bloomFilter = redissonClient.getBloomFilter("mango");// 预计插入的元素数量long expectedInsertions = 10000L;// 误判率double fpp = 0.03;// 初始化布隆过滤器, 指定预计插入的元素数量和误差率if (bloomFilter.tryInit(expectedInsertions, fpp)) {// 添加元素到布隆过滤器bloomFilter.add("Java");bloomFilter.add("PHP");bloomFilter.add("Golang");// 查询元素是否在布隆过滤器System.out.println("Java result is: " + bloomFilter.contains("Java"));System.out.println("java result is: " + bloomFilter.contains("java"));System.out.println("python result is: " + bloomFilter.contains("python"));// Java result is: true// java result is: false// python result is: false}redissonClient.shutdown();}
}

在Springboot使用Redisson实现布隆过滤器

pom文件依赖：

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

配置类：

@Configuration
public class MangoConfig {@Beanpublic RedissonClient redissonClient() {Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");return Redisson.create(config);}}

功能代码：

@SpringBootApplication
public class MangoApplication implements ApplicationRunner {public static void main(String[] args) {SpringApplication.run(MangoApplication.class, args);}@Autowiredprivate RedissonClient redissonClient;@Overridepublic void run(ApplicationArguments args) throws Exception {RBloomFilter<Object> bloomFilterOne = redissonClient.getBloomFilter("mangoOne");RBloomFilter<Object> bloomFilterTwo = redissonClient.getBloomFilter("mangoTwo");bloomFilterOne.tryInit(10000L, 0.03);bloomFilterTwo.tryInit(10000L, 0.03);bloomFilterOne.add("JavaOne");bloomFilterOne.add("PHPOne");bloomFilterOne.add("GolangOne");bloomFilterTwo.add("mathTwo");bloomFilterTwo.add("chineseTwo");bloomFilterTwo.add("englishTwo");System.out.println("bloomFilterOne中JavaOne result is: " + bloomFilterOne.contains("JavaOne"));System.out.println("bloomFilterOne中PHPOne result is: " + bloomFilterOne.contains("PHPOne"));System.out.println("bloomFilterOne中GolangOne result is: " + bloomFilterOne.contains("GolangOne"));System.out.println("bloomFilterOne中mathTwo result is: " + bloomFilterOne.contains("mathTwo"));System.out.println("bloomFilterOne中chineseTwo result is: " + bloomFilterOne.contains("chineseTwo"));System.out.println("bloomFilterOne中englishTwo result is: " + bloomFilterOne.contains("englishTwo"));System.out.println("bloomFilterTwo中mathTwo result is: " + bloomFilterTwo.contains("mathTwo"));System.out.println("bloomFilterTwo中chineseTwo result is: " + bloomFilterTwo.contains("chineseTwo"));System.out.println("bloomFilterTwo中englishTwo result is: " + bloomFilterTwo.contains("englishTwo"));// bloomFilterOne中JavaOne result is: true// bloomFilterOne中PHPOne result is: true// bloomFilterOne中GolangOne result is: true// bloomFilterOne中mathTwo result is: false// bloomFilterOne中chineseTwo result is: false// bloomFilterOne中englishTwo result is: false// bloomFilterTwo中mathTwo result is: true// bloomFilterTwo中chineseTwo result is: true// bloomFilterTwo中englishTwo result is: true}
}

三 业务使用

3.1 解决缓存穿透

pom文件：

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

在代码中模拟数据库功能：

public class DBData {public static Map<String, String> dbMap() {Map<String, String> map = new HashMap<>();map.put("Java", "one");map.put("Golang", "two");return map;}
}

配置类：

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;@Configuration
public class MangoConfig {@Beanpublic RedissonClient redissonClient() {Config config = new Config();config.useSingleServer().setAddress("redis://127.0.0.1:6379");return Redisson.create(config);}@Beanpublic RBloomFilter<String> mangoBloomFilter(RedissonClient redissonClient) {RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("mango");bloomFilter.tryInit(10000L, 0.03);return bloomFilter;}@Beanpublic RBloomFilter<String> zeroBloomFilter(RedissonClient redissonClient) {RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("zero");bloomFilter.tryInit(10000L, 0.03);return bloomFilter;}
}

启动类：

import org.redisson.api.RBloomFilter;
import org.redisson.api.RBucket;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.ApplicationArguments;
import org.springframework.boot.ApplicationRunner;
import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import java.util.Map;
import java.util.concurrent.TimeUnit;@SpringBootApplication
public class MangoApplication implements ApplicationRunner {public static void main(String[] args) {SpringApplication.run(MangoApplication.class, args);}@Autowiredprivate RedissonClient redissonClient;@Autowiredprivate RBloomFilter mangoBloomFilter;@Overridepublic void run(ApplicationArguments args) throws Exception {// 项目启动后将值刷到redis缓存, 和填充布隆过滤器白名单, 模拟从数据库中获取数据Map<String, String> dbMap = DBData.dbMap();dbMap.entrySet().forEach(s -> {RBucket<Object> bucket = redissonClient.getBucket(s.getKey());bucket.expire(1000, TimeUnit.SECONDS);bucket.set(s.getValue());mangoBloomFilter.add(s.getKey());});}
}

业务类：

import org.redisson.api.RBloomFilter;
import org.redisson.api.RBucket;
import org.redisson.api.RedissonClient;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RestController;
import java.util.concurrent.TimeUnit;@RestController
public class MangoController {@Autowiredprivate RedissonClient redissonClient;@Autowiredprivate RBloomFilter<String> mangoBloomFilter;@GetMapping("/bloom/filter")public String bloomFilter(String key) {if (!mangoBloomFilter.contains(key)) {return "布隆过滤器中不存在: " + key;}if (redissonClient.getBucket(key).isExists()) {return "Redis返回的值: " + redissonClient.getBucket(key).get();} else {RBucket<Object> bucket = redissonClient.getBucket(key);bucket.expire(1000, TimeUnit.SECONDS);bucket.set(DBData.dbMap().get(key));return "从数据库中返回的值: " + DBData.dbMap().get(key);}}}

解决缓存穿透问题就是把布隆过滤器当作白名单来处理数据； 

3.2 黑名单案例

有些业务需求是已经处理过的数据就不想再处理，这时候可以使用布隆过滤器当作黑名单处理业务，像记录一些骚扰电话，屏蔽一些垃圾邮件，还有保证添加业务表唯一字段的特性，还有已经推荐过的新闻不再推荐等等，都可以使用这个案例，以拉黑骚扰电话为例：

public class DBData {public static List<String> phoneList() {List<String> list = new ArrayList<>();// 模拟以下九个电话号码是骚扰电话list.add("10000000001");list.add("10000000002");list.add("10000000003");list.add("10000000004");list.add("10000000005");list.add("10000000006");list.add("10000000007");list.add("10000000008");list.add("10000000009");return list;}
}

业务代码：

@RestController
public class MangoController {@Autowiredprivate RBloomFilter<String> zeroBloomFilter;@GetMapping("/phone/filter")public String phoneFilter(String phone) {if (zeroBloomFilter.contains(phone)) {return "黑名单记录收到的骚扰电话: " + phone;}if (DBData.phoneList().contains(phone)) {System.out.println("前端传来的是骚扰电话: " + phone);// 将骚扰电话加入黑名单zeroBloomFilter.add(phone);return "处理前端传来的骚扰电话: " + phone + ", 并加入黑名单";}return "处理前端传来的正常电话: " + phone;}
}


http://www.mrgr.cn/news/53466.html

相关文章：

  • [MySQL课后作业]人事管理系统的SQL实践
  • 【C++】哈希的应用——位图
  • 三菱PLC如何实现数据排序的分析？
  • stm32通过串口读取JY61 JY62数据（HAL库）
  • 代码随想录算法训练营第二天（补） | 滑动窗口、模拟、前缀和
  • QExcel 保存数据 (QtXlsxWriter库)
  • Redis2
  • Scala的sortedWith
  • Java集合常见知识总结（中）
  • 从开发板传送文件回本地
  • 【在Linux世界中追寻伟大的One Piece】应用层自定义协议|序列化
  • 19.面试算法-树的深度优先遍(一)
  • 008、相交链表
  • (01)fastapi的基础学习——开启学习之路
  • JavaScript (基础)
  • 【力扣打卡系列】滑动窗口与双指针(两数之和)
  • 优化漏洞扫描流程以保障企业数字化业务安全
  • 【AI学习】Mamba学习（八）：HiPPO通用框架定义和方法
  • 小白学电路之电流镜仿真
  • OpenLayers：用于在 web 应用程序中创建互动地图