前言
布隆过滤器 Bloom Filter在很多博客中的有提到，但是我希望在本篇博客中按照我的理解将Bloom Filter尽量简单的呈现出来。其实从人类起源开始，人类就在尝试利用语言来描述世界，而语言恰恰是人与人之间交流的重要工具，例如，A告诉B“苹果”，B立刻能够想象出苹果的形状、颜色、作用、苹果公司、乔布斯等信息。显然易见，通过传递简单的两个字，人与人之间传递了大量事先已知的信息。随着互联网的发展，计算机与计算机之间也需要通信，其实这个道理与人之间的通信有几分类似，只不过计算机与计算机之间是用数学的语言在交流。
那么我们就用数学的语言来举一个例子：下面有许多整数，请用汉字来描述这些数字
1，一
101，一百零一
5631388，五百六十三万一千三百八十八
4135722879431564769231343136422521533547654，（说实话，我不知道怎么用汉字来描述这个整数）
接下来，我们要来分析一下上述例子暴露出来的问题。
1）这是一个和计算机类似的系统吗？
是，整数如101，实际上是这个系统的输入值；而汉字如“一百一”是输出值。那么，人脑这时候就是这个系统，研究这个系统如何工作可以帮助我们构造出计算机的方法。
2）那么，人脑是如何工作的呢？
刚出生的小孩可以是通过死记硬背的方法来记住这样的对应关系，如同我们背诵九九乘法口诀一样。显然，我们不可能通过这样的方法计算所有可能存在的整数。长大之后，老师我教我们按照一定的规律去记忆，于是我们知道了下述规则：
首先，我们知道“个”，“十”，“百”，“千”，“万”，“亿”，通过组合，我们可以表述任意个位数到亿亿位数之间的整数。随着我们对数学的理解，我们知道这个描述整数的方法叫做十进制。
其次，我们发现有的大的整数其实我们不知道应该怎么描述，例如上述的第四个例子。但是仿佛这并没有对我们生活造成多大的影响。
综合上述，我们可以做出如下的概括。形容自然界中所有的整数，我们可以采用一个通用的方法，即十进制。这种通用方法是将整数映射到一组用来描述的数字组合，即{x0* 10^0, x1*10^1, ... xn*10^n}，且n趋紧无穷大。我们可以将每个进制看作一个维度，换句话说，我们可以用n个维度来描述任意的整数。不过后来我们发现了其实很多维度在生活并不会用到，于是我们做了简化，就有了十进制中的个（10^0）、十（10^1）、...、亿亿（10^8），大于等于10^9的整数基本就被遗弃了。
以此类推，在计算机的世界里，我们也可以通过类似的方法来描述数据。当然我们希望计算机中的应用不仅限于整数，而且还能推广到各种数据类型。我们通过定义维度来描述数据并且舍弃不重要的维度来简化模型。接下来就让我们来看看，Bloom Filter是如何处理问题的吧？
Bloom Filter的应用
问题描述
假设服务器A是一个反垃圾邮件服务器，A维护了一个可疑IP列表，列表中包含了大量的可疑的IP地址。服务器B是另一个反垃圾邮件服务器，B也维护了一个可疑IP列表，列表中包含了大量的可疑的IP地址。两台服务器只能通过互联网通信。有一天，服务器A需要确认自己的列表和服务器B的列表的相似度（即两者包含的相同的IP地址占所有IP地址的比例）。问题思路
我们可以借鉴前言中的思路，即用n个维度来描述这个IP地址列表，然后我们可以舍弃不重要的维度来减少数据大小。显然，这个方法会有一定的误差或错误，但是这种出错的概率可以从统计方法来降低。而且，统计结果--相似度在计算时间和空间开销小的情况下，损失一点精确度有何妨呢？为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x，第i个哈希函数映射的位置hi(x)就会被置为1（1≤i≤k）。注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。如下图所示，我们可以所有的元素xk映射到位数组中。而m位的位数组就可以作为描述所有元素的简化版。
在判断y是否属于这个集合时，我们对y应用k次哈希函数，如果所有hi(y)的位置都是1（1≤i≤k），那么我们就认为y是集合中的元素，否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合，或者刚好是一个false positive。
m的单位是bit，而n则是以元素个数为单位(准确的说是不同元素的个数，可以是字符串或者复制对象)。所以使用bloom filter内存上通常都是节省的。
其次，我们来看看什么时候会出错呢？会有多大的误差呢？
如果某个元素z，我们对z应用k次哈希函数，如果某一位不为1，则z一定不在原始S集合中（可以通过反证得出）。但是，如果所有位都为1，那么可能有两种情况：1)z是集合S中的元素;2）z是未知数据，并未在S中出现。（这便是由于缩小了维度造成的）
我们再来估计一下可能的错误率。假设哈希函数是完全随机的，那么某个哈希函数将某一位置1的概率是1/m。当集合S={x1, x2,…,xn}的所有元素都被k个哈希函数映射到m位的位数组中时，这个位数组中某一位还是0的概率是：
已知某一位是0的概率，则ρ的数学期望E(ρ)= p’，表示m位中有p‘*m位值为0。对于一个错误的元素z，满足的条件是k个哈希函数随机取得的对应位置都为1，因此错误的概率为：
n是原始集合的元素个数，m与k都是Bloom Filter中定义的值。通常p’大于0.5，1-p‘小于0.5，（1-p‘）^k随着k的增长错误率收敛是很快。例如，0.49^8只有0.003。简而言之，单个哈希函数错误率高并不可怕，随着哈希函数的增加，整体的错误率收敛非常快。从数学上可以证明要让错误率不超过?，m至少需要取到n的log2(1/?)1.44倍。
或许，有人会问这个方法和前言说的是一回事儿吗？我们可以通过实际的分析来解释。
依然是上述的问题，IP的取值是从0.0.0.0至255.255.255.255。为了方便理解，我们不将IP地址作为字符串处理。反之，我们将IP地址中每一位扩充成为三维数字，如1.2.3.4表示001.002.003.004，然后转换成整数001002003004。现在可以有的人会发现，那我们不是可以利用前言的方法来构造哈希函数吗？例如H1(x)=x%10，H2(x)=x%10^2。由于IP地址是完全随机出现的，利用这样的简单处理并不一定是最优的维度选择。对于这个例子，我们还可以利用素数来构造相互独立的哈希函数。例如H1(x)=x%2，H2(x)=x%3，H2(x)=x%5，H2(x)=x%7，然后我们可以根据实际的数据去掉多余的维度。
假设IP地址共计500万条，每条占32B，直接传输需要传输152.59MB。n=500万，如果按照错误率e=0.01计算，log2(1/e)1.44=9.6，m至少应该取到4800万（注意：单位是bit），m占用的空间只有5.72MB。考虑到哈希函数的定义也需要传输，但是显然也不会达到152.59MB的数据大小。当原始数据大小更大时，Bloom Filter的效果更明显。