问题引入
如果你用过网络爬虫你就会有体会，当你运用爬虫去获取一些网址时，倘若A网址中引用了B网址，B网址中引用了C网址，而C网址中又用到了A网址，这时候你的爬虫就会陷入在无限循环中出不来了。
因此我们便会设法将访问过的网址记录下来，每爬到一个新的网址时，去列表中看看这个网址是否已经被访问过了，以避免重复访问。很自然的一个思路便是开一个很大的数组，将每个网址都存下来。有些网址的长度又是很长的，那就假设每个网址用100byte的空间来存储。假设你有10亿个网址，那你占用的空间会达到90GB！并且查找速率也达到了O（n）级别。这样的开销显然不是我们期望的。
于是我们就会想，那能不能对于每个网址，通过某种方式映射到某个值，那么无论是查找效率，还是空间存储，都会显著的提升。因此我们就引入了布隆过滤器（bloom-filter）。
概念简介
所谓的布隆过滤器就是通过一个二进制向量以及一些列的随机（哈希）函数，来判断一个元素是否在集合中。具体来说，比如我们现在有长度为m的全0位串以及k个哈希函数。给定一个网址时，我们通过这k个函数计算就可以得到k个值，对这k个值模m后将位串的相应位置为1即可。那么对于新来的网址，我们通过hash函数映射去看对应的位置是否为全1。如果全为1，则说明这个号码之前出现过，否则便没有。
到这里你可能会察觉到有些问题，是的，当我们谈论一个用于查询的结构时，往往回考察其是否会有假阴性和假阳性。所谓的假阴性，就是查询结果是不在里面，但实际上是在里面。显然我们的布隆过滤器不会出现假阴性结果。而假阳性便是查询结果是告知在里面，但实际却不在其中。布隆过滤器便可能出现假阳性结果。但在实际的应用中，我们并不是要求其查询结果的准确率为百分之百，错误率在一定的范围内，我们便是可以接受了。
如何确定位串长度和hash函数个数
显然hash函数个数k的选取并不是越多越好，考虑极端情况，取了无穷多个hash函数，那么处理一个网址便会将所有bit位都置1了。当然也不是越少越好，个数太少非常容易产生冲突。因此k的选取需要相当的谨慎，这里给出hash函数k的选取最佳为k=ln(2*m/n),m为位串长度，n为预期目标个数。位串长度当然是越长产生假阳性概率越低，但较长的位串会有较大的空间开销，所以也要慎重衡量考虑。
至于具体的代码实现，这里就不介绍了。C++的STL库就提供了bitset的数据结构，可以方便程序员管理一系列的bit位。用bitset模拟01位串，将hash函数映射过来的相应为置为1便可。
典型hash函数
以下给出几个常用的hash函数，hash函数设计的要求便是尽量减少冲突，这些hash函数的设计都是经过学者反复试验和计算才得来的。
long hash0(string str)
{
int b = 378551;
int a = 63689;
long hash = 0;
for (int i = 0; i < str.length(); i++)
{
hash = hash * a + str[i];
a = a * b;
}
return hash;
}
long hash1(string str)
{
long hash = 1315423911;
for (int i = 0; i < str.length(); i++)
{
hash ^= ((hash << 5) + str[i] + (hash >> 2));
}
return hash;
}
long hash2(string str)
{
long seed = 131;
long hash = 0;
for (int i = 0; i < str.length(); i++)
{
hash = (hash*seed) + str[i];
}
return hash;
}
long hash3(string str)
{
long hash = 0;
for (int i = 0; i < str.length(); i++)
{
hash = str[i] + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
long hash4(string str)
{
long hash = 5381;
for (int i = 0; i < str.length(); i++)
{
hash = ((hash << 5) + hash) + str[i];
}
return hash;
}
long hash5(string str)
{
long hash = str.size();
for (int i = 0; i < str.length(); i++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ str[i];
}
return hash;
}
实际应用
垃圾邮件的鉴别、URL去重等
