一文搞懂布隆过滤器(BloomFilter)

简介: 一文搞懂布隆过滤器(BloomFilter)

1 什么是布隆过滤器

  • 布隆过滤器(Bloom Filter)是由布隆(Burton Howard Bloom)在1970年提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成,布隆过滤器本质上由一个长度为m的位向量组成。
  • 基本的布隆过滤器支持两种操作:测试和添加。
  • 用途:布隆过滤器可以用于检索一个元素是否在一个集合中。
  • 它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
    (误识别:元素不存在而说在,不会出现元素在而说不在,即在肯定在,不在可能在)

2 布隆过滤器和HashSet有什么不同

布隆过滤器:

  • 基本思想:通过一个Hash函数将一个元素映射成一个位阵列(Bit Array)中的一个点。这样一来,我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。
  • 优点:占用空间小,效率高。
  • 缺点:存在误差率,不能删除元素。

HashSet:

  • 基本思想:利用Hash函数将元素的HashCode取出,放在一个内部的数组或链表中,增删改查元素时一般都是根据元素的HashCode进行操作。
  • 优点:使用简单,原理简单。
  • 缺点:占用内存大,性能较低。

综上,布隆过滤器主要适用于大量数据的去重,而HashSet等数据结构适合中小量数据的去重和检验。

3 使用布隆过滤器

实现布隆过滤器的方式有很多种,比如:

  • Guava实现
  • Redis实现
  • 自己实现
  • …

这里我们使用Google Guava的内置布隆过滤器做演示:

依赖:

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>23.0</version>
</dependency>

代码:

public class Test {
    /**
     * 过滤器默认容量
     */
    private static final int DEFAULT_SIZE = 1000000;
    /**
     * 自定义误判率,默认0.03,区间(0,1)
     */
    private static final double FPP = 0.02;
    public static void main(String[] args) {
        //初始化一个存储string数据的布隆过滤器,默认误判率是0.03
        BloomFilter<String> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), DEFAULT_SIZE, FPP);
        //用于存放所有实际存在的key,用于是否存在
        Set<String> sets = new HashSet<>(DEFAULT_SIZE);
        //用于存放所有实际存在的key,用于取出
        List<String> lists = new ArrayList<>(DEFAULT_SIZE);
        //插入随机字符串
        for (int i = 0; i < DEFAULT_SIZE; i++) {
            String uuid = UUID.randomUUID().toString();
            //添加数据
            bf.put(uuid);
            sets.add(uuid);
            lists.add(uuid);
        }
        int rightNum = 0;
        int wrongNum = 0;
        for (int i = 0; i < 10000; i++) {
            // 0-10000之间,可以被100整除的数有100个(100的倍数)
            String data = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
            //这里用了might,看上去不是很自信,所以如果布隆过滤器判断存在了,我们还要去sets中实锤
            if (bf.mightContain(data)) {
                if (sets.contains(data)) {
                    rightNum++;
                    continue;
                }
                wrongNum++;
            }
        }
        BigDecimal percent = new BigDecimal(wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
        BigDecimal bingo = new BigDecimal(9900 - wrongNum).divide(new BigDecimal(9900), 2, RoundingMode.HALF_UP);
        System.out.println("在100W个元素中,判断100个实际存在的元素,布隆过滤器认为存在的:" + rightNum);
        System.out.println("在100W个元素中,判断9900个实际不存在的元素,误认为存在的:" + wrongNum + ",命中率:" + bingo + ",误判率:" + percent);
    }
}

运行结果:

原理:

布隆过滤器的核心原理就是利用位数组,将元素利用多次Hash映射成位,当判断是否存在时,将被查找元素按相同操作映射,当一个元素可能有多个位,当每个位都为1时证明该元素存在,反之则不存在。

演示:

# 存储元素:
abc ---> {2,3,4}都为1
def ---> {5,6,7}都为1
# 查找元素:
abc ---> {2,3,4}都为1   1==1&&1==1&&1==1 --->true   存在
aaa ---> {2,3,3}都为1   1==1&&1==1&&0==1 --->false  不存在
# 存在误差:
acf ---> {2,3,6}都为1   1==1&&1==1&&1==1 --->true 存在

4 手写简单的布隆过滤器

public class MyBloomFilter {
    /**
     * 使用加法hash算法,所以定义了一个3个元素的质数数组
     */
    private static final int[] primes = new int[]{2, 3, 5};
    /**
     * 用八个不同的质数,相当于构建8个不同算法
     */
    private Hash[] hashList = new Hash[primes.length];
    /**
     * 创建一个长度为10亿的比特位
     */
    private BitSet bits = new BitSet(1000000000);
    public MyBloomFilter() {
        for (int i = 0; i < primes.length; i++) {
            //使用3个质数,创建3种算法
            hashList[i] = new Hash(primes[i]);
        }
    }
    /**
     * 添加元素
     * @param value
     */
    public void add(String value) {
        for (Hash f : hashList) {
            bits.set(f.hash(value), true);
        }
    }
    /**
     * 判断是否在布隆过滤器中
     * @param value
     * @return
     */
    public boolean contains(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (Hash f : hashList) {
            //查看3个比特位上的值
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }
    /**
     * 加法hash算法
     */
    public static class Hash {
        private int prime;
        public Hash(int prime) {
            this.prime = prime;
        }
        public int hash(String key) {
            int hash, i;
            for (hash = key.length(), i = 0; i < key.length(); i++) {
                hash += key.charAt(i);
            }
            return (hash % prime);
        }
    }
    public static void main(String[] args) {
        MyBloomFilter bloom = new MyBloomFilter();
        System.out.println(bloom.contains("2222"));
        bloom.add("2222");
        //维护1亿个在线用户
        for (int i = 1; i < 100000000; i++) {
            bloom.add(String.valueOf(i));
        }
        long begin = System.currentTimeMillis();
        System.out.println(begin);
        System.out.println(bloom.contains("2222"));
        long end = System.currentTimeMillis();
        System.out.println(end);
        System.out.println("判断2222是否存在使用了:" + (end - begin));
    }
}

运行结果:

参考文章:

https://blog.csdn.net/wuzhiwei549/article/details/106714765

https://www.jasondavies.com/bloomfilter/

https://www.cnblogs.com/liyulong1982/p/6013002.html

https://www.jianshu.com/p/7634eaea3e26

相关文章
|
SQL 前端开发 druid
5-TDengine集成SpringBoot,MyBatis,MyBatisPlus
5-TDengine集成SpringBoot,MyBatis,MyBatisPlus
5913 0
5-TDengine集成SpringBoot,MyBatis,MyBatisPlus
|
关系型数据库 MySQL
【Mysql】服务没有响应控制功能。 请键入 NET HELPMSG 2186 以获得更多的帮助。
解决方法: 1. 下载dll文件 https://www.aliyundrive.com/s/oV6GgghtPkN 2.将文件放置在mysql bin文件夹下 3. 重新启动Mysql,发现启动成功了!🚀
2024 1
|
安全 网络安全 开发工具
git 提示:fatal: Could not read from remote repository.
git 提示:fatal: Could not read from remote repository.
2668 0
git 提示:fatal: Could not read from remote repository.
|
机器人 数据安全/隐私保护
AppFlow:钉钉机器人使用Qwen3自动回复
近期,Qwen3正式发布并开源了8款「混合推理模型」,包括两款MoE模型和六个Dense模型。这些模型已在AppFlow上全面开放调用,支持钉钉、微信等多种渠道使用。本文将详细介绍如何将Qwen3集成到钉钉机器人中,涵盖创建钉钉应用、配置消息卡片、生成连接流以及发布应用版本等步骤,帮助用户快速实现与Qwen3的交互功能。通过简单的配置,您即可在钉钉群聊中与Qwen3进行交流互动。
993 8
AppFlow:钉钉机器人使用Qwen3自动回复
|
安全 搜索推荐 数据挖掘
文件解析的终极工具:Apache Tika
文件解析的终极工具:Apache Tika
3335 0
|
人工智能 安全 Java
深入理解Java浅拷贝与深拷贝
本文深入探讨Java中浅拷贝与深拷贝的概念、实现方式及应用场景。浅拷贝通过`clone()`方法复制对象引用,修改新对象会影响原对象;深拷贝则创建完全独立的新对象,确保数据安全。文章通过代码示例讲解两种拷贝方式的实现,并分析其优缺点。同时,针对List类型提供浅拷贝和深拷贝的具体实现方法,帮助读者更好地理解和应用这两种技术。选择拷贝方式时需权衡对象复杂度、大小及操作安全性等因素。
964 2
Java 线程同步的四种方式,最全详解,建议收藏!
本文详细解析了Java线程同步的四种方式:synchronized关键字、ReentrantLock、原子变量和ThreadLocal,通过实例代码和对比分析,帮助你深入理解线程同步机制。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
Java 线程同步的四种方式,最全详解,建议收藏!
Invalid bound statement (not found)错误【已解决】
Invalid bound statement (not found)错误【已解决】
3931 1
Github进不去的解决方法
Github进不去的解决方法
1166 0