【数据结构】位图BitMap、布隆过滤器的算法实现

我们先给出之前我看过的腾讯公司的一道笔试题，引出位图BitMap。

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。

这个问题怎么解决呢？

1）将40亿数据保存起来（保存在数组、链表、树中），再和该数判断是否相等。

那我们思考一下需要多少内存：

2）借助位图BitMap解决。

位图（BitMap）

是用一个数组中的每个数据的每个二进制位表示一个数是否存在。1表示存在，0表示不存在。

相当于把数组分成很多块的空间，每一块是32个比特位。

原来32个比特位放一个数据，现在一个位就可以放一个数据。16GB/32=0.5GB=512MB。

位图的实现：

#ifndef__BITMAP_H__
#define__BITMAP_H__
#include<iostream>
usingnamespacestd;

#include<vector>

classBitMap
{
public:
BitMap(size_tsize=0)
:_size(0)
{
//_a开辟多一个空间，如size=36/32=1,需要两块空间才能放下
_a.resize((size>>5)+1);
}


voidSet(size_tx)
{
//size_tindex=x/32;
size_tindex=(x>>5);
size_tnum=x%32;

//if(!(_a[index]&(1<<num))表示该二进制位不存在，则该位二进制置成1
if(!(_a[index]&(1<<num)))
{
_a[index]|=(1<<num);
++_size;
}
}


voidReset(size_tx)
{
//size_tindex=x/32;
size_tindex=x>>5;
size_tnum=x%32;

//该位存在则将该位二进制置为0
if(_a[index]&(1<<num))
{
_a[index]&=~(1<<num);
--_size;
}
}


boolTest(size_tx)
{
//size_tindex=x/32;
size_tindex=x>>5;
size_tnum=x%32;
if(_a[index]&(1<<num))
{
returntrue;
}
returnfalse;
}


voidResize(size_tsize)
{
_a.resize(size);
}
private:
vector<size_t>_a;
size_t_size;
};

#endif//__BITMAP_H__

布隆过滤器（BloomFilter）

它是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器可以用于检索一个元素是否在一个集合中。那我们可以利用哈希函数计算出它具体的存放位置。

它的优点是空间效率和查询时间都远远超过一般的算法，将这40亿的数据内存由16GB变成500MB,可见其强大。

缺点是有一定的误识别率、不便于删除。布隆过滤器会出现：检测存在，而实际中却不存在。而不会出现：实际中不存在，而检测存在。

代码实现（仿函数实现，选取5个位图）：

#define_CRT_SECURE_NO_WARNINGS1
#ifndef__COMMON__
#define__COMMON__

size_t_GetnewSize(size_t_size)
{
staticconstint_PrimeSize=28;
staticconstunsignedlong_PrimeList[_PrimeSize]=
{
53ul,97ul,193ul,389ul,769ul,1543ul,3079ul,6151ul,12289ul,24593ul,49157ul,98317ul,196613ul,393241ul,786433ul,1572869ul,3145739ul,6291469ul,12582917ul,25165843ul,50331653ul,100663319ul,201326611ul,402653189ul,805306457ul,1610612741ul,3221225473ul,4294967291ul
};

for(inti=0;i<_PrimeSize;i++)
{
if(_PrimeList[i]>_size)
{
return_PrimeList[i];
}
}
return_PrimeList[_PrimeSize-1];
}


template<classT>
struct__HashFunc1
{
size_tBKDRHash(constchar*str)
{
registersize_thash=0;
while(size_tch=(size_t)*str++)
{
hash=hash*131+ch;//也可以乘以31、131、1313、13131、131313..

}
returnhash;
}

size_toperator()(constT&key)
{
returnBKDRHash(key.c_str());
}
};

template<classT>
struct__HashFunc2
{
size_tSDBMHash(constchar*str)
{
registersize_thash=0;
while(size_tch=(size_t)*str++)
{
hash=65599*hash+ch;
//hash=(size_t)ch+(hash<<6)+(hash<<16)-hash;
}
returnhash;
}

size_toperator()(constT&key)
{
returnSDBMHash(key.c_str());
}
};


template<classT>
struct__HashFunc3
{
size_tRSHash(constchar*str)
{
registersize_thash=0;
size_tmagic=63689;
while(size_tch=(size_t)*str++)
{
hash=hash*magic+ch;
magic*=378551;
}
returnhash;
}

size_toperator()(constT&key)
{
returnRSHash(key.c_str());
}
};


template<classT>
struct__HashFunc4
{
size_tJSHash(constchar*str)
{
if(!*str)//这是由本人添加，以保证空字符串返回哈希值0
return0;
registersize_thash=1315423911;
while(size_tch=(size_t)*str++)
{
hash^=((hash<<5)+ch+(hash>>2));
}
returnhash;
}

size_toperator()(constT&key)
{
returnJSHash(key.c_str());
}
};


template<classT>
struct__HashFunc5
{
size_tDEKHash(constchar*str)
{
if(!*str)//这是由本人添加，以保证空字符串返回哈希值0
return0;
registersize_thash=1315423911;
while(size_tch=(size_t)*str++)
{
hash=((hash<<5)^(hash>>27))^ch;
}
returnhash;
}

size_toperator()(constT&key)
{
returnDEKHash(key.c_str());
}
};

#endif//__COMMON__

布隆过滤器代码实现（借助素数表获取下一个素数，选取合适的容量--》hash函数）：：

#define_CRT_SECURE_NO_WARNINGS1
#include<iostream>
usingnamespacestd;
#include<string>

#include"Common.h"
#include"BitMap.h"

template<classT=string,classHashFunc1=__HashFunc1<T>,classHashFunc2=__HashFunc2<T>,classHashFunc3=__HashFunc3<T>,classHashFunc4=__HashFunc4<T>,classHashFunc5=__HashFunc5<T>>
classBloomFilter
{
public:

BloomFilter(size_tcapacity=0)
{
_capacity=_GetnewSize(capacity);
_bm.Resize(capacity);
}


voidSet(constT&key)
{
size_tindex1=HashFunc1()(key);
size_tindex2=HashFunc2()(key);
size_tindex3=HashFunc3()(key);
size_tindex4=HashFunc4()(key);
size_tindex5=HashFunc5()(key);
_bm.Set(index1%_capacity);
_bm.Set(index2%_capacity);
_bm.Set(index3%_capacity);
_bm.Set(index4%_capacity);
_bm.Set(index5%_capacity);

}


boolTest(constT&key)
{
size_tindex1=HashFunc1()(key);
if(!(_bm.Test(index1%_capacity)))
{
returnfalse;
}

size_tindex2=HashFunc2()(key);
if(!(_bm.Test(index2%_capacity)))
{
returnfalse;
}

size_tindex3=HashFunc3()(key);
if(!(_bm.Test(index3%_capacity)))
{
returnfalse;
}

size_tindex4=HashFunc4()(key);
if(!(_bm.Test(index4%_capacity)))
{
returnfalse;
}

size_tindex5=HashFunc5()(key);
if(!(_bm.Test(index5%_capacity)))
{
returnfalse;
}

returntrue;
}
private:
BitMap_bm;
size_t_capacity;//布隆过滤器的容量
};



voidTestBloomFilter()
{
BloomFilter<>bf(100);
bf.Set("JustDoIT!");
bf.Set("布隆过滤器");
bf.Set("https://mail.google.com/mail/#inbox");


cout<<"Isexist?:"<<bf.Test("测试工程师")<<endl;
cout<<"Isexist?:"<<bf.Test("开发工程师")<<endl;
cout<<"Isexist?:"<<bf.Test("IT")<<endl;
cout<<"Isexist?:"<<bf.Test("布隆过滤器")<<endl;
cout<<"Isexist?:"<<bf.Test("BloomFilter")<<endl;
cout<<"Isexist?:"<<bf.Test("https://mail.google.com/mail/#inbox")<<endl;
cout<<"Isexist?:"<<bf.Test("https://mail.google.com/mail/#inbox222221")<<endl;

}


intmain()
{
TestBloomFilter();
system("pause");
return0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!