布隆过滤器实现的两种方法

Dear 丶 2023-02-18 08:11 65阅读 0赞

解决（缓解）大量不存在的缓存请求到数据库，即缓存击穿

由布隆提出的，她本身是一个很长的二进制向量

也就是说布隆过滤器只能判断数据是否一定不存在，而无法判断数据是否一定存在。

*  优点：由于存放的不是完整的数据，所以占用的内存很少，而且新增，查询速度够快；
 *  缺点： 随着数据的增加，误判率随之增加；无法做到删除数据；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

guava实现布过滤器

private static int size = 1000000;//预计要插入多少数据
        private static double fpp = 0.01;//期望的误判率
        private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
        public static void main(String[] args) {
            //插入数据
            for (int i = 0; i < 1000000; i++) {
                bloomFilter.put(i);
            }
            int count = 0;
            for (int i = 1000000; i < 2000000; i++) {
                if (bloomFilter.mightContain(i)) {
                    count++;
                    System.out.println(i + "误判了");
                }
            }
            System.out.println("总共的误判数:" + count);
        }

redisson实现布隆过滤器

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDQ4MzQ5_size_16_color_FFFFFF_t_70][]

假设一个网页黑名单有URL为100亿，每个样本为64B，失误率为0.01%，

经过上述公式计算后，需要布隆过滤器大小为25GB，这远远小于使用哈希表的640GB的空间。

并且由于是通过hash进行查找的，所以基本都可以在O(1)的时间完成！

@PostMapping("/addUser")
        public Integer insert(@RequestBody MUser user) {
            RBloomFilter<String> bloomFilter = redisson.getBloomFilter(Constant.REDISSON_BLOOMFILTER_USER);
            //布隆过滤器计算的正确率为97%，初始化布隆过滤器容量为50000L
            bloomFilter.tryInit(500000L,0.03);
            if (bloomFilter.contains(user.getName())) {
                throw new InvalidArgumentException("用户名:" + user.getName() + "已经存在");
            }
     
            user.setId(null);
            int res = userMapper.insertSelective(user);
            if (res > 0) {
                //加入布隆过滤器
                bloomFilter.add(user.getName());
            }
            return user.getId();
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDQ4MzQ5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616155205778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMyNDQ4MzQ5,size_16,color_FFFFFF,t_70