哈希扩展——布隆过滤器

一、基本原理：

     对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，但是这个过程并不能保证查找的结果是100%正确的。

二、要点：

1. 删除
        不支持删除一个已经插入的关键字，因为该关键字对应的位可能会牵动到其他的关键字。所以一个简单的改进就是用一个counter数组代替位数组，就可以支持删除了。
2. 误判
        Bloom Filter是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。但是这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合。因此，Bloom Filter不适合那些“零错误”的应用场合，而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

三、代码实现：

• BloomFilter.h

#ifndef __BLOOMFILTER_H__
#define __BLOOMFILTER_H__

#include "Bitmap.h"

typedef const char* BFKeyType;

typedef struct BloomFilter
{
    BitMap _bm;
}BloomFilter;

void BloomFilterInit(BloomFilter* bf, size_t range);
void BloomFilterSet(BloomFilter* bf, BFKeyType key);
int BloomFilterTest(BloomFilter* bf, BFKeyType key);
void BloomFilterDestory(BloomFilter* bf);

#endif __BLOOMFILTER_H__

• BloomFilter.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "BloomFilter.h"

//初始化
void BloomFilterInit(BloomFilter* bf, size_t range)
{
    assert(bf);
    BitMapInit(&(bf->_bm), range*5);
}

//字符串哈希算法
size_t BFHashFunc1(BFKeyType str)
{
    register size_t hash = 0;
    while (*str)
    {
        hash = hash * 131 + (*str++);
    }
    return hash;
}

size_t BFHashFunc2(BFKeyType str)
{
    register size_t hash = 0;
    size_t magic = 63689;
    while (*str)
    {
        hash = hash * magic + (*str++);
        magic *= 378551;
    }
    return hash;
}

size_t BFHashFunc3(BFKeyType str)
{
    register size_t hash = 0;
    while (*str)
    {
        hash = 65599 * hash + (*str++);
    }
    return hash;
}

//将x所在的位置置为1
void BloomFilterSet(BloomFilter* bf, BFKeyType key)
{
    assert(bf);
    size_t hash1 = BFHashFunc1(key) % bf->_bm._range;
    BitMapSet(&bf->_bm, hash1);

    size_t hash2 = BFHashFunc2(key) % bf->_bm._range;
    BitMapSet(&bf->_bm, hash2);

    size_t hash3 = BFHashFunc3(key) % bf->_bm._range;
    BitMapSet(&bf->_bm, hash3);
}

//检测x是否存在
int BloomFilterTest(BloomFilter* bf, BFKeyType key)
{
    assert(bf);
    size_t hash1 = BFHashFunc1(key) % bf->_bm._range;
    if (BitMapTest(&bf->_bm, hash1) == 0)
    {
        return 0;
    }

    size_t hash2 = BFHashFunc2(key) % bf->_bm._range;
    if (BitMapTest(&bf->_bm, hash2) == 0)
    {
        return 0;
    }

    size_t hash3 = BFHashFunc3(key) % bf->_bm._range;
    if (BitMapTest(&bf->_bm, hash3) == 0)
    {
        return 0;
    }
    return 1;
}

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

• Test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "BloomFilter.h"

int main()
{
    BloomFilter bf;
    BloomFilterInit(&bf, 10);

    BloomFilterSet(&bf, "a");
    BloomFilterSet(&bf, "ab");
    BloomFilterSet(&bf, "abc");

    printf("%d\n", BloomFilterTest(&bf, "a"));
    printf("%d\n", BloomFilterTest(&bf, "ab"));
    printf("%d\n", BloomFilterTest(&bf, "abc"));
    printf("%d\n", BloomFilterTest(&bf, "abcd"));

    BloomFilterDestory(&bf);

    system("pause");
    return 0;
}

部分头文件和函数引用请参照哈希变形—位图