浅谈布隆过滤器

首先在开始之前我们先考虑一个问题，如何快速判断某 URL 是否在 20 亿的网址 URL 集合中？
如果想判断一个元素是不是在一个集合里，一般思路的是将集合中所有元素保存起来，然后进行遍历比较。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都可以用于解决该类问题。但是随着集合中元素的增加（比如说是 20 亿个 url），我们需要的存储空间越来越大。同时检索速度也越来越慢。可能很多人首先想到的会是使用 HashSet，因为 HashSet 基于 HashMap，理论上时间复杂度为：O(1)。达到了快速的目的，但是空间复杂度呢？字符串通过 Hash 得到一个 Integer 的值，Integer占4个字节，那 20 亿个 url 字符串理论上需要：20 亿*4/1024/1024/1024=7.45G 的内存，造成庞大的空间开销，显然这种解决方案是不合理的。但是针对这种问题我们该如何解决哪？这便引出了我们这一节的主题 布隆过滤器。

何为 布隆过滤器

按照维基百科定义
布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

布隆过滤器 的原理

布隆过滤器 的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点，把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。这就是 布隆过滤器 的基本思想。
当然只有抽象的原理说明是很难让人理解的，下边我们结合例子对算法的执行流程进行说明。
首先在对算法描述之前我们先给定一个前提即：
我们此处使用的 HASH 算法使用的 HASH 值是 Integer 类型的：由于 Integer.MAX_VALUE=2147483647，意思也就是任何一个 URL 的哈希值都会在 0-2147483647 之间。
第一步：对 source 数组进行预处理，我们可以定义 2147483647 长度的 bit 数组命名为 source，用来存储 hash 之后产生的所有可能值。存储这个 byte 数组系统只需要：2147483647/8/1024/1024=256M。 我们分别通过 N 个 HASH 函数对这 20 亿个 URL 字符串进行处理得到 20 亿条 N 个不同的 HASH 值(此处我们称之为结果对)，然后针对每个结果对 (value_1,value_2 ... value_n)，我们分别将 source 的 N 个位置 (source[value_1],source[value_2]...source[value_n]) 置为 1，分别对 20 亿个结果对做如上的处理，我们便得到的一个处理过的 source 数组，整个过程的处理逻辑如下图所示。

至此整个算法的预处理阶段算式完成。
第二步：url 匹配当我们获得一个需要判断的 url字符串 时我们通过 HASH_1、HASH_2...HASH_n 等 N 个 HASH 函数进行处理得到 N 个整数 （value_1,value_2..value_n） 分别判断 source[value_i] 的值是否是 1，如果是则判断下 source[value_i+1] 的值是否是 1，以此类推，直到将 N 个 HASH 值判断完毕。中间任何一个位置的值不是 1，我们便可以得出结论，待判断的 url 不在 url 集合中，如果 N 个 HASH 判断完毕，均满足条件，我们便可以认为待判断的 url 在 URL 集合中。整个过程如下图所示:

优点

1. 相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数 O(K)。
2. 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。
3. 布隆过滤器可以表示全集，其它任何数据结构都不能

缺点

整个过程并不难理解，但值得注意的是使用该算法判断目标字符串是由一定 误算率 的。一方面随着存入数据元素的规模越来越越大，误算率 也会随之增加。另一方面 误算率 还和使用的 HASH 的个数和种类有关，一般来说选用的 HASH 函数越多，误算率就会越小。

应用场景

1、黑名单 2、URL 去重 3、单词拼写检查 4、Key-Value 缓存系统的 Key 校验 5、ID 校验，比如订单系统查询某个订单 ID 是否存在，如果不存在就直接返回。

使用方法

在实际开发中 Guava 框架提供了布隆过滤器的具体实现：BloomFilter，使得开发不用再自己写一套算法的实现。

1. 创建布隆过滤器并且传入最大集合的个数，以及期望的误报率
   Funnel: 起到管道的作用将各种流和数据类型处理为 BoomFilter 可处理的类型
   expectedInsertions: 要处理的数据规模
   expectedInsertion： 期望的误报率

BloomFilter<String> filter=BloomFilter.create(Funnels.stringFunnel(Charset.defaultCharset()),100,0.01);

2.初始化 urls 集合（相当于得到 source 数组）

//插入url集合String 
urls[]={"vcjmhg.top","example.com","vcjmhg.com","vcjmhg.cn","baidu.com","google.com"};
for(int i=0;i<urls.length;i++){    filter.put(urls[i]);}

3.输入测试 url 进行测试

//我们添加了七个元素，并且定义了最大字符数量为500，因此我们过滤器会产生十分准确的结果//测试vcjmhg.top是否在urls集合中,以及其准确率
System.out.println("vcjmhg.top是否在urls集合中"+filter.mightContain("vcjmhg.top"));
System.out.println("vcjmg.top的测试准确率:"+filter.expectedFpp());
//测试bing.com是否在urls集合中
System.out.println("bing.com是否在urls集合中:"+filter.mightContain("bing.com"));
System.out.println("bing.com此次的测试准确率:"+filter.expectedFpp());

运行结果：

与其他技术的对比与扩展

回顾布隆过滤器的原理我们发现布隆过滤器的原理与位运算的算法和题目很相似，我们可以尝试和位运算相关的算法结合进行学习。

代码地址

博客代码地址