ブロンフィルタ:実装コード
2666 ワード
#pragma once
#include
#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 <> 3));
}
else
{
hash ^= (~((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 <> 2));
}
return hash;
}
size_t operator()(const string& s)
{
return JSHash(s.c_str());
}
};
template
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< countMap;
/*vector _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<
以上
本文は“卵を残す君”のブログから出て、転載して作者と連絡してください!