什么是布隆过滤器
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
实现思想
如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash函数，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。
代码实现
Bloom Filter.h
#pragma once
#include"HashFunc.h"
template<class K=int,
class HashFunc1 = _HashFunc1<K>,
class HashFunc2 = _HashFunc2<K>,
class HashFunc3 = _HashFunc3<K>,
class HashFunc4 = _HashFunc4<K>,
class HashFunc5 = _HashFunc5<K>>
class BloomFilter
{
public:
BloomFilter(size_t size)
{
_bm.Resize(size);
}
void Set(K key)
{
_HashFunc1<K> hf1;
_HashFunc1<K> hf2;
_HashFunc1<K> hf3;
_HashFunc1<K> hf4;
_HashFunc1<K> hf5;
size_t index1 = hf1(key);
size_t index2 = hf2(key);
size_t index3 = hf3(key);
size_t index4 = hf4(key);
size_t index5 = hf5(key);
_bm.Set(index1);
_bm.Set(index2);
_bm.Set(index3);
_bm.Set(index4);
_bm.Set(index5);
++_capacity;
}
//布隆过滤器不能执行删除操作，因为有不同的哈希算法，可能不同的key
//标记在相同的位上，删除会把别人的记录给删除了，影响正确性。
//void Reset(const K& key);
//测试存在不一定存在，不存在一定不存在
bool Test(const K& key)
{
_HashFunc1<K> hf1;
_HashFunc1<K> hf2;
_HashFunc1<K> hf3;
_HashFunc1<K> hf4;
_HashFunc1<K> hf5;
size_t index1 = hf1(key);
size_t index2 = hf2(key);
size_t index3 = hf3(key);
size_t index4 = hf4(key);
size_t index5 = hf5(key);
if (_bm.Test(index1) && _bm.Test(index2) &&
_bm.Test(index3) && _bm.Test(index4) &&
_bm.Test(index5))
return true;
else
return false;
}
protected:
BitMap<K> _bm;
size_t _capacity;
};
BitMap.h
#pragma once
//数据类型的仿函数
template<class T>
struct DataType
{
long long operator()(const T&key)
{
return key;
}
};
//字符串类型的仿函数
template<class T>
struct StringType
{
long long operator()(const string&key)
{
long long size = 0;
for (int i = 0; i < key.size(); i++)
{
size += key[i];
}
return size/(key.size());
}
};
template<class T,template<class T>class BMFunc=DataType>
class BitMap
{
public:
BitMap(size_t size = 1)
{
_a.resize(size / 32 + 1);
}
~BitMap(){}
void Resize(size_t size)
{
_a.resize(size / 32 + 1);
}
void Set(const T& x)
{
BMFunc<T>bmf;
size_t index = bmf(x)/ 32;
size_t num = bmf(x) % 32;
if (!(_a[index] & (1 << num)))
{
_a[index] |= (1 << num);
_size++;
}
}
void Reset(const T&x)
{
BMFunc<T>bmf;
size_t index = bmf(x) / 32;
size_t num = bmf(x) % 32;
if (!(_a[index] & (1 << num)))
{
_a[index] &= (~(1 << num));
_size--;
}
}
bool Test(T x)
{
BMFunc<T> bmf;
size_t index = bmf(x)/ 32;
size_t num = bmf(x)% 32;
return _a[index]&(1 << num);
}
protected:
vector<size_t> _a;
size_t _size;
};
HashFunc.h
//5个高效的哈希算法
template<class T>
// 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++)
{
while (size_t ch = (size_t)*tmp++)
{
hash = hash * 131 + ch;
}
return hash;
}
}
};
template<class T>
//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<class T>
//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<class T>
// 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<class T>
//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;
}
};
本文出自 “学习记录” 博客，转载请与作者联系！
原文：http://10794428.blog.51cto.com/10784428/1795758