作用
检查一个元素是否在一个集合中
优缺点
优点：空间效率和查询时间比一般算法好，时间复杂度低，O(k) k是函数的个数，节省空间
缺点：有一定的错误几率，没有的也可能判定为存在，删除困难，无法获得参数本身
场景
- 解决Redis缓存穿透问题
- 邮件过滤，使用布聋过滤器来做邮件黑名单过滤
- 堆爬虫网址进行过滤
- 解决新闻推荐过的不再推荐，类似刷过的抖音下次刷不到
- 大数据量去重
原理
redis中的布隆过滤器底层由一个大型位数组（二进制数组）+多个无偏hash函数组成
（多个无偏位hash函数就是能把元素的hash值计算的比较均匀的hash函数）
当一个元素进入到布隆过滤器中的时候会使用多个无偏位hash函数分别计算hash，然后通过hash值来取模数组长度，得到数组索引。当查询一个元素是否存在的时候就对这个元素进行hash然后查看对应多个二进制数组地址是否值为1
空间计算
布隆过滤器的三个参数
- 元素的大小n
- 运行的错误率f
- 无偏hash函数的个数k
免费计算布隆过滤器的在线地址（通过元素个数，hash函数，准确率计算出所占用的空间大小） https://krisives.github.io/bloom-calculator/
增加元素流程
1.通过k个无偏hash函数计算得到k个hash值
2.依次取模数组长度，得到数组索引
3.将计算得到的数组索引下表位置数据修改为1
Java集成Redis使用布隆过滤器
- 引入redisson框架
<!--redisson框架引入-->
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson-spring-boot-starter</artifactId>
<version>3.16.0</version>
</dependency>
- 编写代码
package com.zhaoxy.springbootredis;
import org.junit.jupiter.api.Test;
import org.junit.runner.RunWith;
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.data.redis.core.RedisTemplate;
import org.springframework.test.context.junit4.SpringRunner;
@RunWith(SpringRunner.class)
@SpringBootTest(classes = SpringbootRedisApplication.class)
class SpringbootRedisApplicationTests {
/** 预计插入的数量 **/
private static final Integer expectedInsertions = 1000;
/** 误判率 */
private static final Double fpp = 0.01;
@Autowired
private RedisTemplate<String, String> redisTemplate;
@Test
public void testSet() {
redisTemplate.boundValueOps("name").set("zhangsan");
}
@Test
public void testBuloomFilter() {
//redis连接
Config config = new Config();
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
config.useSingleServer().setPassword("123456");
//初始化布聋过滤器
RedissonClient client = Redisson.create(config);
RBloomFilter<Object> bloomFilter = client.getBloomFilter("user");
bloomFilter.tryInit(expectedInsertions,fpp);
//布隆过滤器增加元素
for (Integer i = 0; i < expectedInsertions; i++) {
bloomFilter.add(i);
}
//统计元素
int count = 0;
for (Integer i = expectedInsertions; i < expectedInsertions*2; i++) {
if(bloomFilter.contains(i)){
count++;
}
}
System.out.println("误判次数"+count);
}
}
【程序员都必须会的技术，面试必备【布隆过滤器详解】，Redis缓存穿透解决方案】https://www.bilibili.com/video/BV1zK4y1h7pA?vd_source=40f864ed61303be63434eb6a5f73e297
使用场景
-
用户注册场景
- 用户量过大的情况下，注册的时候需要判断用户名是否重复，初始化的时候将用户名存到布隆过滤器中，注册的时候先到布隆过滤器中查询，如果存在就代表可能存在这个用户名，用户更换名字注册公共后将新的名字注入到布隆过滤器中
- 以上场景存在一个问题，那就是如果用户注销掉了布隆过滤器还是有这个人的名字。可以加一层redis的set类型的注销用户集合，当用户注销的时候加入set，当判断布隆过滤器可能存在用户名后在到redis的set集合中查找一下，如果存在则让他继续注册移除redis中set集合中的用户名。
