Bloom是个人名。

相关资源：

[1] A. Broder and M. Mitzenmacher. . Internet Mathematics, 1(4):485–509, 2005.

[2] M. Mitzenmacher. . IEEE/ACM Transactions on Networking 10:5 (2002), 604—612.

[3]

[4]

, Broder and Mitzenmacher. An excellent overview.

, which has an excellent and comprehensive page on Bloom filters

, Kirsch and Mitzenmacher

, Almeida et al

学习Bloom Filter

1、概述

布隆过滤器（Bloom Filter）是由Burton Howard Bloom于1970年提出，它是一种概率型数据结构，用于判断一个元素是否在集合中。（作用）

 

Bloom filter 是一个数据结构，它可以用来判断某个元素是否在集合内，具有运行快速，内存占用小的特点。

而高效插入和查询的代价就是，Bloom Filter 是一个基于概率的数据结构：它只能告诉我们一个元素绝对不在集合内或可能在集合内

 

判断一个元素是否在集合中可用的方法有：

• 数组
• 链表
• 树、平衡二叉树、Trie
• Map (红黑树)
• 哈希表

既然已经有了这么多的方法，为啥还要用布隆过滤器这种会产生误判的方法呢？

 

当集合里面的元素数量足够大，如果有500万条记录甚至1亿条记录呢？这个时候常规的数据结构的问题就凸显出来了。数组、链表、树等数据结构会存储元素的内容，一旦数据量过大，消耗的内存也会呈现线性增长，最终达到瓶颈。有的同学可能会问，哈希表不是效率很高吗？查询效率可以达到O(1)。但是哈希表需要消耗的内存依然很高。使用哈希表存储一亿 个垃圾 email 地址的消耗？哈希表的做法：首先，哈希函数将一个email地址映射成8字节信息指纹；考虑到哈希表存储效率通常小于50%（哈希冲突）；因此消耗的内存：8 * 2 * 1亿 字节 = 1.6G 内存，普通计算机是无法提供如此大的内存。这个时候，布隆过滤器（Bloom Filter）就应运而生。()

 

假定我们存储一亿个电子邮件地址，我们先建立一个十六亿二进制（比特），即两亿字节的向量，然后将这十六亿个二进制全部设置为零。对于每一个电子邮件地址 X，我们用八个不同的随机数产生器（F1,F2, ...,F8） 产生八个信息指纹（f1, f2, ..., f8）。再用一个随机数产生器 G 把这八个信息指纹映射到 1 到十六亿中的八个自然数 g1, g2, ...,g8。现在我们把这八个位置的二进制（这里没太明白，八个位置的二进制的意思是，这八个位置的意思每个位置代表了若干个字节？）全部设置为一。当我们对这一亿个 email 地址都进行这样的处理后。一个针对这些 email 地址的布隆过滤器就建成了。（见下图）

 

2、应用场景：

• 字处理软件中，需要检查一个英语单词是否拼写正确
• 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
• 在网络爬虫里，一个网址是否被访问过
• yahoo, gmail等邮箱垃圾邮件过滤功能

 

哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。（优点：占用空间小）

布隆过滤器可以插入元素，但不可以删除已有元素。（操作特点：不能删除元素，因为你不知道你删的是哪个）

其中的元素越多，误报率越大，但是漏报是不可能的。（查重特点：宁肯错杀三千，不会放过一个）

3、算法描述

首先一个空的布隆过滤器是有m个bit的位数组，每个bit位都被初始化为0。

同时，还有需要定义k个不同的哈希函数，每个都会将元素通过该哈希函数计算到m个不同位置中的一个。

 

下面描述的时候规定：n表示待判别的元素个数，m为布隆过滤器或者哈希表的slot数，k为布隆过滤器哈希函数的个数。

 

• 增加元素：用k个哈希函数将它hash得到bloom filter中k个bit位，将这k个bit位置1。
• 查询元素：为了判断一个元素是否在集合中，可以用k个hash函数将它进行hash得到k个bit位。如果这k个bit位全为1，则此元素在集合中；如果其中任意一位不为1，则此元素不在集合中。
• 移除元素：一旦向布隆过滤器中添加了一个元素，那么是不允许从布隆过滤器中移除的，因为不能保证你不会讲其他对应到这k个bit的元素同时移除了，这样一来就会导致误判。

 

布隆过滤器（Bloom Filter）的核心实现是一个超大的位数组和几个哈希函数。

以上图为例，具体的操作流程：假设集合里面有3个元素{x, y, z}，哈希函数的个数为3。首先将位数组进行初始化，将里面每个位都设置位0。对于集合里面的每一个元素，将元素依次通过3个哈希函数进行映射，每次映射都会产生一个哈希值，这个值对应位数组上面的一个点，然后将位数组对应的位置标记为1。查询w元素是否存在集合中的时候，同样的方法将w通过哈希映射到位数组上的3个点。如果3个点的其中有一个点不为1，则可以判断该元素一定不存在集合中。反之，如果3个点都为1，则该元素可能存在集合中。注意：此处不能判断该元素是否一定存在集合中，可能存在一定的误判率。可以从图中可以看到：假设某个元素通过映射对应下标为4，5，6这3个点。虽然这3个点都为1，但是很明显这3个点是不同元素经过哈希得到的位置，因此这种情况说明元素虽然不在集合中，也可能对应的都是1，这是误判率存在的原因。()

4、注意的地方

当k很大的时候，要设计出k个独立的哈希函数比较困难；可供替换的方法有：利用输出范围很大的哈希函数（如MD5产生的128位），将输出分为k份，或者将k个不同的初始值结合元素，给哈希函数生成k个不同的数。

 

如果向布隆过滤器增加的元素过多，n/m过大，会导致误判率升高，因此要么重新建立布隆过滤器，要么在开始预估一下需要布隆过滤器中会加入多少元素，然后选择合适的m。

5、时间和空间上的优势

可以当做集合来存储元素的数据结构有：self-balance BST，tries（确定没写错），hash table或者array，chain；它们中的大多数至少需要存储元素本身，对于小的整数需要少量的bits，对于字符串则需要任意多的bits（tries例外，因为元素可以共享存储空间）；而chain结构还要为存储指针付出额外的代价。布隆过滤器的插入和查询操作的复杂度都为O(k)，与集合中元素的多少无关，这是其他的数据结构都无法比拟的。

 

如果数据元素不是很多，并且大多都在集合中，则使用确定性的bit array远远胜过使用布隆过滤器。因为bit array对于每个可能的元素空间上只需要1bit。

 

当考虑到冲突时，对于有m个slot（槽）的bit array或者其他哈希表，如果要保证1%的误判率，则这个bit array只能存储m/100个元素，因而有大量的空间被浪费，同时空间复杂度也会急剧上升。这里可以使用k>1的布隆过滤器，即k个哈希函数将每个元素对应于k个bits，从而误判率会降低很多，如果k和m选取合适，可以使一半的m被置为1，非常节省空间。

 

 

 

代码实现

 

 

 

哈希函数简单介绍

哈希函数的概念是：将任意大小的数据转换成特定大小的数据的函数，转换后的数据称为哈希值或哈希编码。

 

 

Bloom filter 里的哈希函数需要是且。同时，它们也需要尽可能的快 (尽管 sha1 之类的加密哈希算法被广泛应用，但是在这一点上考虑并不是一个很好的选择).

这些都是快速，简单且彼此独立的哈希函数的例子： 包括 , 族哈希函数, 以及.

如果你希望了解一个比加密哈希函数快的哈希函数可以达到什么程度，可以参考。当把 bloom filter 的实现从 md5 切换到 murmur 时，速度提升了 800%。

一个关于 Bloom filter 实现方式的简单调查:

• 使用 . (同时, 是一个简短说明他们如何使用 bloom filter）
• 使用加密哈希算法。
• 使用一种简单的哈希算法，
• 使用 fnv1a (把这个加进来是希望展示有人使用 fnv 算法)
• 使用 MD5

 

关于哈希函数更深入介绍，可以看这里的：

 

高级话题

在写下更过关于 Bloom filter 的内容之前，我需要声明一点：我从未在生产环境使用过 Bloom filter（我擦，你们都不用，然后告诉别人这个好用，还是没有用到适用场景？）。所以不要不假思索的相信下面的内容，我想做的只是给你一个概括式的介绍，同时告诉你可以去哪里寻找更多内容。

在下面的内容里, 我们假设在 Bloom filter 里面有 k 个哈希函数, m 个比特, 以及 n 个已插入元素。

Bloom filter 应该设计为多大？

Bloom filter 的一个优良特性就是可以修改过滤器的错误率。一个大的过滤器会拥有比一个小的过滤器更低的错误率。

错误率会近似于 (1-e^-kn/m)^k, 所以你只需要先确定可能插入的数据集的容量大小 n, 然后再调整 k 和 m 来为你的应用配置过滤器。

而这带来了一个显而易见的问题:

应该使用多少个哈希函数?

Bloom filter 使用的哈希函数越多运行速度就会越慢。但是如果哈希函数过少，又会遇到误判率高的问题。所以这个问题上需要认真考虑。

在创建一个 Bloom filter 的时候需要确定 k 的值，也就是说你需要提前圈定 n 的变动范围。而一旦你这样做了，你依然需要确定 m（总比特数）和 k (哈希函数的个数）的值。

似乎这是一个十分困难的优化问题，但幸运的是，对于给定的 m 和 n ，有一个函数可以帮我们确定最优的 k 值: (m/n)ln(2)

所以可以通过以下的步骤来确定 Bloom filter 的大小:

1. 确定 n 的变动范围
2. 选定 m 的值
3. 计算 k 的最优值
4. 对于给定的n, m, and k计算错误率。如果这个错误率不能接收，那么回到第二步，否则结束

Bloom filter 的时间复杂度和空间复杂度?

对于一个 m 和 k 值确定的 Bloom filter，插入和测试操作的时间复杂度都是 O(k)。这意味着每次你想要插入一个元素或者查询一个元素是否在集合中，只需要使用 k 个哈希函数对这个元素求值，然后将对应的比特位标记或者检查对应的比特位。

相比之下，Bloom filter 的空间复杂度更难以概述，它取决于你可以忍受的错误率。同时也取决于输入元素的范围，如果这个范围是有限的，那么一个确定的比特向量就可以很好的解决问题。如果你甚至不能很好的估计输入元素的范围，那么你最好选择一个哈希表或者一个可拓展的 Bloom filter。

可以用 Bloom filter 来做什么?

我会将你引向 而不是将它们的内容拷贝过来。 的演讲很好的阐述了 Bloom filter 在生物信息学中的应用。

 

总结

总结条毛啊！