Bloom Filter（布隆过滤器）主要用于判断某个元素是否属于集合内，但是这种判断不是一定正确的。
经典问题：
假设你有数量非常庞大的URL集合，现在给你一个新的URL，要你快速判断这个URL是否在上述的URL集合中。
解决这个问题比较原始的方法是：先用一个数组把所有URL存起来，然后再扫描这个数组，判断里面是否有元素与新的这个URL相同。这样做会耗费非常大的空间和时间，是非常不妥的一种做法。
另一种非常快速的方法就是使用布隆过滤器了。如果布隆过滤器说一个元素在某个集合内，那么这个元素是很有可能在这个集合内的，但不是百分之百在；相反，如果布隆过滤器说一个元素不在这个集合内，那么这个元素一定不在这个集合内。
原理：
布隆过滤器主要使用的是hash函数，并且是同时使用多个hash函数，以便减少hash冲突。
首先，假设有7个hash函数，分别是h1(), h2() ….h7()，这里hash函数的具体内容是不定的，看你具体的程序和应用来决定。然后有一个位数组bits，元素个数为m吧，初始化为0.
下面先说往集合里添加元素的过程：
给你一个元素e，你要把它通过布隆过滤器添加到某个集合里。
首先，分别用上面的7个hash函数对e取hash值，假设结果如下：
r1 = h1(e) = 5,
r2 = h2(e) = 6,
r3 = h3(e) = 1,
r4 = h4(e) = 7,
r5 = h5(e) = 6,
r6 = h6(e) = 10,
r7 = h7(e) = 9.
这里需要注意的是，这几个hash函数中有可能返回值是相同的（比如上面的r2和r5）。
根据上面的结果，把bits对应位置为1(重复只需置一次就可以了)：
bits[5] = 1
bits[6] = 1,
bits[1] = 1,
bits[7] = 1,
bits[10] = 1,
bits[9] = 1.
这就把e通过布隆过滤器加入到了集合中来。
现在假设又来一个元素e2，要添加到集合中来。假设用7个hash函数做hash得：
r1 = h1(e2) = 3,
r2 = h2(e2) = 1,
r3 = h3(e2) = 6,
r4 = h4(e2) = 14,
r5 = h5(e2) = 11,
r6 = h6(e2) = 13,
r7 = h7(e2) = 3.
再把对应bits的位置为1，
bits[3] = 1,
bits[1] = 1,
bits[6] = 1,
bits[14] = 1,
bits[11] = 1,
bits[13] = 1,
bits[3] = 1.
注意bits的长度m的大小，不要越过数组边界了。
经过上述两个元素的添加，bits变成下面这样：
bits[1] = 1,
bits[3] = 1,
bits[5] = 1,
bits[6] = 1,
bits[7] = 1,
bits[9] = 1,
bits[10] = 1,
bits[11] = 1,
bits[13] = 1,
bits[14] = 1,
其他都为0。
现在集合里面有e1和e2两个元素了。
现在要判断元素e3是否在这个集合内。
首先分别用上面的7个hash函数对e3求hash，结果假设如下：
r1 = h1(e3) = 3,
r2 = h2(e3) = 1,
r3 = h3(e3) = 6,
r4 = h4(e3) = 14,
r5 = h5(e3) = 11,
r6 = h6(e3) = 13,
r7 = h7(e3) = 3.
（很明显，这里的结果与e2的hash结果一样）
如果e3在集合内，那么上面结果对应的bits位要全都为1才行，，如果有一个为0，那么e3就不在集合内。很明显，bits对应的位都为1，所以我们可以说e3很有可能在集合内，但不是百分之百。
如果是这种情况，e3的所有hash值对应的bits都为1，但是e3不在集合内。假设此时hash值计算结果为：
r1 = h1(e3) = 3,
r2 = h2(e3) = 6,
r3 = h3(e3) = 7,
r4 = h4(e3) = 9,
r5 = h5(e3) = 11,
r6 = h6(e3) =13,
r7 = h7(e3) = 14,
此时虽然对应bits位都为1，但是由于e3的hash结果是由e1和e2混合而来的，所以此时e3是不存在集合中的。
相反，如果计算出所有的hash值，bits对应位中有为0 的，那么可以肯定地说这个元素一定不在集合内；因为如果在集合内的话，那么在用布隆过滤器添加元素时，就应该把这个元素所有hash值的bits对应位都置为了1.
BloomFilter的C++代码：
BloomFilter.h
//// BloomFilter.h// BloomFilter//// Created by 刘建安 on 4/19/15.// Copyright (c) 2015 刘建安. All rights reserved.//#ifndef BloomFilter_BloomFilter_h#define BloomFilter_BloomFilter_h#include "math.h"#include "memory.h"#include "BloomHash.h"using namespace std;class BloomFilter{private:bool bits[numOfBits];BloomHash hash[7]; //7个哈希函数public:BloomFilter(){memset(bits, false, sizeof(bits));int seeds[7] = {5, 7, 11, 13, 23, 29, 37}; //hash函数的种子for (int i = 0; i < 7; i++)hash[i].setSeed(seeds[i]);}//判断是否包含某个字符串bool isContain(string s){bool flag = true;for (int i = 0; i < 7; i++){int tmp = hash[i].hash(s);flag = flag & bits[tmp];}return flag;}//添加字符串void add(string s){for (int i = 0; i < 7; i++){int hasValue = hash[i].hash(s);bits[hasValue] = true;}}};#endif
BloomHash.h
//// BloomHash.h// BloomFilter//// Created by 刘建安 on 4/19/15.// Copyright (c) 2015 刘建安. All rights reserved.//#ifndef BloomFilter_BloomHash_h#define BloomFilter_BloomHash_h#include "string"using namespace std;#define numOfBits (1 << 14) //bits数组的长度class BloomHash{private:int seed;public:void setSeed(int _seed){seed = _seed;}//对一个字符串求哈希值int hash(string s){long long result = 0;long long length = s.size();for (int i = 0; i < length; i++){result = seed * result + int(s[i]);}return (numOfBits -1) & result; //这里记得要减去1，否则答案有错；&是为了保证数组不越界}};#endifmain.cpp//// main.cpp// BloomFilter//// Created by 刘建安 on 4/19/15.// Copyright (c) 2015 刘建安. All rights reserved.//#include <iostream>#include "BloomFilter.h"#include "string"using namespace std;int main(int argc, const char * argv[]) {// insert code here…std::cout << "Hello, World!\n";string s = "hello world";BloomFilter bf = BloomFilter(); //布隆过滤器bf.add(s);if (bf.isContain("helloworld")){cout << "yes" << endl;}elsecout << "no" << endl;return 0;}
如果爱，请深爱;如不爱，请离开。
