精华内容
下载资源
问答
  • 布隆过滤器优缺点

    千次阅读 2018-04-09 21:31:49
    布隆过滤器: 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。 但是随着集合中元素的增加,我们需要的存储空间会很大,检索的速度也越来越慢。 一、原理 ...

    如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。
    但是随着集合中元素的增加,我们需要的存储空间会很大,检索的速度也越来越慢。

    一、原理

    Bloom Filter 是一种空间效率很高的随机数据结构,Bloom filter 可以看做是对 bit-map 的扩展。当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。
    检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它。
    值得注意的是:如果这些点有任何一个 0,则被检索元素一定不在。
    如果都是 1,则被检索元素很可能在。

    二、优点

    空间效率和查询时间都远远超过一般的算法,布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。
    另外, 散列函数相互之间没有关系,方便由硬件并行实现。
    布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

    三、缺点

    布隆过滤器的缺点和优点一样明显。
    误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表就可以。
    另外,一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

    四、布隆过滤器的简单实现

    1、为了检测存在时比较准确,我们这里用了五个哈希函数来映射其在位图中的位置:

    template<class K>
    struct _HashFunc1
    {
        size_t BKDRHash(const char *str)
        {
            register size_t hash = 0;
            while (size_t ch = (size_t)*str++)
            {
                hash = hash * 131 + ch;            //也可以乘以31、131、1313、13131、131313.. 
            }
            return hash;
        }
        size_t operator()(const K& s)
        {
            return BKDRHash(s.c_str());
        }
    };
    
    template<class K>
    struct _HashFunc2
    {
        size_t SDBMHash(const char *str)
        {
            register size_t hash = 0;
            while (size_t ch = (size_t)*str++)
            {
                hash = 65599 * hash + ch;
                //hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  
            }
            return hash;
        }
        size_t operator()(const K& s)
        {
            return SDBMHash(s.c_str());
        }
    };  
    template<class K>
    struct _HashFunc3
    {
        size_t RSHash(const char *str)
        {
            register size_t hash = 0;
            size_t magic = 63689;
            while (size_t ch = (size_t)*str++)
            {
                hash = hash * magic + ch;
                magic *= 378551;
            }
            return hash;
        }
        size_t operator()(const K& s)
        {
            return RSHash(s.c_str());
        }
    };
    
    template<class K>
    struct _HashFunc4
    {
        size_t APHash(const char *str)
        {
            register size_t hash = 0;
            size_t ch;
            for (long i = 0; ch = (size_t)*str++; i++)
            {
                if ((i & 1) == 0)
                {
                    hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
                }
                else
                {
                    hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
                }
            }
            return hash;
        }
        size_t operator()(const K& s)
        {
            return APHash(s.c_str());
        }
    };
    template<class K>
    struct _HashFunc5
    {
        size_t JSHash(const char *str)
        {
            if (!*str)        // 这是由本人添加,以保证空字符串返回哈希值0  
                return 0;
            register size_t hash = 1315423911;
            while (size_t ch = (size_t)*str++)
            {
                hash ^= ((hash << 5) + ch + (hash >> 2));
            }
            return hash;
        }
        size_t operator()(const K& s)
        {
            return JSHash(s.c_str());
        }
    };

    2、底层结构用位图:

    class BitMap
    {
    public:
        BitMap(size_t bitSet = 10)
        :_bitCount(bitSet)
        {
            _bitSet.resize((bitSet >> 5) + 1);   
        }
        void Set(size_t whichBit)   //置1
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                _bitSet[index] |= 1 << (whichBit % 32);
        }
        void ReSet(size_t whichBit)   //置0
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                _bitSet[index] &= ~(1 << (whichBit % 32));
        }
        bool Test(size_t whichBit)   //查看比特位是0是1
        {
            size_t index = whichBit >> 5;
            if (whichBit < _bitCount)
                return _bitSet[index] & (1 << (whichBit % 32));
    
            cout << whichBit << "比特位不存在" << endl;
            return false;
        }
        size_t Count()const      //1的个数
        {
            char *pBitCount = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
            size_t count = 0;
            for (size_t i = 0; i < _bitSet.size(); i++)
            {
                int value = _bitSet[i];
                int j = 0;
                while (j < sizeof(int))
                {
                    count += pBitCount[value & 0x0F];
                    value >>= 4;
                    count += pBitCount[value & 0x0F];
                    value >>= 4;
                    j++;
                }
            }
            return count;
        }
        size_t Size()const    //比特位的个数
        {
            return _bitCount;
        }
    protected:
        vector<int> _bitSet;
        size_t _bitCount;
    };

    关于位图的介绍请看上篇文章:

    https://blog.csdn.net/baidu_37964071/article/details/79859196

    3、布隆过滤器的实现

    template<class K, class KTOInt1 = _HashFunc1<K>,
                      class KTOInt2 = _HashFunc2<K>,
                      class KTOInt3 = _HashFunc3<K>,
                      class KTOInt4 = _HashFunc4<K>,
                      class KTOInt5 = _HashFunc5<K>>
    //检测一个元素是不是在集合里
    class BloomFilter
    {
    public:
        BloomFilter(size_t size)
            :_bmp(size)
            , _size(0)
        {}
    
        void Insert(const K& key)
        {
            size_t bitCount = _bmp.Size();
            size_t index1 = KTOInt1()(key) % bitCount;
            size_t index2 = KTOInt2()(key) % bitCount;
            size_t index3 = KTOInt3()(key) % bitCount;
            size_t index4 = KTOInt4()(key) % bitCount;
            size_t index5 = KTOInt5()(key) % bitCount;
    
            _bmp.Set(index1);
            _bmp.Set(index2);
            _bmp.Set(index3);
            _bmp.Set(index4);
            _bmp.Set(index5);
            _size++;
    
            cout << index1 << " " << index2 << " " << index3 << " " << index4 << " " << index5 << endl;
        }
    
        bool IsInBloomFilter(const K&key)
        {
            size_t bitCount = _bmp.Size();
    
            size_t index1 = KTOInt1()(key) % bitCount;
            if (!_bmp.Test(index1))
                return false;
            size_t index2 = KTOInt2()(key) % bitCount;
            if (!_bmp.Test(index2))
                return false;
            size_t index3 = KTOInt3()(key) % bitCount;
            if (!_bmp.Test(index3))
                return false;
            size_t index4 = KTOInt4()(key) % bitCount;
            if (!_bmp.Test(index4))
                return false;
            size_t index5 = KTOInt5()(key) % bitCount;
            if (!_bmp.Test(index5))
                return false;
    
            return true;   //可能
        }
    
        size_t Size()
        {
            return _size;
        }
    protected:
        BitMap _bmp;
        size_t _size;    //实际元素的个数
    };

    看测试:

    void BloomFilterTest()
    {
        BloomFilter<string> bft(100);
        bft.Insert("张三");
        bft.Insert("李四");
        bft.Insert("刘师");
    
        cout << bft.IsInBloomFilter("张三") << endl;
        cout << bft.IsInBloomFilter("小明") << endl;
        cout << bft.Size() << endl;
    }

    结果:
    这里写图片描述

    展开全文
  • 布隆过滤器1、 布隆过滤器的概念2、 布隆过滤器的插入与查找2.1 布隆过滤器的插入2.2 布隆过滤器的查找2.3 布隆过滤器产生误判的原因3、布隆过滤器的删除4、布隆过滤器优点5、布隆过滤器缺陷6、使用场景7、海量数据...


    1、 布隆过滤器的概念

    布隆过滤器(BloomFilter)是一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 某样东西一定不存在或者可能存在,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间,但是布隆过滤器也存在一定的缺陷:数据只能插入不能删除。
    布隆过滤器的底层实现是位图。

    2、 布隆过滤器的插入与查找

    2.1 布隆过滤器的插入

    布隆过滤器是由一个很长的bit数组和一系列哈希函数组成的。结构如下:
    在这里插入图片描述
    数组的每个元素都只占1bit空间,并且每个元素只能为0或1。

    布隆过滤器还拥有k个哈希函数,当一个元素加入布隆过滤器时,会使用k个哈希函数对其进行k次计算,得到k个哈希值,并且根据得到的哈希值,在数组中把对应下标的值置位1。

    例:“baidu"这个值对应的三个不同的哈希函数返回三个哈希值分别为:1 、4 、7,则将其对应的下标置1,其结构就会变成下面这样:
    在这里插入图片描述

    2.2 布隆过滤器的查找

    布隆过滤器的思想将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1.

    所以在查询某个是否存在时,若该值利用三个不同的哈希函数返回的哈希值对应的下标至少有一个为0,则说明该值一定不存在,若对应的值均为1,说明该值可能存在。

    为什么说是可能存在而不是一定存在呢?
    因为可能会出现不同的值利用哈希函数返回的哈希值对应的下标相同,所以说只能得出可能存在的结果,即某些哈希函数存在一定误判。

    2.3 布隆过滤器产生误判的原因

    当插入的元素越来越多时,当一个不在布隆过滤器中的元素,经过同样规则的哈希计算之后,得到的值在数组中查询,有可能这些位置因为其他的元素先被置1了。

    所以布隆过滤器存在误判的情况,但是如果布隆过滤器判断某个元素不在布隆过滤器中,那么这个值就一定不在。

    3、布隆过滤器的删除

    在介绍布隆过滤器的概念时提到布隆过滤器的缺点是不支持删除,但是它不支持删除的原因是什么呢?
    因为删除一个元素时可能会影响到其他元素。

    举个例子:“baidu"利用三个不同的哈希函数返回的哈希值为1,4,7,“tencent"利用三个不同的哈希函数返回的哈希值为3,4,8,假设删除“baidu"这个元素,则1,4,7对应的下标置0,但是“tencent"这个元素与“baidu”对应的下标4重合,这样就会将“tencent”这个元素也删除,所以布隆过滤器不支持删除。

    一种支持删除的方法:将布隆过滤器中的每个比特位扩展成一个小的计数器,插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一,删除元素时,给k个计数器减一,通过多占用几倍存储空间的代价来增加删除操作。

    但是这中删除方法也存在一定缺陷:

    1. 无法确认元素是否真正在布隆过滤器中
    2. 存在计数回绕

    4、布隆过滤器优点

    1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
    2. 哈希函数相互之间没有关系,方便硬件并行运算
    3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
    4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
    5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
    6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

    5、布隆过滤器缺陷

    1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据)
    2. 不能获取元素本身
    3. 一般情况下不能从布隆过滤器中删除元素
    4. 如果采用计数方式删除,可能会存在计数回绕问题

    6、使用场景

    1. 网页爬虫对URL的去重,避免爬去相同的URL地址。
    2. 垃圾邮件过滤,从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱。
    3. 解决数据库缓存击穿,黑客攻击服务器时,会构建大量不存在于缓存中的key向服务器发起请求,在数据量足够大的时候,频繁的数据库查询会导致挂机。
    4. 秒杀系统,查看用户是否重复购买。

    7、海量数据应用例题

    1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法?
      思路:精确算法利用位图来实现
      近似算法利用布隆过滤器实现,将一个文件的中100亿个query放在一个布隆过滤器中,另个一个文件中的数据到布隆过滤器中去查找,若查找到则说明是这两个文件的交集。
    展开全文
  • 在介绍布隆过滤器之前我们首先引入几个场景。 场景一 在一个高并发的计数系统中,如果一个key没有计数,此时我们应该返回0,但是访问的key不存在,相当于每次访问缓存都不起作用了。那么如何避免频繁访问数量为0的...
  • 布隆过滤器优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。本文将介绍布隆过滤器的原理以及Redis如何实现布隆过滤器,感兴趣的朋友跟随小编一起看看吧
  • 详解布隆过滤器的原理、优缺点

    千次阅读 2019-11-19 23:50:03
    什么是布隆过滤器? 本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希...

    什么是布隆过滤器?

    本质上布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。
    在这里插入图片描述

    HashMap 的问题

    讲述布隆过滤器的原理之前,我们先思考一下,通常你判断某个元素是否存在用的是什么?应该蛮多人回答 HashMap 吧,确实可以将值映射到 HashMap 的 Key,然后可以在 O(1) 的时间复杂度内返回结果,效率奇高。但是 HashMap 的实现也有缺点,例如存储容量占比高,考虑到负载因子的存在,通常空间是不能被用满的,而一旦你的值很多例如上亿的时候,那 HashMap 占据的内存大小就变得很可观了。

    还比如说你的数据集存储在远程服务器上,本地服务接受输入,而数据集非常大不可能一次性读进内存构建 HashMap 的时候,也会存在问题。

    布隆过滤器数据结构

    布隆过滤器是一个 bit 向量或者说 bit 数组,长这样:
    在这里插入图片描述
    如果我们要映射一个值到布隆过滤器中(插入),我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为:
    在这里插入图片描述
    值得注意的是,4 这个 bit 位由于两个值的哈希函数都返回了这个 bit 位,因此它被覆盖了。现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

    这是为什么呢?答案跟简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在。

    支持删除么

    目前我们知道布隆过滤器可以支持 add 和 isExist 操作,那么 delete 操作可以么,答案是不可以,例如上图中的 bit 位 4 被两个值共同覆盖的话,一旦你删除其中一个值例如 “tencent” 而将其置位 0,那么下次判断另一个值例如 “baidu” 是否存在的话,会直接返回 false,而实际上你并没有删除它。

    如何解决这个问题,答案是计数删除。但是计数删除需要存储一个数值,而不是原先的 bit 位,会增大占用的内存大小。这样的话,增加一个值就是将对应索引槽上存储的值加一,删除则是减一,判断是否存在则是看值是否大于0。

    如何选择哈希函数个数和布隆过滤器长度

    很显然,过小的布隆过滤器很快所有的 bit 位均为 1,那么查询任何值都会返回“可能存在”,起不到过滤的目的了。布隆过滤器的长度会直接影响误报率,布隆过滤器越长其误报率越小。

    另外,哈希函数的个数也需要权衡,个数越多则布隆过滤器 bit 位置位 1 的速度越快,且布隆过滤器的效率越低;但是如果太少的话,那我们的误报率会变高。

    布隆过滤器优点

    1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关
    2. 哈希函数相互之间没有关系,方便硬件并行运算
    3. 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势
    4. 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势
    5. 数据量很大时,布隆过滤器可以表示全集,其他数据结构不能
    6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

    布隆过滤器缺陷

    1. 有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白
      名单,存储可能会误判的数据)
    2. 不能获取元素本身
    3. 一般情况下不能从布隆过滤器中删除元素
    4. 如果采用计数方式删除,可能会存在计数回绕问题

    参考博文:https://www.jianshu.com/p/2104d11ee0a2

    展开全文
  • 布隆过滤器是什么  布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。...布隆过滤器优缺点 优点:  1.布隆过滤器的存储空间和插入/查询时间都是常数
  • 布隆过滤器的实现及其优缺点

    千次阅读 2017-08-15 13:31:12
    布隆过滤器是由一个很长的二进制向量和一系列随机映射函数组成。它可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误判。 布隆过滤器的原理:底层使用的...

    布隆过滤器是由一个很长的二进制向量和一系列随机映射函数组成。它可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误判。
    布隆过滤器的原理:底层使用的是位图。当一个元素被加入集合时,通过 K 个 Hash 函数将这个元素映射成一个位阵列(Bit array)中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:
    1、如果这些点有任何一个 0,则被检索元素一定不在;
    2、如果都是 1,则被检索元素很可能在。
    布隆过滤器的优点 : 空间效率和查询时间都远远超过一般的算法,布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系,方便由硬件并行实现。布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势。
    布隆过滤器的缺点:误算率是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。(误判补救方法是:再建立一个小的白名单,存储那些可能被误判的信息。)
    另外,一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位数组变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
    布隆过滤器的实现:
    common.h文件,定义五个哈希函数:

    //字符转数字:BKDRHash
    size_t BKDRHash(const char * str)
    {
        unsigned int seed = 131; // 31 131 1313 13131 131313
        unsigned int hash = 0;
        while (*str)
        {
            hash = hash * seed + (*str++);
        }
        return (hash & 0x7FFFFFFF);
    }
    //字符转数字:SDBMHash
    size_t SDBMHash(const char* str)
    {
        register size_t hash = 0;
        while(size_t ch = (size_t)*str++)
        {
        hash = 65599*hash+ch;
        //hash = (size_t)ch+(hash<<6)+ (hash<<16)-hash;
        }
        return hash;
    }
    //字符转数字:RSHash
    size_t RSHash(const char *str)
    {
        register size_t hash = 0;
        size_t magic = 63689;
        while (size_t ch = (size_t)*str++)
        {
            hash = hash * magic + ch;
            magic *= 378551;
        }
        return hash;
    }
    //字符转数字:APHash
    size_t APHash(const char* str)
    {
        register size_t hash = 0;
        size_t ch;
        for (long i = 0; ch = (size_t)*str++; i++)
        {
            if (0 == (i&1))
            {
                hash ^= ((hash << 7) ^ (hash >> 3));
            }
            else
            {
                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
            }
        }
        return hash;
    }
    //字符转数字:JSHash
    size_t JSHash(const char* str)
    {
        if (!*str)
            return 0;
        register size_t hash = 1315423911;
        while (size_t ch = (size_t)*str++)
        {
            hash ^= ((hash << 5) + ch + (hash >> 2));
        }
        return hash;
    }
    
    template<typename K>
    struct _Fun1
    {
        size_t operator()(const K& key)
        {
            return BKDRHash(key.c_str());
        }
    };
    
    template<typename K>
    struct _Fun2
    {
        size_t operator()(const K& key)
        {
            return SDBMHash(key.c_str());
        }
    };
    
    template<typename K>
    struct _Fun3
    {
        size_t operator()(const K& key)
        {
            return RSHash(key.c_str());
        }
    };
    
    template<typename K>
    struct _Fun4
    {
        size_t operator()(const K& key)
        {
            return APHash(key.c_str());
        }
    };
    
    template<typename K>
    struct _Fun5
    {
        size_t operator()(const K& key)
        {
            return JSHash(key.c_str());
        }
    };

    底层结构:位图

    #include<iostream>
    #include<vector>
    using namespace std;
    class BitMap
    {
    public:
        BitMap()
        {}
        BitMap(size_t size)
        {
            _table.resize((size >> 5) + 1);
        }
        void Set(int val)//将对应bit位置1--等同于插入一个元素
        {
            size_t byteNo = val >> 5;
            size_t bitNo = val % 32;
            _table[byteNo] |= (1 << bitNo);
        }
        void Reset(int val)//将对应bit位置0--等同于删除一个元素
        {
            size_t byteNo = val >> 5;
            size_t bitNo = val % 32;
            _table[byteNo] &= ~(1 << bitNo);
        }
        bool Test(int val)
        {
            size_t byteNo = val >> 5;
            size_t bitNo = val % 32;
            if ((1 << bitNo)&_table[byteNo])
            {
                return true;
            }
            else
            {
                return false;
            }
        }
    private:
        vector<int> _table;
    };

    布隆过滤器的实现:

    #include "BitMap.hpp"
    #include "common.h"
    template<typename T,class Fun1 = _Fun1<T>,
                      class Fun2 = _Fun2<T>,
                      class Fun3 = _Fun3<T>,
                      class Fun4 = _Fun4<T>,
                      class Fun5 = _Fun5<T>>
    class BloomFilter
    {
    public:
        BloomFilter(size_t size)
            : _bm(size)
            , _capacity(size)
        {}
        void Insert(const T& key)
        {
            size_t idx1 = Fun1()(key) % _capacity;
            _bm.Set(idx1);
            size_t idx2 = Fun2()(key) % _capacity;
            _bm.Set(idx2);
            size_t idx3 = Fun3()(key) % _capacity;
            _bm.Set(idx3);
            size_t idx4 = Fun4()(key) % _capacity;
            _bm.Set(idx4);
            size_t idx5 = Fun5()(key) % _capacity;
            _bm.Set(idx5);
            cout << idx1 << " " << idx2 << " " << idx3 << " " << idx4 << " " << idx5 << " " << endl;
        }
        bool Find(const T& key)
        {
            size_t idx1 = Fun1()(key) % _capacity;
            size_t idx2 = Fun2()(key) % _capacity;
            size_t idx3 = Fun3()(key) % _capacity;
            size_t idx4 = Fun4()(key) % _capacity;
            size_t idx5 = Fun5()(key) % _capacity;
            if (!_bm.Test(idx1))
                return false;
            if (!_bm.Test(idx2))
                return false;
            if (!_bm.Test(idx3))
                return false; 
            if (!_bm.Test(idx4))
                return false; 
            if (!_bm.Test(idx5))
                return false;
            cout << idx1 << " " << idx2 << " " << idx3 << " " << idx4 << " " << idx5 << " " << endl;
            return true;
        }
    private:
        BitMap _bm;
        size_t _capacity;
    };
    void FunTest()
    {
        BloomFilter<string> bf(100);
        bf.Insert("圆通");
        bf.Insert("韵达");
        bf.Insert("天天");
        bf.Insert("汇通");
        bf.Insert("中通");
        cout<<bf.Find("天天")<<endl;
        cout << bf.Find("邮政")<<endl;
    }
    展开全文
  • 缺点 但是布隆过滤器缺点和优点一样明显。误算率(False Positive)是其中之一。随着存入的元素数量增加,误算率随之增加。但是如果元素数量太少,则使用散列表足矣。 另外,一般情况下不能从布隆过滤器中删除...
  • 布隆过滤器

    千次阅读 2019-03-17 22:38:39
    布隆过滤器概述 简单来说,布隆过滤是判断一个值(key)是否在一个集合中的一种特别的...缺点:有一定的误报比率,就是不在集合中的值可能也会被当做在集合中,而误报比率和具体的申请的布隆过滤器的内存空间大小以...
  • 布隆过滤器缺点

    2020-02-10 19:45:36
    布隆过滤器在时间和空间上的效率比较高,但也有缺点: 存在误判。布隆过滤器可以100%确定一个元素不在集合之中,但不能100%确定一个元素在集合之中。当k个位都为1时,也有可能是其它的元素将这些bit置为1的。 删除...
  • 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,...
  • 布隆过滤器优缺点③. 布隆过滤器的使用场景④. 布隆过滤器原理⑤. 布谷鸟过滤器(了解) ①. 布隆过滤器BloomFilter的概述 ①. 它实际上是一个很长的二进制数组+一系列随机hash算法映射函数,主要用于判断一个元素...
  • 在文章里咱们说了解决缓存穿透的办法之一,就是布隆过滤器,可是上次并无讲如何使用布隆过滤器。java做为暖男的老哥,给大家补上,请叫我IT老暖男。web 什么是布隆过滤器布隆过滤器(Bloom Filter),是1970年,由一个...
  • 文章目录布隆过滤器 - Redis 布隆过滤器,Guava 布隆过滤器 BloomFilter1、布隆过滤器的起源,用途2、布隆过滤器的概念3、布隆过滤器优缺点1、优点2、缺点4、应用场景5、布隆过滤器的工作原理6、布隆过滤器的设计 ...
  • 布隆过滤器算法代码

    2017-09-18 17:24:13
    比如说,一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件(email)提供商,总是需要过滤来自发送垃圾邮件的人(spamer)的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册...
  • 布隆过滤器 一、历史背景知识  布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和...
  • 布隆过滤器 布隆过滤器是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “一定不存在或者可能存在”。 相比于传统的 List、Set、Map 等数据...
  • 一、什么是布隆过滤器布隆过滤器可以用来判断一个元素是否在一个集合中。它的优势是只需要占用很小的内存空间以及有着高效的查询效率。 对于布隆过滤器而言,它的本质是一个位数组:位数组就是数组的每个元素都...
  • 使用同一组散列函数的布隆过滤器可以进行交、并、差运算 缺点: 1.误判率,即存在假阳性(False Position),不能准确判断元素是否在集合中 2.不能获取元素本身 3.一般情况下不能从布隆过滤器中删除元素 
  • 为什么需要布隆过滤器 想象一下遇到下面的场景你会如何处理: 手机号是否重复注册 用户是否参与过某秒杀活动 伪造请求大量 id 查询不存在的记录,此时缓存未命中,如何避免缓存穿透 针对以上问题常规...
  • 当时没想到怎么做,回了家一拍大腿才想起来这是布隆过滤器…… 唉,在极客时间学过这个概念,但是学完之后再也没用到过,而且太久没打LOL了,所以远远地抛到脑后…… 今天赶快复习一下…… 作用 布隆过滤器...
  • 布隆过滤器的应用 我们先来看下布隆过滤器的应用场景,让大家知道神奇的布隆过滤器到底能做什么。 缓存穿透 我们经常会把一部分数据放在Redis等缓存,比如产品详情。 这样有查询请求进来,我们可以根据产品Id直接去...
  • 什么是布隆过滤器 布隆过滤器(Bloom Filter)是1970年由布隆提出的,它实际上是由一个很长的二进制向量和一系列随意映射函数组成。 它是一种基于概率的数据结构,主要用来判断某个元素是否在集合内,它具有运行...
  • 说一说布隆过滤器

    千次阅读 2020-12-23 04:51:03
    它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难为什么要用布隆过滤器?事实上,布隆过滤器被广泛用于网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统以及解决缓存穿透...
  • 布隆过滤器 为什么需要布隆过滤器 如果想判断一个元素是不是在一个集合里,一般想到的是将集合中所有元素保存起来,然后通过比较确定。链表、树、散列表(又叫哈希表,Hash table)等等数据结构都是这种思路。 但是...
  • Redis布隆过滤器

    2021-01-22 12:19:10
    redis+布隆过滤器思路图:https://kdocs.cn/l/sgVaSvSB3Z0s 几个小案例 ①、原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中? 解决办法一:将10亿个号码存入数据库中...
  • 过滤器使用场景: 比如有如下几个需求: 1.原本有10亿个号码,现在又来了10万个号码,要快速准确判断这10万个号码是否在10亿个号码库中?  解决办法一:将10亿个号码存入数据库中,进行数据库查询,准确性有了,...
  • 布隆过滤器之C++实现

    热门讨论 2011-11-20 18:52:46
    做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否在某个字典内,当集合很大的时候,用布隆过滤器很有优势,不过使用前,请了解它的优缺点缺点是有一定的误判率)
  • 分布式布隆过滤器实践定义原理guava布隆过滤器使用redis隆过滤器使用优缺点优点缺点使用场景最后 定义 布隆过滤器是由Burton Howard Bloom大佬在1970年提出的一种概念。由一个很长的二进制数组和一些哈希函数所构成...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 9,637
精华内容 3,854
关键字:

布隆过滤器的优缺点