- 中文名布隆過濾粘秆，適用于排除某個值不在一個集合內(nèi)狮辽，本文不討論布隆過濾的缺陷
- 首先給出一組字符串集合烁巫，然后判斷某個字符串是否在這個集合中
char *httphead[] = {
"Uri=",
"Host=",
"Referer=",
"User-Agent=",
};
- 初始化篩選器淳衙，通過計算多個hash算法蘑秽，得出多個key值，然后在bit位中key值的地方置1箫攀，得出一個bloom篩選器
- 判斷字符串是否在篩選器中肠牲，對字符串進(jìn)行多次hash計算，同樣得出多個key值靴跛，然后獲取bit位中相應(yīng)key值的值缀雳，如果不是都為1， 那么字符串肯定不在集合中梢睛。但是反過來肥印，值都為1，只能說字符串可能再集合中绝葡，這就涉及到一個hash沖突竖独，誤識別率的問題，暫時不討論
- 字符串hash算法
- 具體實(shí)現(xiàn)
#define MAX_BIT_COUNT 1000
#define MAX_HTTPHEAD_NUM 32
#define MAX_HASHFUNC_NUM 8
unsigned char bits[MAX_BIT_COUNT] = {0};
typedef unsigned int (* hashfunc)(char *);
hashfunc func[] = {
SDBMHash,
RSHash,
JSHash,
PJWHash,
ELFHash,
BKDRHash,
DJBHash,
APHash
};
void add_to_bloomfilter(char *str)
{
int hashvalue = 0, i = 0;
for(i = 0 ; i < MAX_HASHFUNC_NUM; i++)
{
hashvalue = func[i](str) % (MAX_BIT_COUNT * 8);
bits[hashvalue/8] |= (0x01 << (hashvalue % 8));\
}
}
unsigned char judge_bloomfilter(char *str)
{
int hashvalue = 0, i = 0;
for (i = 0 ; i < MAX_HASHFUNC_NUM; i++)
{
hashvalue = func[i](str) % (MAX_BIT_COUNT * 8);
if ((bits[hashvalue/8] & (0x01 << (hashvalue % 8))) == 0)
{
break;
}
}
if (i == MAX_HASHFUNC_NUM)
{
return 1;
}
else
{
return 0;
}
}
int main(int argc, char **argv)
{
int i = 0;
for (i = 0; i < MAX_HTTPHEAD_NUM; i++)
{
add_to_bloomfilter(httphead[i]);
}
for (i = 0; i < MAX_HTTPHEAD_NUM; i++)
{
if (judge_bloomfilter(httphead[i]) > 0)
{
printf("%s hash been find\n", httphead[i]);
}
}
if (judge_bloomfilter("axjhfdsaew") > 0)
{
printf("%s hash been find\n", "aaaaaaa");
}
return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
