如何理解

如何理解，很多新手对此不是很清楚，为了帮助大家解决这个难题，下面小编将为大家详细讲解，有这方面需求的人可以来学习下，希望你能有所收获。

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

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。【详见百度百科】

总的来说：布隆过滤器就是利用哈希算法+位图实现的。

所以布隆过滤器的底层我们就用一个位图封装。

对哈希算法不熟悉的可以看博主博客http://helloleex.blog.51cto.com/10728491/1770568

如果对位图不太熟悉的可以查看博主的博客http://helloleex.blog.51cto.com/10728491/1772827

#pragma once#include#include"Bit_Map.h"#include"HashFunc.h"using namespace std;//5个哈希函数的仿函数template,class HashFunc2 = _HashFunc2,class HashFunc3 = _HashFunc3, class HashFunc4 = _HashFunc4, class HashFunc5 = _HashFunc5>class BloomFilter{public:        BloomFilter(size_t size)        {                //size_t newsize = _GetNextPrime(size);                //_capacity = newsize;                //size不一定是素数，在素数表中取一个素数开一个素数大的空间                _capacity = _bm.Resize(size);        }        void Set(const K& key)        {                size_t index1 = HashFunc1()(key);                size_t index2 = HashFunc2()(key);                size_t index3 = HashFunc3()(key);                size_t index4 = HashFunc4()(key);                size_t index5 = HashFunc5()(key);                _bm.Set(index1);                _bm.Set(index2);                _bm.Set(index3);                _bm.Set(index4);                _bm.Set(index5);        }        //布隆过滤器不能执行删除操作，因为有不同的哈希算法，可能不同的key        //标记在相同的位上，删除会把别人的记录给删除了，影响正确性。        //void Reset(const K& key);        //测试存在不一定存在，不存在一定不存在        bool Test(const K& key)        {                size_t index1 = HashFunc1()(key);                size_t index2 = HashFunc2()(key);                size_t index3 = HashFunc3()(key);                size_t index4 = HashFunc4()(key);                size_t index5 = HashFunc5()(key);                if (_bm.Test(index1) || _bm.Test(index2) ||                        _bm.Test(index3) || _bm.Test(index4) ||                        _bm.Test(index5))                        return true;                else                        return false;        }protected:        BitMap _bm;        size_t _capacity;};

HashFunc.h//5个高效的哈希算法，都是大神发明的。#pragma oncetemplate//BKDR Hash Function是一种简单快捷的hash算法，//也是Java目前采用的字符串的Hash算法（累乘因子为31）struct _HashFunc1{        size_t operator()(const T& str)        {                register size_t hash = 0;                const char* tmp = str.c_str();                while (size_t ch = (size_t)*tmp++)                {                        hash = hash * 131 + ch;                }                return hash;        }};template//RS Hash Function。因Robert Sedgwicks在其《Algorithms in C》一书中展示而得名。struct _HashFunc2{        size_t operator()(const T& str)        {                register size_t hash = 0;                size_t magic = 63689;                const char* tmp = str.c_str();                while (size_t ch = (size_t)*tmp++)                {                        hash = hash * magic + ch;                        magic *= 378551;                }                return hash;        }}; template//AP Hash Function 由Arash Partow发明的一种hash算法。struct _HashFunc3{        size_t operator()(const T& str)        {                register size_t hash = 0;                size_t ch;                const char* tmp = str.c_str();                for (long i = 0; ch = (size_t)*tmp++; i++)                {                        if ((i & 1) == 0)                        {                                hash ^= ((hash << 7) ^ ch ^ (hash >> 3));                        }                        else                        {                                hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));                        }                }                return hash;        }}; template// DJB Hash Function 2。由Daniel J. Bernstein 发明的另一种hash算法。struct _HashFunc4{        size_t operator()(const T& str)        {                const char* tmp = str.c_str();                if (!*tmp)   // 这是由本人添加，以保证空字符串返回哈希值0                          return 0;                register size_t hash = 5381;                while (size_t ch = (size_t)*tmp++)                {                        hash = hash * 33 ^ ch;                }                return hash;        }}; template//JS Hash Function 。由Justin Sobel发明的一种hash算法。struct _HashFunc5{        size_t operator()(const T& str)        {                const char* tmp = str.c_str();                if (!*tmp)        // 这是由本人添加，以保证空字符串返回哈希值0                          return 0;                register size_t hash = 1315423911;                while (size_t ch = (size_t)*tmp++)                {                        hash ^= ((hash << 5) + ch + (hash >> 2));                }                return hash;        }};

布隆过滤器是有误识别率的，虽然几率很低很低，但是如果5个哈希函数其中有一两个误识别了，就会出现错误。

而且布隆过滤器是不支持删除Reset的。因为有很几率会删除其他哈希函数所标识的记录，误识别几率大大增高。

看完上述内容是否对您有帮助呢？如果还想对相关知识有进一步的了解或阅读更多相关文章，请关注行业资讯频道，感谢您对的支持。