#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; }
以上
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。