哈希表的扩展--布隆过滤器_bu long guo l眉

布隆过滤器 Bloom Filter
在位图的基础上可以实现布隆过滤器
想了解位图的可以参考下面网址：
http://blog.csdn.net/adzn1/article/details/79511386

原理

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hashtable）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。

Bloom Filter 是一种空间效率很高的随机数据结构，Bloom filter 可以看做是对 bit-map 的扩展, 它的原理是：

当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了： •如果这些点有任何一个 0，则被检索元素一定不在；如果都是 1，则被检索元素很可能在。

优点

它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

代码实现：
BulongFilter.h

#pragma once
typedef  char* KeyType;
#include<stdio.h>
#include<stdlib.h>
#include"BitMap.h"
typedef size_t(*HASH_FUNC)(KeyType str);//这里使用一个函数指针将字符串进行转换
typedef struct BuLongFilter
{
    BitMap _bm;
    HASH_FUNC _HashFunc1;
    HASH_FUNC _HashFunc2;
    HASH_FUNC _HashFunc3;
}BuLongFilter; 

void BuLongInit(BuLongFilter*bf, size_t range);//初始化
void BuLongSet(BuLongFilter*bf, KeyType Key);//插值
int BuLongTest(BuLongFilter*bf, KeyType key);//测试
void BuLongDesTroy(BuLongFilter*bf);//销毁
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

BulongFilter.c

#include"BulongFilter.h"
static size_t BKDRHash(KeyType str)//哈希函数1
{
    unsigned int seed = 131; // 31 131 1313 13131 131313
    unsigned int hash = 0;
    while (*str)
    {
        hash = hash * seed + (*str++);
    }
    return (hash & 0x7FFFFFFF);
}

size_t DEKHash(KeyType str)//哈希函数2
{
    if (!*str)
    {// 这是由本人添加，以保证空字符串返回哈希值0  
        return 0;
    }
    register size_t hash = 1315423911;
    size_t ch;
    while (ch = (size_t)*str++)
    {
        hash = ((hash << 5) ^ (hash >> 27)) ^ ch;
    }
    return hash;
}

size_t FNVHash(KeyType str)//哈希函数3
{
    if (!*str)
    {// 这是由本人添加，以保证空字符串返回哈希值0  
        return 0;
    }


    register size_t hash = 2166136261;
    size_t ch;
    while (ch = (size_t)*str++)
    {
        hash *= 16777619;
        hash ^= ch;
    }
    return hash;
}
void BuLongInit(BuLongFilter*bf, size_t range)//初始化
{
    InitBitMap(&bf->_bm, range);
    bf->_HashFunc1 = BKDRHash;
    bf->_HashFunc2 = BKDRHash;
    bf->_HashFunc3 = FNVHash;
}

void BuLongSet(BuLongFilter*bf, KeyType key)//插入
{
    assert(bf);
    size_t range = bf->_bm._range;
    BitMapSet(&bf->_bm, bf->_HashFunc1(key) % range);//取模以防止越界，调用位图的插入
    BitMapSet(&bf->_bm, bf->_HashFunc2(key) % range);
    BitMapSet(&bf->_bm, bf->_HashFunc3(key) % range);
}
int BuLongTest(BuLongFilter*bf, KeyType key)
{
    assert(bf);
    if (BitMapTest(&bf->_bm, bf->_HashFunc1(key) % bf->_bm._range)==0)
        return 0;
    if (BitMapTest(&bf->_bm, bf->_HashFunc2(key) % bf->_bm._range)==0)
        return 0;
    if (BitMapTest(&bf->_bm, bf->_HashFunc3(key) % bf->_bm._range)==0)
        return 0;
    return -1;
}
void BuLongDesTroy(BuLongFilter*bf)//销毁
{
    free(&bf->_bm);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

test.c

#include"BulongFilter.h"
void test()
{
    BuLongFilter bf;
    BuLongInit(&bf, 10000);

    BuLongSet(&bf, "white");
    BuLongSet(&bf, "red");
    BuLongSet(&bf, "blue");
    BuLongSet(&bf, "water111111111111");



    printf("%d\n ", BuLongTest(&bf, "white"));
    printf("%d\n ", BuLongTest(&bf, "green"));
    printf("%d\n ", BuLongTest(&bf, "whi"));
    printf("%d\n ", BuLongTest(&bf, "blue"));
    printf("%d\n ", BuLongTest(&bf, "water111111111111"));
}
int main()
{
    test();
    system("pause");
    return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

哈希参考函数：
http://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html