算法–布隆过滤器（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
