介绍布隆过滤器特点和应用场景。
布隆过滤器
在内存有所限制的情况下（如上面的面试问题），快速判断一个元素是否在一个集合（容器）当中，除了用位图法，还可以使用布隆过滤器 。哈希表比较占用内存，位图法又不适用于数据少且最大值大的情况，布隆过滤器就是这两者的结合。
布隆过滤器特点：
1 布隆过滤器通过一个位数组+k个哈希函数构成。
2 布隆过滤器有一定错误率。布隆过滤器判断一个元素不在集合中，那么该元素一定不在集合中；布隆过滤器判断一个元素在集合中，那么该元素有可能在集合中，有可能不在，有个典型的应用场景就是过滤非法网站。
3 布隆过滤器的错误查找率与位数组大小以及哈希函数有关系，有相应的计算公式。
4 Bloom Filter过滤器默认只支持add增加和query查询操作，不支持delete删除操作。
增加一个元素：
1 经过k个哈希函数计算，得到bitmap位数组里面的一组位的序号；
2 把相应的位置成1；
搜索一个元素：
1 经过k个哈希函数计算，得到bitmap位数组里面的一组位的序号；
2 判断上面几个位置的值如果全是1，证明key可能存在；如果有1个0，则证明key不在bloom filter中。
Bloom filter能提供删除操作吗？
不能删除，因为某个位可能多个数公用，所以布隆过滤器不能删除某个元素。
布隆过滤器使用场景：
场景1：提示过滤一些非法的网站，或者钓鱼网站等。
比如我们用浏览器访问某个网站时候，浏览器先判断该网站是否合法，判断的方法就是布隆过滤器。
将所有怀疑有问题的网站的URL添加到布隆过滤器中，当用户要访问网站时候，查找当前访问的网站是否在黑名单中，通过布隆过滤器计算哈希值，在位数组中根据哈希表判断，如果存在（可能有误），会提示当前网站有风险，禁止访问；如果URL不存在，那么该网址一定是白名单上合法网站，直接访问。
场景2：redis缓存中的应用
比如购物网站，客户查询某个商品时候，就用到了布隆过滤器。
service层查找key，查找方法用布隆过滤器，现在redis缓存中查找（内存IO），再次从DB中查找（磁盘IO）；然后依次返回。
// 布隆过滤器
class BloomFilter
{
public:
BloomFilter(int bitSize = 1471)
:bitSize_(bitSize)
{
bitMap_.resize(bitSize_ / 32 + 1);
}
public:
void setBit(const char *str)
{
// 计算k组哈希函数的值
int idx1 = BKDRHash(str) % bitSize_;
int idx2 = RSHash(str) % bitSize_;
int idx3 = APHash(str) % bitSize_;
// 把相应的idx1 idx2 idx3 这个位全部置1
int index = 0;
int offset = 0;
index = idx1 / 32;
offset = idx1 % 32;
bitMap_[index] |= (1 << offset);
index = idx2 / 32;
offset = idx2 % 32;
bitMap_[index] |= (1 << offset);
index = idx3 / 32;
offset = idx3 % 32;
bitMap_[index] |= (1 << offset);
}
// 查询元素
bool getBit(const char *str)
{
// 计算k组哈希函数的值
int idx1 = BKDRHash(str) % bitSize_;
int idx2 = RSHash(str) % bitSize_;
int idx3 = APHash(str) % bitSize_;
int index = 0;
int offset = 0;
index = idx1 / 32;
offset = idx1 % 32;
if (0 == (bitMap_[index] & (1 << offset)))
{
return false;
}
index = idx2 / 32;
offset = idx2 % 32;
if (0 == (bitMap_[index] & (1 << offset)))
{
return false;
}
index = idx3 / 32;
offset = idx3 % 32;
if (0 == (bitMap_[index] & (1 << offset)))
{
return false;
}
}
private:
int bitSize_; // 位图长度
vector<int> bitMap_; // 位图数组
};
class BlackList
{
private:
BloomFilter blockList_;
public:
BlackList()
{
}
void add(string url)
{
blockList_.setBit(url.c_str());
}
bool query(string url)
{
return blockList_.getBit(url.c_str());
}
};
int main()
{
BlackList l1;
l1.add("www.baidu.com");
l1.add("www.360.com");
l1.add("www.tencent.com");
string url = "www.baidu.com";
cout << l1.query(url) << endl;
system("pause");
return 0;
}