Java 布隆过滤器

迈不过友情╰ 2023-09-24 19:01 74阅读 0赞

你在么？可能在！一定在么？不一定在！一定不在么？一定不在。

你想要100%的准去性，还是99%的准确性附带较高的速度和较小的资源消耗。

任何算法都是时间效益、资源消耗、准确性的平衡（1天的时间 10元的投入 生产10个单位的产品，还是 0.6天的时间 6元的投入 生产9个单位的产品）

## **1.布隆过滤器** ##

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

> 维基百科
> 
> A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not, thus a Bloom filter has a 100% recall rate. In other words, a query returns either “possibly in set” or “definitely not in set”.
> 
> 空间效率高的概率型数据结构，用来检查一个元素是否在一个集合中。对于一个元素检测是否存在的调用，BloomFilter会告诉调用者两个结果之一：可能存在或者一定不存在。

### 1.用途 ###

存值，与set map类似（set map 存储大量数据时浪费空间）。

校验值是否存在（不存在一定不存在，存在可能不一定存在【有一定误差】）。

### 2.原理 ###

#### 2.1存值 ####

k = m/n \* ln2 【m是数组长度，n是插入的元素个数，k是hash函数的个数】

假设想要将“张三”放入数组中，经计算k=3的情况，大体存储如下图。![aa462d0faa6e4bc18d266d56f82d2a24.png][]

#### 2.2校验 ####

1.同样的k值计算，获取hash函数个数，计算落点位置。

2.逐个落点校验，每个落点位置都标记为1则元素可能存在，只要有一个落点标记为0则不存在。

## **2.Guava Bloom Filter** ##

import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;
    import org.junit.Test;
    
    import java.nio.charset.Charset;
    
    public class BloomFilterTest {
    
    
        @Test
        public void test() {
            // 100w bit长度 ,0.01%误判率
            // bf对象则会生成 299534 个long数组,使用13次hash计算.
            BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()), 100 * 10000, 0.0001d);
    
            System.out.println(bloomFilter.mightContain("test1")); // false
            bloomFilter.put("test1");
            System.out.println(bloomFilter.mightContain("test1")); // true
            bloomFilter.put("test12");
    
        }
    
    }

## **3.Redis Redission Bloom Filter** ##

### 1.pom依赖包 ###

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

###    2.yml配置（redis配置） ###

spring:
        redis:
            host: xxxxx
            port: 60002
            password: x
            ssl: false

###  ###

### 3.Java 测试代码 ###

import lombok.extern.slf4j.Slf4j;
    import org.junit.Test;
    import org.junit.runner.RunWith;
    import org.redisson.api.RBloomFilter;
    import org.redisson.api.RedissonClient;
    import org.springframework.boot.test.context.SpringBootTest;
    import org.springframework.test.context.ActiveProfiles;
    import org.springframework.test.context.junit4.SpringRunner;
    
    import javax.annotation.Resource;
    
    @SpringBootTest
    @RunWith(SpringRunner.class)
    @ActiveProfiles("test")
    @Slf4j
    public class RedisBloomFilterTest {
    
        @Resource
        private RedissonClient redissonClient;
    
        @Test
        public void testBloomFilter() {
            // 预期插入数量
            long expectedInsertions = 100L;
            // 错误比率
            double falseProbability = 0.01;
            RBloomFilter<String> bloomFilter = redissonClient.getBloomFilter("blackList");
            bloomFilter.tryInit(expectedInsertions, falseProbability);
            // 布隆过滤器增加元素
            for (long i = 0; i < expectedInsertions; i++) {
                bloomFilter.add("test" + i);
            }
            long elementCount = bloomFilter.count();
            log.info("elementCount = {}.", elementCount);
    
            // 统计误判次数
            int count = 0;
            for (long i = expectedInsertions; i < expectedInsertions * 2; i++) {
                if (bloomFilter.contains("test" + i)) {
                    count++;
                }
            }
            log.info("误判次数 = {}.", count);
            bloomFilter.delete();
        }
    }

[aa462d0faa6e4bc18d266d56f82d2a24.png]: https://img-blog.csdnimg.cn/aa462d0faa6e4bc18d266d56f82d2a24.png