精华内容
下载资源
问答
  • 大话布隆过滤器及其应用场景

    千次阅读 2020-03-31 21:50:25
    今天看博客,有这么一篇文章,他以一道面试题引出了布隆过滤器的概念。这道题大致意思是这样的:假设现在有1000瓶水,其中有一瓶有毒,只要喝一滴,过30天就会毒发身亡。问最少需要多少只小白鼠可以找到有毒的那瓶水...

    1.前言

    今天看博客,有这么一篇文章,他以一道面试题引出了布隆过滤器的概念。这道题大致意思是这样的:假设现在有1000瓶水,其中有一瓶有毒,只要喝一滴,过30天就会毒发身亡。问最少需要多少只小白鼠可以找到有毒的那瓶水,当然是要求30天找到。不然我可以用一只小白鼠实验30*1000=30000天(大约82年)[想想好多人连30000天都活不了,不谈这个伤心的话题了]。那么这个问题怎么解决呢?这里就用到了布隆过滤器。为了便于说明问题,我们假定有10瓶水。我们大致说一下解决思路:

    1.先对10瓶水进行编号,并且转换为2进制。所以就有了10串二进制的数。

    2.让一号小白鼠和最右边一列为1的水,分别为1、3、5、7、9(只要一滴,撑不死的)

    3.让二号、三号、四号小白鼠分别喝相对应列中为1的水。

    4.30天后统计被毒死的小白鼠。可以算出那一瓶有毒。(如下图)

    分析:

    假如我们发现第一只小白鼠和第三只小白鼠被毒死了。二号和四号无恙。我们首先找B列和D列为1的,A列和C列为0的。所以我们找到为0101,即5号瓶子有毒。

    那么我们回到上诉问题,如果有1000瓶水呢?我们可以将1000转换为2进制,应该是10位。所以需要10只小白鼠。

    11 1110 1000

    2.概述

    通过上面的实例相信大家对布隆过滤器有了初步的了解。那么什么是布隆过滤器呢?布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。布隆其实有布尔的谐音,也不知道是不是巧合。我们不去关注这个问题。

    如果想要判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表(又叫哈希表,Hash table)的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点。这样一来,我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
    Hash面临的问题就是冲突。假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们在说谎,不过直觉上判断这种事情的概率是比较低的。

    但是布隆过滤器也有缺点。误算率是其中之一。随着存入的元素数量增加,误算率随之增加。常见的补救办法是建立一个小的白名单,存储那些可能被误判的元素。但是如果元素数量太少,则使用散列表足矣。

    3.应用案例

    其实在读了那篇文章好,我突然想起之前写的一段自我感觉很牛的代码是不是可以通过布隆过滤器优化一下呢?这个业务逻辑是这样的,假设现在有10个按钮,分别为btn1、btn2、btn3...btn10。我们怎么快速判断那一个按钮可以点击,哪一个不可以点击。如果按照正常情况我们会分成2的10次方进行分别讨论,那代码量可想而知。那么我们现在有没有一个通用的方法通过给定一个模数,然后返回需要打开可编辑的按钮呢?

    3.1我最原始的代码

    @Test
    public void test1() {
    	//构造符合要求的按钮集合
        List < FunBtn > btns = new ArrayList < > ();
        for (int i = 9; i >= 0; i--) {
        	//这里用到左移,也就是2的N次方
            btns.add(new FunBtn("btn" + i, 1 << i));
        }
    
        changeEnableFun1(btns, 50);
    
    }
    public void changeEnableFun1(List < FunBtn > funBtns, int funMode) {
        for (FunBtn funBtn: funBtns) {
            funMode = checkFun(funMode, funBtn);
        }
    }
    
    private int checkFun(int funMode, FunBtn funBtn) {
    	//从后往前查找,如果模数大于最大按钮的权重,说明此按钮包含在模数中,最终减去此按钮的权重
    	//否则不包含
    	//
        int weigth = funBtn.getWeight();
        if (funMode >= weigth) {
            System.out.println(funBtn.name);
            funMode -= weigth;
        }
        return funMode;
    }
    
    /**
     * 按钮对象
     * name:假定按钮对象
     * weight:权重,这里的权重按照2的n次方
     */
    public static class FunBtn {
        private String name;
        private Integer weight;
    
        public FunBtn(String name, Integer weight) {
            this.name = name;
            this.weight = weight;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public Integer getWeight() {
            return weight;
        }
    
        public void setWeight(Integer weight) {
            this.weight = weight;
        }
    }

    我们可以事先算好一种业务模式。比如业务场景一,我们需要将按钮btn0、btn1、btn3可编辑,那么我们可以传入的数为2^0+2^1+2^3 = 11。所以,我们将funModel传入11的时候,按钮btn0、btn1、btn3可编辑。大家可以尝试一下。

    3.2 通过布隆过滤器改造的代码

    @Test
    public void test2() {
        List < String > btns = new ArrayList < > ();
        for (int i = 0; i < 10; i++) {
            btns.add("btn" + i);
        }
    
        changeEanbleFun2(btns, 50);
    }
    public void changeEanbleFun2(List < String > btns, int funMode) {
        Integer result = Integer.valueOf(Integer.toBinaryString(funMode));
        String s = String.format("%010d", result);
        for (int i = 0; i < 10; i++) {
            if (s.charAt(i) == 49) {
                System.out.println(btns.get(9 - i));
            }
        }
    }

    首先我们不需要定义那个FunBtn对象了,changeEanbleFun2在处理逻辑上也精简了不少。处理逻辑如下:

    1.首先先将funMode转换为2进制数。如果不够10位的左侧补0.

    2.接着我们对这个二进制的字符串逐个检查,如果等于1,即符合条件的输出结果,否则不变。此时需要注意的是我们通过按钮集合btns的索引位置确定按钮的权重。

    我们可以和上面小白鼠对照一下。10个按钮->10只小白鼠,funMode->有毒的水瓶编号,可编辑的按钮->被毒死的小白鼠。好像这里求的过程和上面的不一样。上面例题中是通过毒死的小白鼠求有毒的水瓶编号,而这里编程通过有毒水瓶的编号求被毒死的小白鼠。不管怎么样,最终还是可以求出结果的。

    3.3 两种思路的耗时比较

    private static final Integer LOOP = 100000;
    
    @Test
    public void test1() {
        List < FunBtn > btns = new ArrayList < > ();
        for (int i = 9; i >= 0; i--) {
            btns.add(new FunBtn("btn" + i, 1 << i));
        }
        for (int i = 0; i < LOOP; i++) {
            changeEnableFun1(btns, 50);
        }
    }
    
    @Test
    public void test2() {
        List < String > btns = new ArrayList < > ();
        for (int i = 0; i < 10; i++) {
            btns.add("btn" + i);
        }
        for (int i = 0; i < LOOP; i++) {
            changeEanbleFun2(btns, 50);
        }
    }

    为了区别明显,我们让其循环10000次,test1是我最开始写的代码,test2是通过布隆过滤器调用的方法。

    是不是有点惊讶,我们费了半天写的代码竟然没有之前执行的效率高。打击可不是一般的小啊。不过我们还是要分析一下原因。讲过对比,其实问题还是出现在Integer result = Integer.valueOf(Integer.toBinaryString(funMode));。在Integer.toBinaryString(funMode)中,JDK对于数字转换也是通过遍历的方式。

    static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
        int charPos = len;
        int radix = 1 << shift;
        int mask = radix - 1;
        do {
            buf[offset + --charPos] = Integer.digits[val & mask];
            val >>>= shift;
        } while (val != 0 && charPos > 0);
    
        return charPos;
    }

    其实核心代码还是代码6、7行。这个在下面会有分析。说白了,我们在test2中,其实是执行了两次循环。这样一来,时间就有差距了。

    既然test2进行了两次循环,我们能不能在一次循环中解决问题,换句话说在生成二进制的期间就把问题解决了?顺着这个思路,我们有了以下的改进。

    3.4 代码改进

    3.4.1 思路

    学过计算机的都应该了解一个十进制转换二进制的方法。我们在这里使用其中一种思路:

    1)对十进制与2取模,写到第一位;

    2)对十进制的数除以2,得到新的数,然后在对2取模。

    3)依次类推。。。

    3.4.2 代码样例

    private void changeEanbleFun3(List < String > btns, int funMode) {
        int position = 0;
        while (funMode != 0) {
            if (funMode % 2 == 1) {
                System.out.println(btns.get(position));
            }
            funMode = funMode / 2;
            position++;
        }
    }

    看起来代码更简洁了。那么我们看一下执行效率。

    这次终于有些成就感了。不知道你们是否还记得上面提到JDK实现十进制转换二进制的方式?他主要是通过位运算实现的。那么我们是否可以借鉴一下想法。

    3.5 终极解决

    3.5.1 JDK转换二进制源码分析

    static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
        int charPos = len;
        int radix = 1 << shift;
        int mask = radix - 1;
        do {
            buf[offset + --charPos] = Integer.digits[val & mask];
            val >>>= shift;
        } while (val != 0 && charPos > 0);
    
        return charPos;
    }

    我们主要分析一下代码6行和代码7行。

    1)代码6行中主要实现为val & mask。这里再次用到了掩码的思想。mask的英文就是掩码的意思,掩码一般和&一起使用。这里mask为1,通过运算,也就是对val对2取模。

    2)代码7行中val >>>= shift;中,是无符号右移1位,说白了就是执行了val/2的运算。其实思路和上面一样,先取模,在除以2,只不过这里使用位运算。感觉效率会比四则运算高。

    3.5.2 代码展示

    private void changeEanbleFun4(List < String > btns, int funMode) {
        int position = 0;
        do {
            if ((funMode & 1) == 1) {
                System.out.println(btns.get(position));
            }
            funMode >>>= 1;
            position++;
    
        } while (funMode != 0);
    }

    这里就不做解释了,相信大家能看懂。我们看一下耗时吧。

    test3和test4基本差不多。不过实现起来还是显得高大上了写。

    4.总结

    在实际工作中,我们对于同一个问题往往有多种不同的解决思路。只要我们肯去思考,就一定能找出一条最优的方案。

    展开全文
  • 理解布隆过滤器使用场景

    千次阅读 2020-03-15 09:53:59
    简单来说,可以把布隆过滤器看作一个【位数组】,这个数组里面存入的都是0或者1。 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200315095034920.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5...

    1.布隆过滤器基础

    简单来说,布隆过滤器可以看作是一个【位数组】。存的都是0或者1。
    位数组中每个元素都只占用1bit;
    它是一种概率性数据结构,可以实现高效插入和查询。
    通常都是用来检索某个元素是否在给定的大集合中***
    能告诉你:XXX一定不存在或者可能存在,给你的结果不是确切的,更加的
    高效、占用空间小
    *。
    在这里插入图片描述

    2.布隆过滤器原理?(如何使用它去判断元素是否存在)

    思考:通常情况下,我们判断某个元素是否存在,会使用HashMap,因为Key是唯一的,我们就可以去查询一个元素的Key,而去找到这个元素。时间复杂度是O(1),效率很高。但是当存储的数据量很大时,也会占用很大内存。
    布隆过滤器可以实现更加快速的查询。
    如图所示,当字符串存储要加入到布隆过滤器中时,该字符串首先由多个哈希函数生成不同的哈希值,然后在对应的位数组的下表的元素设置为 1(当位数组初始化时 ,所有位置均为0)。
    在这里插入图片描述
    加入元素
    如,往布隆过滤器中加入“hello”字符串时,会先使用布隆过滤器中的n个哈希函数对 字符串进行计算,得到n个不同的哈希值,然后将对应的位数组置1。假设得到三个不同的哈希值 1,3,5.
    在这里插入图片描述
    此时,再加入“world”字符串,假设得到 2,3,4
    由于3位置本身就是1,此时又得到了3,就覆盖,完了还是1.
    在这里插入图片描述
    查找元素
    当查找元素“HI”时,计算得到的哈希值为0,3,5
    此时发现0位置的值是0,说明"HI"一定不存在!

    当查找元素“GOOD”是,计算得到的哈希值为1,2,5
    所在位置都是1,但是它实际上并不存在!只能说明“GOOD”可能存在
    同理,就是查找的是前面存过的”hello“,哈希值是1,3,5 也只能告知”hello“可能存在,而不是一定存在。

    总结

    布隆过滤器说某个元素存在,小概率会误判。布隆过滤器说某个元素不在,那么这个元素一定不在。

    3.布隆过滤器使用场景

    3.1 学习Redis时,在某种情况下,可能会出现缓存雪崩和缓存穿透
    缓存穿透:大量请求访问时,Redis没有命中数据,导致请求绕过了Redis缓存,直接去访问数据库了。数据库难以承受大量的请求。
    此时便可以使用布隆过滤器来解决。
    请求到来时,先用布隆过滤器判断数据是否有效,布隆过滤器可以判断元素一定不存在和可能存在,对于一定不存在的数据,则可以直接丢弃请求。对可能存在的请求,再去访问Redis获取数据,Redis没有时,再去访问数据库。
    3.2 邮箱的垃圾邮件过滤、黑名单等。
    3.3 去重,:比如爬给定网址的时候对已经爬取过的 URL 去重。

    展开全文
  • 布隆过滤器使用场景

    2019-12-04 08:20:15
    判断给定数据是否存在:比如判断一个数字是否在包含大量数字的数字集中、 防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)等等、邮箱的垃圾邮件过滤、黑名单...添加元素到位数组(布隆过滤器)的...
    1. 判断给定数据是否存在:比如判断一个数字是否在包含大量数字的数字集中、 防止缓存穿透(判断请求的数据是否有效避免直接绕过缓存请求数据库)等等、邮箱的垃圾邮件过滤、黑名单功能等等;

    2. 去重:比如爬给定网址的时候对已经爬取过的 URL 去重。

    下面,我们再来看看如果想要手动实现一个的话,那么需要以下几步:

    1. 合适大小的位数组保存数据
    2. 几个不同的哈希函数
    3. 添加元素到位数组(布隆过滤器)的方法实现
    4. 判断给定元素是否存在于位数组(布隆过滤器)的方法实现。
    展开全文
  • 十一:redis之布隆过滤器使用应用场景 什么是布隆过滤器 我们会遇到一些场景,判断元素是否在集合中。 我们可以采用的方案有set。我们来看这两个方案的优缺点 如果我们使用set来进行判断元素是否在集合中,那么...

    十一:redis之布隆过滤器的使用与应用场景

    什么是布隆过滤器

    我们会遇到一些场景,判断元素是否在集合中。

    我们可以采用的方案有set。我们来看这两个方案的优缺点

    如果我们使用set来进行判断元素是否在集合中,那么假设每一个元素的32Bit(2^24 ≈ 1600万; 2^32 ≈ 42亿),
    假设我们存储1亿个不重复的元素那么我们需要 100 000 000 * 32 /8/1024/1024 ≈ 381MB;

    布隆过滤器的空间占有有一个简单的计算公式,但是推到比较繁琐。布隆过滤器有两个参数,预计元素数量N,错误率f,公式得到两个输出。为位数组长度L(即布隆过滤器占用的空间Bit长度),这里k表示hash函数的最佳数量。

    k = 0.7*(L/n)
    f = 0.6185^(L/n)

    这里我们假设错误率为1%,那么我们在1亿个不重复元素中判断元素是否存在,需要的空间

    f = 0.01 = 0.6185 ^(L/100 000 000)
    L = 9.585 * 100 000 000 = 9585 000 000 bit = 958 500 000/8/1024/1024 ≈ 114MB

    并且set需要的内存是线性增长的如果单个元素的字节很多那么需要使用的内存是爆炸行的增长,
    而单个元素的字节数并不会影响布隆过滤器(对元素进行hash)。所以在大量数据允许有误差的情况下,布隆过滤器
    是首选,如果不允许有错误率并且数据量小,那么采用集合set也是一种很好的方案。

    命令

    bf.add

    • 解释
      添加元素到指定键键的布隆过滤器。
      如果键不存在先创建键。
      返回1表示元素添加成功
      0表示元素已经存在本次不添加

    • 用法 bf.add key element

    • 示例

    127.0.0.1:6379> bf.add key1 123
    (integer) 1
    127.0.0.1:6379> bf.add key1 123
    (integer) 0
    
    

    bf.exists

    • 解释
      判断元素是否存在于键的类型为布隆过滤器中
      1: 存在
      0: 不存在

    • 用法 bf.exists key element

    • 示例

    127.0.0.1:6379> bf.add key1 123
    (integer) 1
    127.0.0.1:6379> bf.exists key1 123
    (integer) 1
    
    

    redis加载布隆过滤器模块

    redis4.0.0及之后的版本,可以在redis启动的时候加载布隆过滤器模块,以支持布隆过滤器。

    下载布隆过滤器模块源码

    在github下载一个redisBloom稳定的版本: https://github.com/RedisBloom/RedisBloom

    编译

    下载解压后的目录/usr/soft/redisBloom-2.2.2
    在这个目录下执行 make
    可以看到编译出了一个 redisbloom.so

    redis服务启动加载模块

    启动redis服务并且加载上面的模块(模块地址/usr/soft/redisBloom-2/redisbloom.so)

    redis-server /usr/local/etc/redis.conf --loadmodule /usr/soft/redisBloom-2/redisbloom.so
    //启动成功后,我们可以查看一下模块是否被加载成功
    
    127.0.0.1:6379> module list
    1) 1) "name"
       2) "bf"
       3) "ver"
       4) (integer)20202
    //可以看到模块加载成功了。
    

    布隆过滤器与 hyperLogLog的区别

    虽然而这都是在大数据量下的数据判断,但是侧重点会不同一些。
    布隆过滤器关注元素是否在一个大的集合中;hyperLogLog关注
    集合的数量,hyperLogLog可以根据pfadd的返回值判断元素是否存在,
    但是结果不是幂等的。

    布隆过滤器的原理

    从最上面我们直到布隆过滤器的是由一个很长的位数组和k个hash函数组成的,
    那么他们是怎么工作的呢?
    当添加一个元素的时候,使用上面的k个hash函数分别计算得到k个整型索引,
    每个索引对位数组长度进行取模运算得到各自的位置,将这些位置都置为1。
    判断是否存在就是通过上面的k个hash计算索引,取模,取模结果的所有位
    都是1,则这个元素存在集合中,否则不存在。
    因为hash、取模会有碰撞、所以会存在误差率。

    应用场景

    • 网页爬虫url去重
    • 垃圾邮件过滤
    • 秒杀系统

    参考

    redis添加bloom filter布隆过滤器插件

    布隆过滤器(Bloom Filter)的原理和实现

    Redis如何实现布隆过滤器

    展开全文
  • 一、BitMap 解决的问题:大数据量下的排序、查找、去重。 1、关键 通过 bit位 表示一个数值的状态(是否存在),那么1MB能...3、应用场景 对 不重复的 密集整数 进行排序 查找数据是否存在海量集合中 找出没有重复的数
  • 使用布隆过滤器解决缓存穿透问题 什么是缓存穿透? 缓存穿透是指查询一个根本不存在的数据,缓存层和存储层都不会命中,但是出于容错的考虑,如果从存储层查不到数据则不写入缓存层。 注:一般的逻辑 查询缓存 ->...
  • 场景 假设你现在要处理这样一个问题,你有一个网站并且拥有很多访客,每当有用户访问时,你想知道这个ip是不是第一次访问你的网站。 hashtable 可以么 一个显而易见的答案是将所有的 IP 用 hashtable 存起来,每次...
  • 今天碰到个业务,他的 Redis 集群有个大 Value 用途是作为布隆过滤器,自己之前只是听说过这个,但是没深入了解过,趁这个机会补充一下知识。 在进入正文之前,之前看到的有句话我觉得说得很好: Data structures...
  • 布隆过滤器的概念这里就不赘述了 参考链接 如何在海量元素中(例如 10 亿无序、不定长、不重复)快速判断一个元素是否存在? 很简单嘛, 把所有的数据都添加到数据结构里去, 如list或map等, get判断不就完了嘛. ...
  • 布隆过滤器其实就是将目标数据经过布隆大哥自己写的hash算法, 这个算法是将 将一个8位比特位1的数据 也就是8个1(这个是比特位的1)(数量根据需要的成功率会有变化), 然后将每个比特位通过他的算法对应到一个长度位64k...
  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...
  • 大意是不同的数据结构有不同的适用场景和优缺点,你需要仔细权衡自己的需求之后妥善适用它们,布隆过滤器就是践行这句话的代表。 什么是布隆过滤器 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构...
  • 什么是布隆过滤器 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和...很多的使用都是利用布隆过滤器一定不存在的这个特性来进行的。 HashMap当然这
  • 1、布隆过滤器 使用场景 1.布隆过滤器的特性是:去重,多数去重场景都跟这个特性有关。比如爬虫的时候去掉相同的URL,推送消息去掉相同的消息等。 2.解决缓存击穿的问题。 3.反垃圾邮件,从数十亿个垃圾邮件列表...
  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...
  • 文章目录布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter1、布隆过滤器的起源,用途2、布隆过滤器的概念3、布隆过滤器的优缺点1、优点2、缺点4、应用场景5、布隆过滤器的工作原理6、布隆过滤器的设计 ...
  • 布隆过滤器使用场景4.通过 Java 编程手动实现布隆过滤器5.利用Google开源的 Guava中自带的布隆过滤器6.Redis 中的布隆过滤器6.1介绍6.2使用Docker安装6.3常用命令一览6.4实际使用 海量数据处理以及缓存穿透这两个...
  • 用Java实现布隆过滤器

    千次阅读 2020-05-11 15:47:03
    布隆过滤器使用场景4.用Java 实现布隆过滤器 1.什么是布隆过滤器布隆过滤器(Bloom Filter)是一个叫做 Bloom 的老哥于1970年提出的。 实际上可以把它看作由二进制向量(或者说位数组)和一系列随机映射函数...
  • 布隆过滤器(概率型数据结构): 某样东西一定不存在或可能存在 布隆过滤器原理? 把一个 key 进行好几个 hash 运算后,得到的 hash 值,对一个 bit 数组取模放进去,用 1 表示, 比如下面示例: 这个 再有其他 key 到来,再...
  • redis应用实战(布隆过滤器)

    万次阅读 2018-12-26 20:09:40
    布隆过滤器是Burton Howard Bloom在1970年提出来的,一种空间效率极高的概率型算法和数据结构,主要用来 判断一个元素是否在集合中存在。因为他是一个概率型的算法,所以会存在一定的误差,如果传入一个值去布隆过 ...
  • https://blog.csdn.net/wx1528159409/article/details/88357728
  • 一、什么是布隆过滤器布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 对于布隆过滤器而言,它的本质是一个位数组:位数组就是数组的每个元素都...
  • 布隆过滤器的概念2、 布隆过滤器的插入与查找2.1 布隆过滤器的插入2.2 布隆过滤器的查找2.3 布隆过滤器产生误判的原因3、布隆过滤器的删除4、布隆过滤器优点5、布隆过滤器缺陷6、使用场景7、海量数据应用例题 ...
  • 我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经看过的内容。问题来了,新闻客户端推荐系统如何实现推送去重的?  会想到服务器记录了用户看过的所有历史记录,当...
  • 介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
  • 布隆过滤器 本质上布隆过滤器是一种数据结构,可以用来告诉你 “某样东西一定不存在或者可能存在”。 如果我们平时常用的List,set,map ,tree 来实现同样的效果,set和map都是采用map的数据结构,时间复杂度是O1级别...
  • 布隆过滤器原理以及java/redis使用

    千次阅读 2020-08-05 17:55:30
    文章目录布隆过滤器布隆过滤器原理使用场景利用Google开源的 Guava中自带的布隆过滤器Redis 中的布隆过滤器使用Docker安装命令 布隆过滤器 布隆过滤器是用于判断一个元素是否在集合中。通过一个位数组和N个hash函数...
  • 目录布隆过滤器HBase中如何设置 布隆过滤器 布隆是个人,发明了布隆算法,基于布隆算法实现的组件,称为布隆过滤器!这个组件一般是用作过滤! 过滤功能: 在海量数据中,用非常高的效率和性能,判断一个数据是否在...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,808
精华内容 4,323
关键字:

布隆过滤器应用场景