如何理解-创新互联
如何理解,很多新手对此不是很清楚,为了帮助大家解决这个难题,下面小编将为大家详细讲解,有这方面需求的人可以来学习下,希望你能有所收获。
我们提供的服务有:成都做网站、网站设计、微信公众号开发、网站优化、网站认证、长宁ssl等。为上千企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务,是有科学管理、有技术的长宁网站制作公司布隆过滤器(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 once template//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的。因为有很几率会删除其他哈希函数所标识的记录,误识别几率大大增高。
看完上述内容是否对您有帮助呢?如果还想对相关知识有进一步的了解或阅读更多相关文章,请关注创新互联行业资讯频道,感谢您对创新互联的支持。
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
网站题目:如何理解-创新互联
文章URL:http://pwwzsj.com/article/didhcp.html