Bloom filter 是由 Howard Bloom 在 1970 年提出的二进制向量数据结构，它具有很好的空间和时间效率，被用来检测一个元素是不是集合中的一个成员。如果检测结果为是， 该元素不一定在集合中；但如果检测结果为否，该元素一定不在集合中。因此Bloom filter具有100%的召回率。这样每个检测请求返回有“在集合内（可能错误）”和“不在集合内（绝对不 在集合内）”两种情况，可见 Bloom filter 是牺牲了正确率和时间以节省空间。
Bloom-Filter算法的核心思想就是利用多个不同的Hash函数来解决“冲突”。
计算某元素x是否在一个集合中，首先能想到的方法就是将所有的已知元素保存起来构成一个集合R，然后用元素x跟这些R中的元素一一比较来判断是否存在于集合R中；我们可以采用链表等数据 结构来实现。但是，随着集合R中元素的增加，其占用的内存将越来越大。试想，如果有几千万个不同网页需要下载，所需的内存将足以占用掉整个进程的内存地址空间。即使用MD5，UUID这些 方法将URL转成固定的短小的字符串，内存占用也是相当巨大的。
于是，我们会想到用Hash table的数据结构，运用一个足够好的Hash函数将一个URL映射到二进制位数组（位图数组）中的某一位。如果该位已经被置为1，那么表示该URL已经存在。
Hash存在一个冲突（碰撞）的问题，用同一个Hash得到的两个URL的值有可能相同。为了减少冲突，我们可以多引入几个Hash，如果通过其中的一个Hash值我们得出某元素不在集合中，那么该 元素肯定不在集合中。只有在所有的Hash函数告诉我们该元素在集合中时，才能确定该元素存在于集合中。这便是Bloom-Filter的基本思想。
原理要点：一是位数组， 二是k个独立hash函数。
1.位数组
假设Bloom Filter使用一个m比特的数组来保存信息，初始状态时，Bloom Filter是一个包含m位的位数组，每一位都置为0，即BF整个数组的元素都设置为0:
2.添加元素，k个独立hash函数
为了表达S={x1, x2,…,xn}这样一个n个元素的集合，Bloom Filter使用k个相互独立的哈希函数（Hash Function），它们分别将集合中的每个元素映射到{1,…,m}的范围中。
当我们往Bloom Filter中增加任意一个元素x时候，我们使用k个哈希函数得到k个哈希值，然后将数组中对应的比特位设置为1。即第i（1≤i≤k）个哈希函数映射的位置hashi(x)就会被置为1。
注意，如果一个位置多次被置为1，那么只有第一次会起作用，后面几次将没有任何效果。在下图中，k=3，且有两个哈希函数选中同一个位置（从左边数第五位，即第二个"1"处）。
3.判断元素是否存在集合
在判断y是否属于这个集合时，我们只需要对y使用k个哈希函数得到k个哈希值，如果所有hashi(y)的位置都是1（1≤i≤k），即k个位置都被设置为1了，那么我们就认为y是集合中的元素，
否则就认为y不是集合中的元素。下图中y1就不是集合中的元素（因为y1有一处指向了"0"位）。y2或者属于这个集合，或者刚好是一个false positive。
显然这 个判断并不保证查找的结果是100%正确的。
Bloom Filter的缺点
1)
Bloom Filter无法从Bloom Filter集合中删除一个元素。因为该元素对应的位会牵动到其他的元素。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组， 就可以支持删除了。 此外，Bloom Filter的hash函数选择会影响算法的效果。
2)
这里m与n的单位不同，m是bit为单位，而n则是以元素个数为单位(准确的说是不同元素的个数)。通常单个元素的长度都是有很多bit的。所以使用bloom filter内存上通常都是节省的。
一般BF可以与一些key-value的数据库一起使用，来加快查询。由于BF所用的空间非常小，所有BF可以常驻内存。这样子的话，对于大部分不存在的元素，我们只需要访问内存中的BF就可以 判断出来了，只有一小部分，我们需要访问在硬盘上的key-value数据库。从而大大地提高了效率。
m bit数组的宽度（bit数）
n 加入其中的key的数量
k 使用的hash函数的个数
f False Positive的比率Bloom Filter的应用
Bloom-Filter一般用于在大数据量的集合中判定某元素是否存在。
例如邮件服务器中的垃圾邮件过滤器。
在搜索引擎领域，Bloom-Filter最常用于网络蜘蛛(Spider)的URL过滤，网络蜘蛛通常有一个URL列表，保存着将要下载和已经下载的网页的URL，网络蜘蛛下载了一个网页，从网页中提取到新 的URL后，需要判断该URL是否已经存在于列表中。此时，Bloom-Filter算法是最好的选择。
1.key-value 加快查询
一般Bloom-Filter可以与一些key-value的数据库一起使用，来加快查询。
一般key-value存储系统的values存在硬盘，查询就是件费时的事。将Storage的数据都插入Filter，在Filter中查询都不存在时，那就不需要去Storage查询了。当False Position出现时， 只是会导致一次多余的Storage查询。
由于Bloom-Filter所用的空间非常小，所有BF可以常驻内存。这样子的话，对于大部分不存在的元素，我们只需要访问内存中的Bloom-Filter就可以判断出来了，只有一小部分，我们需要访问 在硬盘上的key-value数据库。从而大大地提高了效率。如图：
2.Google的BigTable
Google的BigTable也使用了Bloom Filter，以减少不存在的行或列在磁盘上的查询，大大提高了数据库的查询操作的性能。
3.Proxy-Cache
在Internet Cache Protocol中的Proxy-Cache很多都是使用Bloom Filter存储URLs，除了高效的查询外，还能很方便得传输交换Cache信息。
4.垃圾邮件地址过滤
像网易，QQ这样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。
一个办法就是记录下那些发垃圾邮件的 email地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。
如果用哈希表，每存储一亿个 email地址，就需要 1.6GB的内存（用哈希表实现的具体办法是将每一个 email地址对应成一个八字节的信息指纹，然后将这些信息指纹存入哈希表，由于哈希表 的存储效率一般只有 50%，因此一个 email地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB的内存。
而Bloom Filter只需要哈希表 1/8到 1/4 的大小就能解决同样的问题。
BloomFilter决不会漏掉任何一个在黑名单中的可疑地址。而至于误判问题，常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。
例子：网络蜘蛛（web crawler）
假设要你写一个网络蜘蛛（web crawler）。由于网络间的链接错综复杂，蜘蛛在网络间爬行很可能会形成“环”。为了避免形成“环”，就需要知道蜘蛛已经访问过那些URL。给一个URL， 怎样知道蜘蛛是否已经访问过呢？稍微想想，就会有如下几种方案：
1.将访问过的URL保存到数据库。
2.用HashSet将访问过的URL保存起来。那只需接近O(1)的代价就可以查到一个URL是否被访问过了。
3.URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库。
4.Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。
方法1~3都是将访问过的URL完整保存，方法4则只标记URL的一个映射位。
以上方法在数据量较小的情况下都能完美解决问题，但是当数据量变得非常庞大时问题就来了。
方法1的缺点：数据量变得非常庞大后关系型数据库查询的效率会变得很低。而且每来一个URL就启动一次数据库查询是不是太小题大做了？
方法2的缺点：太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。
方法3：由于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。
方法4消耗内存是相对较少的，但缺点是单一哈希函数发生冲突的概率太高。
综合以上，最好就是选用方法5，bloom filter，允许小概率的出错，不一定要100%准确！也就是说少量url实际上没有没网络蜘蛛访问，而将它们错判为已访问的代价是很小的——大不了少抓几个网页呗。
<?php
class BloomFilter {
protected $m; //bit数组的宽度
protected $k; //使用的hash函数的个数
protected $n; //当前已加入合集个数
protected $bitset; //bit数组
//初始化
public function __construct($m, $n)
{
$this->m = $m;
$this->k = ceil(($m/$n)*log(2));//计算最优的hash函数个数:当hash函数个数k=(ln2)*(m/n)时错误率最小
$this->n = 0;
$this->bitset = array_fill(0, $this->m-1, false);//位数组
}
//False Positive的比率：f = (1 – e-kn/m)k
public function getFalsePositiveProbability()
{
$exp = (-1 * $this->k * $this->n) / $this->m;
return pow(1 - exp($exp), $this->k);
}
//添加数据到集合
public function add($key)
{
if (is_array($key)) {
foreach ($key as $k) {
$this->add($k);
}
return;
}
foreach ($this->getSlots($key) as $slot) {
$this->bitset[$slot] = true;
}
$this->n++;
}
//校验数据是否存在集合中
public function contains($key)
{
if (is_array($key)) {
foreach ($key as $k) {
if ($this->contains($k) == false) {
return false;
}
}
return true;
}
foreach ($this->getSlots($key) as $slot) {
if ($this->bitset[$slot] == false) {
return false;
}
}
return true;
}
//计算hash值给出的位置
protected function getSlots($key)
{
$slots = array();
//使用CRC32产生一个32bit的校验值
//由于CRC32产生校验值时源数据块的每一bit都会被计算，所以数据块中即使只有一位发生了变化，也会得到不同的CRC32值
$hash = crc32($key);
//随机数播种
mt_srand($hash);
//执行K次hash函数,获取对应位置
for ($i = 0; $i < $this->k; $i++) {
$slots[] = mt_rand(0, $this->m-1); //mt_srand与mt_rand连用
}
return $slots;
}
}
//添加数据
$items = array("first item", "second item", "third item");
$filter = new BloomFilter(100, 3);
$filter->add($items);
//校验数据
$items = array("firsttem", "second item", "thirditem");
foreach ($items as $item) {
var_dump(($filter->contains($item)));
}
输出结果：
bool(false)
bool(true)
bool(false)本文参考：