BloomFilter(布隆过滤器)
BloomFilter布隆过滤器,大数据处理2016-11-08
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;
};