BloomFilter(布隆过滤器)
发布时间:2020-12-14 01:27:43 所属栏目:大数据 来源:网络整理
导读:bloomfilter(布隆过滤器): ? 要判断一个元素是否在一个集合中出现,一般情况下就是将这个集合的元素保存下来,然后再到这个集合中一一比较即可,但是如果这个集合中的元素很多的话,不仅需要的内存很大,而且查找起来也比较慢。 ? 为了提高效率我们可以采用
bloomfilter(布隆过滤器):
? 要判断一个元素是否在一个集合中出现,一般情况下就是将这个集合的元素保存下来,然后再到这个集合中一一比较即可,但是如果这个集合中的元素很多的话,不仅需要的内存很大,而且查找起来也比较慢。
? 为了提高效率我们可以采用hash表,并且将集合中的元素都映射到bitmap中的一个位上,这样的话就会节省空间和查找的时间。但是由于哈希冲突的原因,我们有可能会产生误判,即不同的元素经过散列函数之后可能产生同一个地址。
1、怎样降低误判的概率
? 为了降低误判的概率,我们可以将一个元素经过多个散列函数,映射到多个位上,如果这几个位上都为1,我们就认为这个元素是存在的,但是只要有一个位为0,那么这个元素就一定不存在。所以对于布隆过滤器来说,它的存在是不准确的,但是它的不存在一定是准确的。
2、如何对布隆过滤器进行删除操作
? 因为一个位可能对应着多个元素,所以当我们删除一个元素时不能直接删除,否则会影响到其他元素。这时候我们可以采用引用计数的方式来实现删除操作,为了记录这个元素出现的次数,我们这时候就不能用一个位来表示状态了,我们可以用一个无符号整形来表示状态。具体实现方式是:用一个vector<size_t>,将集合中的每个元素经过多个散列函数映射到多个位置,而每个位置的值则表示有多少个元素映射到这个位置。
? ??
布隆过滤器也是hash和bitmap的一种扩展,但是它得到的存在的结果只是一种近似精确的。
#pragma once #include<vector> using namespace std; struct _HashFunc1 { size_t operator()(const string& str) { size_t num=0; for (int i = 0; i < (int)str.size();i++) { num = num * 131 +str[i]; } return num; } }; struct _HashFunc2 { size_t operator()(const string& str) { size_t num=0; for (int i =0; i < (int)str.size(); i++) { num = num * 65599 + str[i]; } return num; } }; struct _HashFunc3 { size_t operator()(const string& str) { size_t magic = 63689; size_t num = 0; for (int i = 0; i < (int)str.size(); i++) { num = num *magic + str[i]; magic *= 378551; } return num; } }; struct _HashFunc4 { size_t operator()(const string& str) { size_t num = 0; for (int i = 0; i < (int)str.size(); i++) { if ((i & 1) == 0) { num ^= ((num << 7) ^ str[i] ^ (num >> 3)); } else { num^= (~((num << 11) ^ str[i]^ (num >> 5))); } } return num; } }; struct _HashFunc5 { size_t operator()(const string& str) { if (str.empty()) return 0; size_t num = 5381; for (int i = 0; i < (int)str.size(); i++) { num =num* 33 ^str[i]; } return num; } }; //支持Reset的bloomfliter template<typename K=string,class HashFunc1=_HashFunc1,class HashFunc2 = _HashFunc2,class HashFunc3= _HashFunc3,class HashFunc4= _HashFunc4,class HashFunc5 = _HashFunc5> class BloomFilter { public: BloomFilter(size_t range) { _bitmap.resize(range*5); //为了减少误判,提高精度,用5个位置来表示一个数 } void Set(const K& key) //要设置为1,必须将5个位置都设置 { size_t index1 = HashFunc1()(key) % _bitmap.size(); size_t index2 = HashFunc2()(key) % _bitmap.size(); size_t index3 = HashFunc3()(key) % _bitmap.size(); size_t index4 = HashFunc4()(key) % _bitmap.size(); size_t index5 = HashFunc5()(key) % _bitmap.size(); _bitmap[index1]++; _bitmap[index2]++; _bitmap[index3]++; _bitmap[index4]++; _bitmap[index5]++; } bool ReSet(const K& key) //采用引用计数的方式复位 { size_t index1 = HashFunc1()(key) % _bitmap.size(); size_t index2 = HashFunc2()(key) % _bitmap.size(); size_t index3 = HashFunc3()(key) % _bitmap.size(); size_t index4 = HashFunc4()(key) % _bitmap.size(); size_t index5 = HashFunc5()(key) % _bitmap.size(); if (_bitmap[index1] == 0 || _bitmap[index2] == 0 || _bitmap[index3] == 0 || _bitmap[index4] == 0 || _bitmap[index5] == 0) //只要有一个为0,说明这个key不存在 return false; //要是都不为0,才减一 _bitmap[index1]--; _bitmap[index2]--; _bitmap[index3]--; _bitmap[index4]--; _bitmap[index5]--; return true; } bool Test(const K& key) { size_t index1 = HashFunc1()(key) % _bitmap.size(); size_t index2 = HashFunc2()(key) % _bitmap.size(); size_t index3 = HashFunc3()(key) % _bitmap.size(); size_t index4 = HashFunc4()(key) % _bitmap.size(); size_t index5 = HashFunc5()(key) % _bitmap.size(); //只有五个位置都为1,才存在 if (_bitmap[index1] != 0 && _bitmap[index2] != 0 && _bitmap[index3] != 0 && _bitmap[index4] != 0 && _bitmap[index5] != 0) return true; return false; } private: vector<size_t> _bitmap; }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |