在日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断 它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。
最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间（因为要同时存储key和value，加上需要解决哈希碰撞，所以实际空间效率<50%）。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。比如说，一个象 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。如果用哈希表，每存储一亿 个 email 地址， 就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个 email 地址对应成一个八字节的信息指纹（详见：数学之美之信息指纹）， 然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有 50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB， 即十六亿字节的内存）。因此存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。
今天我们就介绍一个一种称作布隆过滤器的数学工具，它只需要哈希表 1/8 到 1/4 的大小就能解决同样的问题。
布隆过滤器介绍
原理
如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大。同时检索速度也越来越慢。
Bloom Filter 是一种空间效率很高的随机数据结构，Bloom filter 可以看做是对 bit-map 的扩展, 它的基本原理是：当一个元素被加入集合时，通过 K 个 Hash 函数将这个元素映射成一个位阵列（Bit array）中的 K 个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：
- 如果这些点有任何一个 0，则被检索元素一定不在；
- 如果都是 1，则被检索元素很可能在（存在误判率，下文会详解）。
如上图可知布隆过滤器的重点有两个：
- 一个bit数组，用来存放映射信息
- 多个Hash函数，用来将元素映射到bit数组
布隆过滤器背后的数学原理在于两个完全随机的数学冲突峰概率很小，因此，可以在很小的无识别率的条件下，用很小的空间存储大量的信息。
优点
- 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash 函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
- 布隆过滤器可以表示全集，其它任何数据结构都不能。
缺点
但是布隆过滤器的缺点和优点一样明显。误算率（False Positive）是其中之一。随着存入的元素数量增加，误算率随之增加(误判补救方法是：再建立一个小的白名单，存储那些可能被误判的信息。)。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。
布隆过滤器的应用场景
布隆过滤器决不会漏掉任何一个在黑名单中的可疑地址。但是，它有一条不足之处。比如，它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中，因为有可能某个好的邮件地址正巧对应个八个都被设置成一的二进制位。好在这种可能性很小。我们把它称为误识概率。
不能接受误报的场景
以注册用户的例子为例，我们利用布隆过滤器建立以注册的用户名单，判断用户是否可注册，会按照以下步骤执行:
- 传入注册用户的通行证，根据我们建立的已注册用户的布隆过滤器，查询该用户是否存在布隆过滤器中。
- 假设该用户不存在布隆过滤器的集合，对于元素不在集合的结果，布隆过滤器是不会误报，所以可以放心返回该用户可以成功注册的结果。
- 假设用户存在于布隆过滤器，对于元素在集合的结果，布隆过滤器有可能误报，所以我们还需要再查询下真正的数据库，确认用户是否真的已注册了。
可以接受误报的场景
对于垃圾邮件的黑名单过滤，它有极小的可能将一个不在黑名单中的电子邮件地址判定为在黑名单中。常见的补救办法是在建立一个小的白名单，存储那些可能别误判的邮件地址。
应用场景举例
- chrome、360危险网站识别
- 垃圾邮箱识别
- 爬虫URL去重
- 解决缓存穿透问题
- ……
布隆过滤器在java中的使用
接下来我将演示如何使用guava中封装的布隆过滤器算法以及说明其误判率。
创建代码工程
- 新建一个maven工程，然后在pom中引入guava的依赖：
<dependencies>
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>19.0</version> //版本在18以上才提供了布隆过滤器算法
</dependency>
</dependencies>
- 新建一个测试类
BoolmFilterTest,编写如下代码：
public class BoolmFilterTest {
private static final int insertions = 1000000;//100w
public static void main(String[] args) {
//初始化一个存储String数据的布隆过滤器，初始化大小为100w
BloomFilter<String> bloomFilter =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.01);
//初始化一个存储String数据的set，初始化大小为100w，做验证参考
Set<String> sets = new HashSet<String>(insertions);
//初始化一个存储String数据额list，初始化大小为100w
List<String> lists = new ArrayList<String>(insertions);
//向三个容器中初始化100w个随机唯一的字符串
for (int i = 0; i < insertions; i++) {
String uuid = UUID.randomUUID().toString();
bloomFilter.put(uuid);
sets.add(uuid);
lists.add(uuid);
}
//布隆过滤器误判的次数
int wrongCount = 0;
//布隆过滤器正确地次数
int rightCount = 0;
//随机抽取1w数据做验证
for (int i = 0; i < 10000; i++) {
String test = i % 100 == 0 ? lists.get(i / 100) : UUID.randomUUID().toString();
//布隆过滤器验证通过
if (bloomFilter.mightContain(test)) {
if (sets.contains(test))
rightCount++;
else
wrongCount++;
}
}
System.out.println("right count : " + rightCount);
System.out.println("wrong count : "+wrongCount);
System.out.println("wrong rate : "+Math.round(((wrongCount*1.0)/(9900))*100)+"%");
}
其中insertions表示我们全量数据的大小（但实际bit数组的长度和hash算法的个数都是不定的，根据误判率动态调整）。
BloomFilter<String> bloomFilter =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.01);
这一行代码建立一个布隆过滤器，工厂方法有三个参数，分别表示过滤器的类型，容量大小，误判率（没错，你可以指定误判率，但是千万别写0，默认是0.03）。
接下来我们以100万随机字符串为数据源介绍布隆过滤器的使用以及统计其误判率。
由结果可以看到布隆过滤器说不过的确实不过，但是它说过的不一定真的是对的，这就是误判的情况，总体上实际误判率与我们期望的是一致的。
我们再来看看算法内部调整的数组长度和hash函数的个数：
可以看到为了达到我们要求的误判率，算法包实际创建的bit数组的长度是 9585058，Hash函数的个数是7个，具体为什么是这些数字，可以查看这篇论文了解：
http://en.wikipedia.org/wiki/Bloom_filter#Probability_of_false_positives
总结
我们首先介绍了布隆过滤器的基本原理、优势劣势、使用场景；然后利用guava提供的算法包展示了字符串的判断和测试，并验证了它的误判率。布隆过滤器在行业应用比较广泛，感谢google的工程师为我们提供了好用的算法包。
