【数据结构】位图BitMap与布隆过滤器BloomFilter

??? 首先先看一下下面这个腾讯的面试题：

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

思路一：

??? 最容易想到的解法就是遍历所有的40多亿个整数，然后一个一个判断。但是这个需要花费的内存是多大呢？

????大家可以去算一下，这里我就直接给出结果为16G，是不是需要的空间很大啊。如果面试官给出限制条件，要你使用的空间少于多少，遍历的方法就行不通啦。

思路二：

????我们可以把一个整形再细分一下，一个int类型就可以编程32个位，每一位用0，1表示当前这个位置上是否存有值，同样是利用哈希存储的方法。只是这样存储的话就可以减少很多的空间了，例如上题使用的内存就可以从16G降到500M的内存。空间的使用率减少了不止一点。

????位图的实现

#ifndef?__BITMAP_H__
#define?__BITMAP_H__
#include?<vector>
#include?"Common.h"

class?BitMap
{
public:
????BitMap(size_t?size?=?0)
????????:_size(0)
????{
????????_a.resize((size>>5)+1);
????}
????
????//插入数据
????void?Set(size_t?x)
????{
????????size_t?index?=?x?>>?5;
????????size_t?num?=?x?%?32;
????????//如果当前位置不存在值，直接插入
????????if?(!(_a[index]?&?(1?<<?num)))//判断这个位上是不是等0的
????????{
????????????++_size;
????????????_a[index]?|=?(1?<<?num);//将当前位上的值置成1
????????}
????}

????void?Reset(size_t?x)
????{
????????size_t?index?=?x?>>?5;
????????size_t?num?=?x?%?32;
????????
????????//判断当前位上的值是不是等于1，等于1删除
????????if?(_a[index]?&?(1?<<?num))
????????{
????????????--_size;
????????????_a[index]?&=?~(1?<<?num);//将当前位置成0
????????}
????}

????bool?Test(size_t?x)
????{
????????size_t?index?=?x?>>?5;
????????size_t?num?=?x?%?32;
????????
????????//如果当前位等于1，那么存在
????????if?(_a[index]?&?(1?<<?num))
????????{
????????????return?true;
????????}

????????return?false;
????}

????void?Resize(size_t?size)
????{
????????_a.resize((size?>>?5)?+?1);
????}

????size_t?Size()
????{
????????return?_size;
????}

private:
????vector<size_t>?_a;
????size_t?_size;//位图上插入了多少值
};


void?Test()
{
????BitMap?bm(35);
????bm.Set(4);
????bm.Set(5);
????bm.Set(6);
????cout?<<?"is4Exist?->"?<<?bm.Test(4)?<<?endl;
????cout?<<"is5Exist?->"<<?bm.Test(5)?<<?endl;

????bm.Reset(5);
????cout?<<?"is4Exist?->"?<<?bm.Test(4)?<<?endl;
????cout?<<?"is5Exist?->"?<<?bm.Test(5)?<<?endl;
}

#endif?//__BITMAP_H__

布隆过滤器 Bloom Filter

原理

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

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

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

• 如果这些点有任何一个 0，则被检索元素一定不在；

• 如果都是 1，则被检索元素可能在。

????如果只是空洞的说这些原理的话，肯定大家都不知道布隆过滤器有什么用处。布隆过滤器对于单机来说可能用处不是很大，但对于分布式来说就比较有用了。

????如主从分布：一个数组过来，我想要知道他是不是在内存中，我们是不是需要一个一个去访问磁盘，判断数据是否存在。但是问题来了访问磁盘的速度是很慢的，所以效率会很低，如果使用布隆过滤器，我们就可以先去过滤器这个集合里面找一下对应的位置的数据是否存在。虽然布隆过滤器有他的缺陷，但是我们能够知道的是当前位置为0是肯定不存在的，如果都不存在，就不需要去访问了。

下面来讲一下布隆过滤器的缺陷：

????缺陷一：误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。所以我们用多个哈希表去 存储一个数据。那么问题又来了，我们是多用一些呢，还是少用一些。如果多用哈希表的话，如上面的题，一个哈希就需要500M，那么放的越多是不是越占内存啊。如果太少的话是不是误算率就高啊，所以取个适中的。下面我的实现是取了五个哈希表(没有什么根据，只是把思路展现出来一下，能够分析出取多少个，那都是大牛们弄出来的算法，我当前水平不够~)

????缺陷二：如果当前位置为0肯定不存在，但是为1不一定存在

布隆过滤器的实现：（用了素数表和5个哈希算法）

????一、5个哈希算法的实现

#ifndef?__COMMON_H__
#define?__COMMON_H__

size_t?GetPrimeSize(size_t?size)
{
????static?const?int?_PrimeSize?=?28;
????static?const?unsigned?long?_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?(size_t?i?=?0;?i?<?_PrimeSize;?i++)
????{
????????if?(_PrimeList[i]?>?size)
????????{
????????????return?_PrimeList[i];
????????}
????????if?(_PrimeList[_PrimeSize]?==?size)
????????????return?_PrimeList[_PrimeSize?-?1];
????}
????return?_PrimeList[_PrimeSize?-?1];
}


template<class?T>
struct?__HashFunc1
{
????size_t?BKDRHash(const?char*?str)
????{
????????register?size_t?hash?=?0;
????????while?(size_t?ch?=?(size_t)*str++)
????????{
????????????hash?=?hash?*?131?+?ch;???//?也可以乘以31、131、1313、13131、131313..??
????????}
????????return?hash;
????}

????size_t?operator()(const?T&?str)
????{
????????return?BKDRHash(str.c_str());
????}

};


template<class?T>
struct?__HashFunc2
{
????size_t?SDBMHash(const?char*?str)
????{
????????register?size_t?hash?=?0;
????????while?(size_t?ch?=?(size_t)*str++)
????????{
????????????hash?=?65599?*?hash?+?ch;
????????????//hash?=?(size_t)ch?+?(hash?<<?6)?+?(hash?<<?16)?-?hash;??
????????}
????????return?hash;
????}

????size_t?operator()(const?T&?str)
????{
????????return?SDBMHash(str.c_str());
????}

};


template<class?T>
struct?__HashFunc3
{
????size_t?RSHash(const?char?*str)
????{
????????register?size_t?hash?=?0;
????????size_t?magic?=?63689;
????????while?(size_t?ch?=?(size_t)*str++)
????????{
????????????hash?=?hash?*?magic?+?ch;
????????????magic?*=?378551;
????????}
????????return?hash;
????}

????size_t?operator()(const?T&?str)
????{
????????return?RSHash(str.c_str());
????}

};


template<class?T>
struct?__HashFunc4
{
????size_t?APHash(const?char?*str)
????{
????????register?size_t?hash?=?0;
????????size_t?ch;
????????for?(long?i?=?0;?ch?=?(size_t)*str++;?i++)
????????{
????????????if?((i?&?1)?==?0)
????????????{
????????????????hash?^=?((hash?<<?7)?^?ch?^?(hash?>>?3));
????????????}
????????????else
????????????{
????????????????hash?^=?(~((hash?<<?11)?^?ch?^?(hash?>>?5)));
????????????}
????????}
????????return?hash;
????}

????size_t?operator()(const?T&?str)
????{
????????return?APHash(str.c_str());
????}

};


template<class?T>
struct?__HashFunc5
{
????size_t?JSHash(const?char?*str)
????{
????????if?(!*str)????????//?这是由本人添加，以保证空字符串返回哈希值0??
????????????return?0;
????????register?size_t?hash?=?1315423911;
????????while?(size_t?ch?=?(size_t)*str++)
????????{
????????????hash?^=?((hash?<<?5)?+?ch?+?(hash?>>?2));
????????}
????????return?hash;
????}

????size_t?operator()(const?T&?str)
????{
????????return?JSHash(str.c_str());
????}

};






#endif?//__COMMON_H__

（编辑：ASP站长网）