`
erichi101
  • 浏览: 11214 次
文章分类
社区版块
存档分类
最新评论

布隆过滤器

阅读更多

 

 

本文是站在小白的角度去讨论布隆过滤器,如果你是科班出身,或者比较聪明,又或者真正想完全搞懂布隆过滤器的可以移步。

不知道从什么时候开始,本来默默无闻的布隆过滤器一下子名声大燥,仿佛身在互联网,做着开发的,无人不知,无人不晓,哪怕对技术不是很关心的小伙伴也听过它的名号。我也花了不少时间去研究布隆过滤器,看了不少博客,无奈不是科班出身,又没有那么聪明的头脑,又比较懒...经过“放弃,拿起,放弃,拿起”的无限轮回,应该算是了解了布隆过滤器的核心思想,所以想给大家分享下。

布隆过滤器的应用

我们先来看下布隆过滤器的应用场景,让大家知道神奇的布隆过滤器到底能做什么。

缓存穿透

我们经常会把一部分数据放在Redis等缓存,比如产品详情。这样有查询请求进来,我们可以根据产品Id直接去缓存中取数据,而不用读取数据库,这是提升性能最简单,最普遍,也是最有效的做法。一般的查询请求流程是这样的:先查缓存,有缓存的话直接返回,如果缓存中没有,再去数据库查询,然后再把数据库取出来的数据放入缓存,一切看起来很美好。但是如果现在有大量请求进来,而且都在请求一个不存在的产品Id,会发生什么?既然产品Id都不存在,那么肯定没有缓存,没有缓存,那么大量的请求都怼到数据库,数据库的压力一下子就上来了,还有可能把数据库打死。
虽然有很多办法都可以解决这问题,但是我们的主角是“布隆过滤器”,没错,“布隆过滤器”就可以解决(缓解)缓存穿透问题。至于为什么说是“缓解”,看下去你就明白了。

大量数据,判断给定的是否在其中

现在有大量的数据,而这些数据的大小已经远远超出了服务器的内存,现在再给你一个数据,如何判断给你的数据在不在其中。如果服务器的内存足够大,那么用HashMap是一个不错的解决方案,理论上的时间复杂度可以达到O(1),但是现在数据的大小已经远远超出了服务器的内存,所以无法使用HashMap,这个时候就可以使用“布隆过滤器”来解决这个问题。但是还是同样的,会有一定的“误判率”。

什么是布隆过滤器

布隆过滤器是一个叫“布隆”的人提出的,它本身是一个很长的二进制向量,既然是二进制的向量,那么显而易见的,存放的不是0,就是1。

现在我们新建一个长度为16的布隆过滤器,默认值都是0,就像下面这样:
image.png

现在需要添加一个数据:

我们通过某种计算方式,比如Hash1,计算出了Hash1(数据)=5,我们就把下标为5的格子改成1,就像下面这样:

image.png

我们又通过某种计算方式,比如Hash2,计算出了Hash2(数据)=9,我们就把下标为9的格子改成1,就像下面这样:
image.png

还是通过某种计算方式,比如Hash3,计算出了Hash3(数据)=2,我们就把下标为2的格子改成1,就像下面这样:
image.png

这样,刚才添加的数据就占据了布隆过滤器“5”,“9”,“2”三个格子。

可以看出,仅仅从布隆过滤器本身而言,根本没有存放完整的数据,只是运用一系列随机映射函数计算出位置,然后填充二进制向量。

这有什么用呢?比如现在再给你一个数据,你要判断这个数据是否重复,你怎么做?

你只需利用上面的三种固定的计算方式,计算出这个数据占据哪些格子,然后看看这些格子里面放置的是否都是1,如果有一个格子不为1,那么就代表这个数字不在其中。这很好理解吧,比如现在又给你了刚才你添加进去的数据,你通过三种固定的计算方式,算出的结果肯定和上面的是一模一样的,也是占据了布隆过滤器“5”,“9”,“2”三个格子。

但是有一个问题需要注意,如果这些格子里面放置的都是1,不一定代表给定的数据一定重复,也许其他数据经过三种固定的计算方式算出来的结果也是相同的。这也很好理解吧,比如我们需要判断对象是否相等,是不可以仅仅判断他们的哈希值是否相等的。

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

按理来说,介绍完了新增、查询的流程,就要介绍删除的流程了,但是很遗憾的是布隆过滤器是很难做到删除数据的,为什么?你想想,比如你要删除刚才给你的数据,你把“5”,“9”,“2”三个格子都改成了0,但是可能其他的数据也映射到了“5”,“9”,“2”三个格子啊,这不就乱套了吗?

相信经过我这么一介绍,大家对布隆过滤器应该有一个浅显的认识了,至少你应该清楚布隆过滤器的优缺点了:

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

可以看到,布隆过滤器的优点和缺点一样明显。

在上文中,我举的例子二进制向量长度为16,由三个随机映射函数计算位置,在实际开发中,如果你要添加大量的数据,仅仅16位是远远不够的,为了让误判率降低,我们还可以用更多的随机映射函数、更长的二进制向量去计算位置。

guava实现布隆过滤器

现在相信你对布隆过滤器应该有一个比较感性的认识了,布隆过滤器核心思想其实并不难,难的在于如何设计随机映射函数,到底映射几次,二进制向量的长度设置为多少比较好,这可能就不是一般的开发可以驾驭的了,好在Google大佬给我们提供了开箱即用的组件,来帮助我们实现布隆过滤器,现在就让我们看看怎么Google大佬送给我们的“礼物”吧。

首先在pom引入“礼物”:

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

然后就可以测试啦:

    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);
    }

代码简单分析:
我们定义了一个布隆过滤器,有两个重要的参数,分别是 我们预计要插入多少数据,我们所期望的误判率,误判率不能为0。
我向布隆过滤器插入了0-1000000,然后用1000000-2000000来测试误判率。

运行结果:

1999501误判了
1999567误判了
1999640误判了
1999697误判了
1999827误判了
1999942误判了
总共的误判数:10314

现在总共有100万数据是不存在的,误判了10314次,我们计算下误判率
image.png
和我们定义的期望误判率0.01相差无几。

redis实现布隆过滤器

上面使用guava实现布隆过滤器是把数据放在本地内存中,无法实现布隆过滤器的共享,我们还可以把数据放在redis中,用 redis来实现布隆过滤器,我们要使用的数据结构是bitmap,你可能会有疑问,redis支持五种数据结构:String,List,Hash,Set,ZSet,没有bitmap呀。没错,实际上bitmap的本质还是String。

可能有小伙伴会说,纳尼,布隆过滤器还没介绍完,怎么又出来一个bitmap,没事,你可以把bitmap就理解为一个二进制向量。

要用redis来实现布隆过滤器,我们需要自己设计映射函数,自己度量二进制向量的长度,这对我来说,无疑是一个不可能完成的任务,只能借助搜索引擎,下面直接放出代码把。

public class RedisMain {
    static final int expectedInsertions = 100;//要插入多少数据
    static final double fpp = 0.01;//期望的误判率

    //bit数组长度
    private static long numBits;

    //hash函数数量
    private static int numHashFunctions;

    static {
        numBits = optimalNumOfBits(expectedInsertions, fpp);
        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);
    }

    public static void main(String[] args) {
        Jedis jedis = new Jedis("192.168.0.109", 6379);
        for (int i = 0; i < 100; i++) {
            long[] indexs = getIndexs(String.valueOf(i));
            for (long index : indexs) {
                jedis.setbit("codebear:bloom", index, true);
            }
        }
        for (int i = 0; i < 100; i++) {
            long[] indexs = getIndexs(String.valueOf(i));
            for (long index : indexs) {
                Boolean isContain = jedis.getbit("codebear:bloom", index);
                if (!isContain) {
                    System.out.println(i + "肯定没有重复");
                }
            }
            System.out.println(i + "可能重复");
        }
    }

    /**
     * 根据key获取bitmap下标
     */
    private static long[] getIndexs(String key) {
        long hash1 = hash(key);
        long hash2 = hash1 >>> 16;
        long[] result = new long[numHashFunctions];
        for (int i = 0; i < numHashFunctions; i++) {
            long combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) {
                combinedHash = ~combinedHash;
            }
            result[i] = combinedHash % numBits;
        }
        return result;
    }

    private static long hash(String key) {
        Charset charset = Charset.forName("UTF-8");
        return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();
    }

    //计算hash函数个数
    private static int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }

    //计算bit数组长度
    private static long optimalNumOfBits(long n, double p) {
        if (p == 0) {
            p = Double.MIN_VALUE;
        }
        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }
}

运行结果:

88可能重复
89可能重复
90可能重复
91可能重复
92可能重复
93可能重复
94可能重复
95可能重复
96可能重复
97可能重复
98可能重复
99可能重复

本篇博客到这里就结束了,谢谢大家。

 

https://www.cnblogs.com/CodeBear/p/10911177.html

 

分享到:
评论

相关推荐

    Go-一个简单的golang布隆过滤器

    布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Go语言中实现一个简单的布隆过滤器可以帮助我们高效地处理大数据集,尤其是在内存有限的情况下。以下是对这个主题的详细...

    java实现的布隆过滤器算法

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它可能会误判,但不会漏判,即如果它说一个元素在集合中,那可能是错误的,但如果它说一个元素不在集合中,那么...

    bloom filter(C#版自制布隆过滤器)

    布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的,主要应用于大数据存储和检索,尤其在数据库、缓存系统和网络搜索等领域有广泛...

    转载:布隆过滤器算法

    根据给定的信息,本文将详细解释布隆过滤器的基本概念、工作原理以及通过提供的C/C++实现代码来深入了解其实际应用。 ### 布隆过滤器简介 布隆过滤器是一种空间效率极高的概率型数据结构,用于测试一个元素是否在...

    布隆过滤器(利用布隆过滤器实现文字的嵌入和查找功能)

    布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash&gt; bf五个参数你要查找的元素个数,查找元素类型,三个...

    布隆过滤器之C++实现

    C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...

    布隆过滤器C源码-bloomfilter.rar

    布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的,主要应用于大数据和分布式系统中,以减少内存消耗并提高查询效率。在C语言实现...

    【技术分享】Bloomfilter布隆过滤器.pptx

    布隆过滤器是一种高效的空间节省的数据结构,用于判断一个元素是否可能在一个集合中,但可能会产生一定的误判率。它由一个很长的二进制向量和多个独立的哈希函数组成。布隆过滤器的基本原理是,当一个元素被添加到...

    布隆过滤器python库

    布隆过滤器是一种概率数据结构,用于判断一个元素是否可能在一个集合中存在。它通过使用位数组和几个独立的哈希函数来实现,具有高效、节省空间的特点,但可能会产生假阳性错误,即误判一个不在集合中的元素为在集合...

    布隆过滤器的实现,以及测试用例,简单易懂并做了一些注释

    布隆过滤器是一种概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由Burton Howard Bloom在1970年提出的,主要用于解决大数据集的存储和查询问题,尤其在空间效率上有着显著优势。在数据库、搜索引擎、...

    布隆过滤器BloomFilters的一个简单Java库

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...

    9 Redis布隆过滤器插件安装.zip

    Redis布隆过滤器插件是Redis数据库中一个非常实用的扩展功能,主要用于高效地判断一个元素是否可能存在于集合中。由于其独特的数据结构和算法,它在存储空间和查询效率之间取得了良好的平衡,尤其适用于大数据场景下...

    php + redis布隆过滤器.zip

    布隆过滤器是一种概率型数据结构,用于判断一个元素是否可能在一个集合中存在。它在处理大量数据时,能够高效地进行存在性查询,而牺牲一定的误判率。在PHP和Redis结合应用中,布隆过滤器常被用来解决缓存穿透问题,...

    基于布隆过滤器的字符串模糊匹配算法的FPGA实现.pdf

    布隆过滤器是一种高效的概率型数据结构,它用于判断一个元素是否在一个集合中,具有空间效率和时间效率高的优点。在字符串模糊匹配算法中,布隆过滤器能够用来快速排除那些肯定不匹配的字符串,从而减少不必要的精确...

    Go-布隆过滤器的一个Go实现参考bloomfilter.js

    布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会产生误报(false positive),但绝不会产生漏报(false negative)。这种特性使得它在大数据处理、缓存、数据库等...

    布隆过滤器-BloomFilter

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。由布隆在1970年提出,它不像传统的数据结构如哈希表那样保证不误判,而是允许有一定的错误率。这种特性使得...

    布隆过滤器-详说布隆过滤器.pdf

    布隆过滤器详解 布隆过滤器是一种空间效率高、查询效率高的数据结构,用于判断某个元素是否存在于一个大型集合中。它由一个二进制向量(位数组)和一系列随机映射函数(哈希函数)组成。布隆过滤器的原理是将元素...

    布隆过滤器 java实现代码

    布隆过滤器 源码 java版 /** * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as published by * the Free Software ...

    布隆过滤器在网页去重中的应用

    布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用

Global site tag (gtag.js) - Google Analytics