原文链接:http://blog.csdn.net/qq_38646470/article/details/79431659
1.概念：
如果想判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。
它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率（假正例False positives，即Bloom Filter报告某一元素存在于某集合中，但是实际上该元素并不在集合中）和删除困难，但是没有识别错误的情形（即假反例False negatives，如果某个元素确实没有在该集合中，那么Bloom Filter 是不会报告该元素存在于集合中的，所以不会漏报）。
2.实现原理：
直观的说，bloom算法类似一个hash set，用来判断某个元素（key）是否在某个集合中。和一般的hash set不同的是，这个算法无需存储key的值，对于每个key，只需要k个比特位，每个存储一个标志，用来判断key是否在集合中。
算法：
1）. 首先需要k个hash函数，每个函数可以把key散列成为1个整数
2）. 初始化时，需要一个长度为range比特的数组，每个比特位初始化为0
3）. 某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1
4）. 判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中。
3.代码实现：
采用3个hash函数计算散列值。
布隆结构设计：

typedef char* KeyType;

typedef size_t(*HASH_FUNC)(KeyType str);

typedef struct BloomFilter 
{
    BitMap _bm;
    HASH_FUNC _Hashfunc1;
    HASH_FUNC _Hashfunc2;
    HASH_FUNC _Hashfunc3;
}BloomFilter;

hash函数：

static size_t BKDRHash(KeyType str)
{
    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)  
{  
    if(!*str)        // 这是由本人添加，以保证空字符串返回哈希值0  
        return 0;  
    register size_t hash = 1315423911;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash = ((hash << 5) ^ (hash >> 27)) ^ ch;  
    }  
    return hash;  
}  

size_t FNVHash(KeyType str)  
{  
    if(!*str)   // 这是由本人添加，以保证空字符串返回哈希值0  
        return 0;  
    register size_t hash = 2166136261;  
    while (size_t ch = (size_t)*str++)  
    {  
        hash *= 16777619;  
        hash ^= ch;  
    }  
    return hash;  
}  

bloom算法实现函数:

void BloomFilterInit(BloomFilter *bf,size_t range) //初始化
{
    BitMapInit(&bf->_bm,range);
    bf->_Hashfunc1 = BKDRHash;
    bf->_Hashfunc2 = FNVHash;
    bf->_Hashfunc3 = DEKHash;
}

void BloomFilterSet(BloomFilter *bf,KeyType key)//标记相应位
{
    assert(bf);
    BitMapSet(&bf->_bm,bf->_Hashfunc1(key)%bf->_bm._range);
    BitMapSet(&bf->_bm,bf->_Hashfunc2(key)%bf->_bm._range);
    BitMapSet(&bf->_bm,bf->_Hashfunc3(key)%bf->_bm._range);
}

int BloomFilterTest(BloomFilter *bf,KeyType key)
{
    assert(bf);
    if (BitMapTest(&bf->_bm,bf->_Hashfunc1(key)%bf->_bm._range))
        return -1;
    if (BitMapTest(&bf->_bm,bf->_Hashfunc2(key)%bf->_bm._range))
        return -1;
    if (BitMapTest(&bf->_bm,bf->_Hashfunc3(key)%bf->_bm._range))
        return -1;

    return 0;
}

void BloomFilterDestory(BloomFilter *bf) //销毁
{
    BitMapDestory(&bf->_bm);
}

算法测试案例及运行结果：

void TestBlooomFilter()
{
    BloomFilter bf;
    BloomFilterInit(&bf,-1);
    BloomFilterSet(&bf,"123.5.3.6");
    BloomFilterSet(&bf,"123.5.3.8");
    BloomFilterSet(&bf,"123.5.3.6");
    BloomFilterSet(&bf,"123.5.3.7");
    BloomFilterSet(&bf,"123.5.3.4");
    BloomFilterSet(&bf,"123.5.3.6");
    BloomFilterSet(&bf,"123.5.3.8");
    BloomFilterSet(&bf,"123.5.3.8");
    BloomFilterSet(&bf,"123.5.3.6");

    printf("ip is exist? %d\n",BloomFilterTest(&bf,"123.5.3.6"));
    pr