布隆过滤器：实现代码

#pragma once #include <string> #include "BitMap.h" struct HashFunc1 {	size_t BKDRHash(const char *str)  	{  	register size_t hash = 0;  	while (size_t ch = (size_t)*str++)  	{         	hash = hash * 131 + ch;   // 也可以乘以31、131	return hash;  	} 	}	size_t operator()(const string& s)	{	return BKDRHash(s.c_str());	} }; struct HashFunc2 {	size_t SDBMHash(const char *str)  	{  	register size_t hash = 0;  	while (size_t ch = (size_t)*str++)  	{  	hash = 65599 * hash + ch;        	}  	return hash;  	}  	size_t operator()(const string& s)	{	return SDBMHash(s.c_str());	} }; struct HashFunc3 {	size_t RSHash(const char *str)  	{  	register size_t hash = 0;  	size_t magic = 63689;     	while (size_t ch = (size_t)*str++)  	{  	hash = hash * magic + ch;  	magic *= 378551;  	}  	return hash;  	}	size_t operator()(const string& s)	{	return RSHash(s.c_str());	} }; struct HashFunc4 {	size_t APHash(const char *str)  	{  	register size_t hash = 0;  	size_t ch;  	for (long i = 0; ch = (size_t)*str++; i++)  	{  	if ((i & 1) == 0)  	{  	hash ^= ((hash << 7) ^ ch ^ (hash >> 3));  	}  	else  	{  	hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));  	}  	}  	return hash;  	}	size_t operator()(const string& s)	{	return APHash(s.c_str());	} }; struct HashFunc5 {	size_t JSHash(const char *str)  	{  	if(!*str)	return 0;	register size_t hash = 1315423911;  	while (size_t ch = (size_t)*str++)  	{  	hash ^= ((hash << 5) + ch + (hash >> 2));  	}  	return hash;  	}	size_t operator()(const string& s)	{	return JSHash(s.c_str());	} }; template<class K = string, class __HashFunc1 = HashFunc1, class __HashFunc2 = HashFunc2, class __HashFunc3 = HashFunc3, class __HashFunc4 = HashFunc4, class __HashFunc5 = HashFunc5> class BloomFilter { public:	BloomFilter(size_t size)	:_bitMap(size)	,_capacity(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);	cout<<index1<<endl;	cout<<index2<<endl;	cout<<index3<<endl;	cout<<index4<<endl;	cout<<index5<<endl;	_bitMap.Set(index1%_capacity);	_bitMap.Set(index2%_capacity);	_bitMap.Set(index3%_capacity);	_bitMap.Set(index4%_capacity);	_bitMap.Set(index5%_capacity);	_v[index%_capacity]++;	}	/*ReSet()	{	if(_v[index1%_capacity] == 0)	return false;	else	--_v[index%_capacity];	}*/	bool Test(const K& key)	{	size_t index1 = __HashFunc1()(key);	if (!_bitMap.Test(index1%_capacity))	return false;	size_t index2 = __HashFunc2()(key);	if (!_bitMap.Test(index2%_capacity))	return false;	size_t index3 = __HashFunc3()(key);	if (!_bitMap.Test(index3%_capacity))	return false;	size_t index4 = __HashFunc4()(key);	if (!_bitMap.Test(index4%_capacity))	return false;	size_t index5 = __HashFunc5()(key);	if (!_bitMap.Test(index5%_capacity))	return false;	return true;	} protected:	BitMap _bitMap;	size_t _capacity;	//map<size_t, size_t> countMap;	/*vector<size_t> _v;*/ }; void Test1() {	BloomFilter<> bf(-1);	bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html");	bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528154.html");	bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528155.html");	bf.Set("http://www.cnblogs.com/-clq/archive/2012/05/31/2528156.html");	cout<<bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html")<<endl;	cout<<bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528154.html")<<endl;	cout<<bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528155.html")<<endl;	cout<<bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528156.html")<<endl;	cout<<bf.Test("http://www.cnblogs.com/-clq/archive/2012/05/31/2528157.html")<<endl; }

以上