Redisson实现布隆过滤器

旧城等待， 2024-05-02 20:26 40阅读 0赞

### 1、什么是布隆过滤器 ###

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

如果还是不太好理解的话，就可以把布隆过滤器理解为一个set集合，我们可以通过add往里面添加元素，通过contains来判断是否包含某个元素。

### 2、布隆过滤器的原理 ###

*  首先，建立一个二进制向量，并将所有位设置为0。
 *  然后，选定K个散列函数，用于对元素进行K次散列，计算向量的位下标。
 *  添加元素：当添加一个元素到集合中时，通过K个散列函数分别作用于元素，生成K个值作为下标，并将向量的相应位设置为1。
 *  检查元素：如果要检查一个元素是否存在集合中，用同样的散列方法，生成K个下标，并检查向量的相应位是否全部是1。如果全为1，则该元素很可能在集合中；否则（只要有1个或以上的位为0），该元素肯定不在集合中。  
    ![在这里插入图片描述][0e2f0f374bee4359a81b85c36dc36dec.png_pic_center]

### 3、空间计算 ###

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

错误率越低，位数组越长，控件占用较大  
错误率越低，hash函数越多，计算耗时较长  
如下地址是一个免费的在线布隆过滤器在线计算的网址：

https://krisives.github.io/bloom-calculator/

**布隆过滤器的优点：**

*  时间复杂度低，增加和查询元素的时间复杂为O(N)，（N为哈希函数的个数，通常情况比较小）
 *  保密性强，布隆过滤器不存储元素本身
 *  存储空间小，如果允许存在一定的误判，布隆过滤器是非常节省空间的

**布隆过滤器的缺点：**

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

### 4、布隆过滤器的使用场景 ###

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

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

### 5、在Spring Boot中集成Redisson实现布隆过滤器 ###

![在这里插入图片描述][edb9d6d8ef414623ab2f11526f89f779.png_pic_center]

### 6、Redisson实现布隆过滤器 ###

**加入redisson依赖**

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

**application.properties中正常配置redis即可**

**在RedisConfig加入配置类**

@Value("${spring.redis.host}")
        private String host;
    
        @Value("${spring.redis.port}")
        private String port;
    
        @Bean
        public RedissonClient redisson() {
            //创建配置
            Config config = new Config();
            config.useSingleServer().setAddress("redis://" + host + ":" + port);
            //根据config创建出RedissonClient实例
            return Redisson.create(config);
        }

**使用**

@Service
    public class UserService {
        
    	@Autowired
        RedissonClient redissonClient;
    
        private RBloomFilter<Integer> bloomFilter = null;
    
        @Resource
        private UserDao userDao;
    
        @PostConstruct // 项目启动的时候执行该方法，也可以理解为在spring容器初始化的时候执行该方法
        public void init() {
        
            // 启动项目时初始化bloomFilter
            List<User> userList = userDao.queryUserAll();
            //参数：布隆过滤器的名字
            bloomFilter = redissonClient.getBloomFilter("userFilter");
            // 初始化布隆过滤器  预计数据量   误判率
            bloomFilter.tryInit(1000L, 0.01);
            for (User user : userList) {
        
                bloomFilter.add(user.getId());
            }
        }
    
        public User findById(Integer id) {
        
            // bloomFilter中不存在该key,为非法访问
            if (!bloomFilter.contains(id)) {
        
                System.out.println("所要查询的数据既不在缓存中，也不在数据库中，为非法key");
                return null;
            }
            // 不是非法访问，可以访问数据库
            System.out.println("数据库中得到数据*****");
            return userDao.selectById(id);
        }
    
        public Integer addUer(User user) {
        
            userDao.insert(user);
            // 新生成key的加入布隆过滤器，此key从此合法
            bloomFilter.add(user.getId());
            return user.getId();
        }
    }

**UserMapper.xml**

<?xml version="1.0" encoding="UTF-8" ?>
    <!DOCTYPE mapper
            PUBLIC "-//mybatis.org//DTD Mapper 3.0//EN"
            "http://mybatis.org/dtd/mybatis-3-mapper.dtd">
    <mapper namespace="com.webliu.dao.UserDao">
    
        <select id="queryUserAll" resultType="com.webliu.model.User">
            select * from user
        </select>
    
        <select id="selectById" resultType="com.webliu.model.User">
            select * from user where id=#{id}
        </select>
    
        <insert id="insert">
            insert into user (name,age) values(#{name},#{age})
            <selectKey keyProperty="id" resultType="integer" keyColumn="newId" order="AFTER">
                SELECT LAST_INSERT_ID() as newId
            </selectKey>
        </insert>
    </mapper>

[0e2f0f374bee4359a81b85c36dc36dec.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/968626ca42994dfaa32b99e8d332d700.png
[edb9d6d8ef414623ab2f11526f89f779.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/05/02/f8770d2da5cb43d4a1d1b473b33d59d0.png