【C++从小白到大牛】布隆过滤器

可涵不会debug 2024-08-25 08:35:01 阅读 59

布隆过滤器的提出

布隆过滤器概念

布隆过滤器的原理:

布隆过滤器的运作的总体过程:

布隆过滤器的插入

原码

布隆过滤器的查找

布隆过滤器删除

关于布隆过滤器的面试题:

1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

思路:

如何进行哈希切分呢?

2、如何扩展BloomFilter使得它支持删除元素的操作?

3、给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?

思路:

解析:

布隆过滤器优点:

布隆过滤器的缺点:

总结:

布隆过滤器的提出

上一篇文章我们已经学习了位图的应用,但是位图一般只能处理整形,如果内容编号是字符串,就无法处理了。而我们又知道如果只用哈希表存储用户记录,缺点就是浪费空间。但是我们将哈希表和位图结合起来呢,就是我们的布隆过滤器!

布隆过滤器概念

布隆过滤器是由布隆(Burton Howard Bloom)在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构,特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存

在”,它是用多个哈希函数,将一个数据映射到位图结构中。此种方式不仅可以提升查询效率,也可以节省大量的内存空间。

布隆过滤器的原理:

布隆过滤器是一个 bit 向量或者说 bit 数组,如果我们要映射一个值到布隆过滤器中,我们需要使用多个不同的哈希函数生成多个哈希值,并对每个生成的哈希值指向的 bit 位置 1,用多个不同的哈希函数生成多个哈希值,这句话是核心!

布隆过滤器为什么可以告诉你某样东西一定不存在或者可能存在 ?

现在我们如果想查询 “dianping” 这个值是否存在,哈希函数返回了 1、5、8三个值,结果我们发现 5 这个 bit 位上的值为 0,说明没有任何一个值映射到这个 bit 位上,因此我们可以很确定地说 “dianping” 这个值不存在。而当我们需要查询 “baidu” 这个值是否存在的话,那么哈希函数必然会返回 1、4、7,然后我们检查发现这三个 bit 位上的值均为 1,那么我们可以说 “baidu” 存在了么?答案是不可以,只能是 “baidu” 这个值可能存在。

这是为什么呢?答案很简单,因为随着增加的值越来越多,被置为 1 的 bit 位也会越来越多,这样某个值 “taobao” 即使没有被存储过,但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ,那么程序还是会判断 “taobao” 这个值存在!

布隆过滤器的运作的总体过程:

字符串(通过哈希函数)——>返回整形——>映射存储的位置

谁有误判?

在:有误判的可能(本来不在,映射位置冲突了,误判成在了)

不在:准确无误的

布隆可以多映射几个位,降低冲突的概率。

布隆过滤器的插入

注意这里的红框框部分

这里的Hash()就是实例化一个临时对象,然后调用operator()求key hash之后的值,这里就是匿名对象的应用,对象访问类型里面的仿函数直接()就行,不用加上.操作符

Hash1()是为了生成临时对象Hash1()()是用生成的临时对象调用仿函数

原码

<code>struct HashFuncBKDR

{

// BKDR

size_t operator()(const string& s)

{

size_t hash = 0;

for (auto ch : s)

{

hash *= 131;

hash += ch;

}

return hash;

}

};

struct HashFuncAP

{

// AP

size_t operator()(const string& s)

{

size_t hash = 0;

for (size_t i = 0; i < s.size(); i++)

{

if ((i & 1) == 0) // 偶数位字符

{

hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));

}

else // 奇数位字符

{

hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));

}

}

return hash;

}

};

struct HashFuncDJB

{

// DJB

size_t operator()(const string& s)

{

size_t hash = 5381;

for (auto ch : s)

{

hash = hash * 33 ^ ch;

}

return hash;

}

};

template<size_t N,

class K = string,

class Hash1 = HashFuncBKDR,

class Hash2 = HashFuncAP,

class Hash3 = HashFuncDJB>

class BloomFilter

{

public:

void Set(const K& key)

{

size_t hash1 = Hash1()(key) % M;

size_t hash2 = Hash2()(key) % M;

size_t hash3 = Hash3()(key) % M;

_bs->set(hash1);

_bs->set(hash2);

_bs->set(hash3);

}

bool Test(const K& key)

{

size_t hash1 = Hash1()(key) % M;

if (_bs->test(hash1) == false)

return false;

size_t hash2 = Hash2()(key) % M;

if (_bs->test(hash2) == false)

return false;

size_t hash3 = Hash3()(key) % M;

if (_bs->test(hash3) == false)

return false;

return true; // 存在误判(有可能3个位都是跟别人冲突的,所以误判)

}

private:

static const size_t M = 10 * N;

//bit::bitset<M> _bs;

std::bitset<M>* _bs = new std::bitset<M>;

};

布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找:分别计算每个哈希值对应的比特位置存储的是否零,只要有一个为零,代表该元素一定不在哈希表中,否则可能在哈希表中。

注意:布隆过滤器如果说某个元素不存在时,该元素一定不存在,如果该元素存在时,该元素可能存在,因为有些哈希函数存在一定的误判。

比如:在布隆过滤器中查找"alibaba"时,假设3个哈希函数计算的哈希值为:1、3、7,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实该元素是不存在的。

布隆过滤器删除

布隆过滤器不能直接支持删除工作,因为在删除一个元素时,可能会影响其他元素。

比如:删除上图中"tencent"元素,如果直接将该元素所对应的二进制比特位置0,“baidu”元素也被删除了,因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠

关于布隆过滤器的面试题:

1. 给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法

我们首先要预估一下100亿个query,也就是字符串会占多少空间

假设一个字符串50字节,而我们又知道1G 约等于 10字节,所以大概会占500个G

近似算法就是利用布隆器过滤,因为可能存在误判,所以就是近似算法。

这里重点讲解一下精确算法——哈希切分

首先将磁盘分成1000份,为什么不是分成500份呢?一共500个G,正好每个文件占1G,注意我们这里是哈希切分,而不是普通的切分,哈希切分出来的文件大小是不确定的,并不是均分的,因此有可能冲突比较多会超过1G,因此切分成1000份,基本不会超出范围。

思路:

我们直接依次将数据进行哈希切分到这1000*2个文件中这些数据都是存放在磁盘当中,所以不受1G内存的限制接着我们依次取出一份A0,和B0放入内存中进行找交集的操作因为分了1000份,所以此时的A0和B0基本不会超出内存1G的限制

如何进行哈希切分呢?

依次读取每一个query,i = HashFunc(query) % 1000,这个query就放入Ai文件;

同理,依次读取每一个query,i = HashFunc(query) % 1000,这个query就放入Bi文件;

注意这里的平均切找交集是N^2,而哈希切找交集是N。

原因:因为平均切出来的A0文件要分别与B0,B1……B999找交集,但是我们的哈希切只需要A0和B0,A1和B1进行单对单的找交集,因为A和B相同的query一定会进入编号相同的Ai和Bi小文件

如何找交集呢?

Ai 的 query放在 set<string> seta, Bid query放在 set<string> setb,seta和setb找交集即可

Ai和Bi文件想象桶一样,重复和冲突的query都是进入相同的桶,某个文件太大,有两种可能,第一:相同的太多,这种读出来插入set就会去重,不会影响;第二:冲突的太多,读出来set时会抛异常,需要二次处理,再换哈希函数进行二次哈希切分

2、如何扩展BloomFilter使得它支持删除元素的操作?

每个位置改成多个位的引用计数就可以支持。比如一个映射位置给8个bit标记,但是这样空间消耗就大了

3、给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?与上题条件相同,如何找到top K的IP?

思路:

这一道题普通切分根本行不通,因为可能每个小文件都可能存在相同的IP,因此这题必须使用哈希切分!

解析:

依次读取每个IP,i = HashFunc(ip) % 100,每个IP就进入Ai小文件。那么相同的IP就进入相同的小文件。每个小文件里面要么存放相同的IP,要么存放冲突的IP。

依次使用map<string, int> countMap,统计出每个文件IP出现的次数(如果map抛异常爆了,那么说明冲突很多,小文件很大,就换哈希函数,二次切分处理)

布隆过滤器优点:

 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数,一般比较小),与数据量大小无关 布隆过滤器不需要存储元素本身,在某些对保密要求比较严格的场合有很大优势 在能够承受一定的误判时,布隆过滤器比其他数据结构有这很大的空间优势

布隆过滤器的缺点:

有误判率,即存在假阳性(False Position),即不能准确判断元素是否在集合中(补救方法:再建立一个白名单,存储可能会误判的数据) 不能获取元素本身. 一般情况下不能从布隆过滤器中删除元素 如果采用计数方式删除,可能会存在空间消耗过大的问题

总结:

海量数据问题特征:数据量大,内存存不下

总体思路:

先考虑具有特点的数据结构能否解决?比如:位图、堆、布隆过滤器等等大事化小思路。哈希切分(不能平均切分)切小以后,放入内存中能处理



声明

本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。