初识布隆过滤｜工作场景

作用

检查一个元素是否在一个集合中

优缺点

优点：空间效率和查询时间比一般算法好，时间复杂度低，O(k) k是函数的个数，节省空间

缺点：有一定的错误几率，没有的也可能判定为存在，删除困难，无法获得参数本身

场景

1. 解决Redis缓存穿透问题
2. 邮件过滤，使用布聋过滤器来做邮件黑名单过滤
3. 堆爬虫网址进行过滤
4. 解决新闻推荐过的不再推荐，类似刷过的抖音下次刷不到
5. 大数据量去重

原理

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使用布隆过滤器

1. 引入redisson框架

<!--redisson框架引入-->
<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.16.0</version>
</dependency>

1. 编写代码

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集合中的用户名。