算法–布隆过滤器(Bloom Filter)
问题
我有个网站,拥有很多访客,当有用户访问时,我想知道这个ip是不是第一次访问我的网站,很快我们能够想到用哈希表来记录用户的访问记录,这样我们就可以在O(1)的时间复杂度内得到结果。
但是,如果我们的网站被几亿人访问过呢?那么我们的哈希表将会很大,比如我们把ip用无符号整数来存储在哈希表中,一个ip就是4个字节,1亿个ip占用的内存就是 4 * 100000000 = 400000000Bytes = 380MB
。
看起来 380M 也还可以,比较机器的内存几个G还是没问题的,但是如果我们是 10 亿的数据量呢?要知道我们的ip地址可是有2^32 = 4GB
那么有没有可以节省空间的办法呢?
bitset
32位无符号int能表示最大值是4GB,我们用一个bitset来保持是否出现过这个ip,那么只需要 4GB/8 = 512MB
就可以表示所有ip了。
#include <bitset>
#include <arpa/inet.h>
#include <iostream>
using namespace std;
bitset<(1L<<32)> ipbitset;
bool hasip(const string& ip) {
int dwip;
if (inet_pton(AF_INET, ip.c_str(), &dwip) > 0) {
if (ipbitset.test(dwip) == false) {
ipbitset.set(dwip);
return false;
}
return true;
}
cerr << "invalid ip: " << ip << endl;
return false;
}
int main(int argc, char** argv) {
cout << boolalpha;
cout << "127.0.0.1\t" << hasip("127.0.0.1") << endl;
cout << "127.0.0.1\t" << hasip("127.0.0.1") << endl;
cout << "192.168.1.1\t" << hasip("192.168.1.1") << endl;
cout << "192.168.1.1\t" << hasip("192.168.1.1") << endl;
return 0;
}
但是,bitset也不是那么的完美,它有两个比较局限的地方:
1. 当样本分布极度不均匀的时候,bitset会造成很大空间上的浪费。举个例子,比如你有10个数,分别是1、2、3、4、5、6、7、8、99999999999;那么你不得不用99999999999个bit位去实现你的BitSet,而这个BitSet的中间绝大多数位置都是0,并且永远不会用到,这显然是极度不划算的。
2. 当元素不是整型的时候,bitset就不适用了。比如爬虫程序的url,如果想用bitset做去重的话,得先把url转换成int型,在转换的过程中难免某些url会计算相同的int值,于是bitset的准确性就会降低。
那么针对这两种情况有没有解决办法呢?
第一种分布不均匀的情况可以通过hash函数,将元素都映射到一个区域范围内,减少大段区间闲置造成的浪费,这很简单,取模就可以了,难的是取模之后保证不相同,即不发生hash冲突。
第二种情况,把字符串映射成整数是有必要的,那么唯一要做的就是保证我们的hash函数尽可能的减少冲突,一次不行我就多hash几次,hash还是容易碰撞的,那我就扩大数组的范围,使hash值尽可能的均匀分布,减少hash冲突的概率。基于这种思想,Bloom Filter就诞生了。
Bloom Filter
原理
BloomFiler又叫布隆过滤器,下面举例说明BlooFilter的实现原理:
比如你有10个Url,你完全可以创建一长度是100bit的数组,然后对url分别用5个不同的hash函数进行hash,得到5个hash后的值,这5个值尽可能的保证均匀分布在100个bit的范围内。然后把5个hash值对应的bit位都置为1,判断一个url是否已经存在时,一次看5个bit位是否为1就可以了,如果有任何一个不为1,那么说明这个url不存在。这里需要注意的是,如果对应的bit位值都为1,那么也不能肯定这个url一定存在,这个是BloomFilter的特点之一,稍后再说。
核心思想
BloomFilter的核心思想有两点:
1. 多个hash,增大随机性,减少hash碰撞的概率
2. 扩大数组范围,使hash值均匀分布,进一步减少hash碰撞的概率。
BloomFilter的准确性
尽管BloomFilter已经尽可能的减小hash碰撞的概率了,但是,并不能彻底消除,因此正如上面提到的:如果对应的bit位值都为1,那么也不能肯定这个url一定存在
也就是说,BloomFilter其实是存在一定的误判的,这个误判的概率显然和数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关,具体的计算公式,可以查阅相关论文,这里只给出结果:
Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,误判概率还是比较小的,空间利用率也很高。
BloomFilter的应用
- 黑名单。
比如邮件黑名单过滤器,判断邮件地址是否在黑名单中 - 排序(仅限于bitSet)。
仔细想想,其实BitSet在set(int value)的时候,“顺便”把value也给排序了。 - 网络爬虫。
判断某个URL是否已经被爬取过 - K-V系统快速判断某个key是否存在。
典型的例子有Hbase,Hbase的每个Region中都包含一个BloomFilter,用于在查询时快速判断某个key在该region中是否存在,如果不存在,直接返回,节省掉后续的查询。
修改自:https://blog.csdn.net/xinzhongtianxia/article/details/81294922