欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

哈希扩展——布隆过滤器

程序员文章站 2024-03-15 21:56:18
...

一、基本原理:

     对于原理来说很简单,位数组+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;
}

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