算法–布隆过滤器(Bloom Filter)

作者: veaxen 分类: 数据结构与算法 发布时间: 2019-05-27 14:51

问题

我有个网站,拥有很多访客,当有用户访问时,我想知道这个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的特点之一,稍后再说。

blob.jpg

核心思想

BloomFilter的核心思想有两点:
1. 多个hash,增大随机性,减少hash碰撞的概率
2. 扩大数组范围,使hash值均匀分布,进一步减少hash碰撞的概率。

BloomFilter的准确性

尽管BloomFilter已经尽可能的减小hash碰撞的概率了,但是,并不能彻底消除,因此正如上面提到的:如果对应的bit位值都为1,那么也不能肯定这个url一定存在
也就是说,BloomFilter其实是存在一定的误判的,这个误判的概率显然和数组的大小以及hash函数的个数以及每个hash函数本身的好坏有关,具体的计算公式,可以查阅相关论文,这里只给出结果:
Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,误判概率还是比较小的,空间利用率也很高。

BloomFilter的应用

  1. 黑名单。
    比如邮件黑名单过滤器,判断邮件地址是否在黑名单中
  2. 排序(仅限于bitSet)。
    仔细想想,其实BitSet在set(int value)的时候,“顺便”把value也给排序了。
  3. 网络爬虫。
    判断某个URL是否已经被爬取过
  4. K-V系统快速判断某个key是否存在。
    典型的例子有Hbase,Hbase的每个Region中都包含一个BloomFilter,用于在查询时快速判断某个key在该region中是否存在,如果不存在,直接返回,节省掉后续的查询。

修改自:https://blog.csdn.net/xinzhongtianxia/article/details/81294922

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据