概述
之前在浏览某个社区的时候，看到有个人为了一个问题，具体帖子忘了是哪个了，不过问题的的意思是给 10W 个关键词，让你给出比较有效的方式来屏蔽关键词。这个问题其实挺有意思的，看上去似乎很简单，但是，细看一下其实也不简单。这里的上下文没有给得很明确，因为你说要屏蔽关键词，没说是在啥场景下？是一个博客社区，还是说某款聊天软件亦或者论坛回复？还是说只是判断一个词是不是关键词？
不过，从后面大家的讨论和回复来说，似乎场景就仅仅局限在给定一个词，判断这个词是不是需要过滤的关键词。这个似乎就比较好办了，我一上来的第一个想法就是这不就是 Hash 吗？但是，再回味一下，似乎 Hash 会有些问题，一个是空间占用，这里没有要求，如果每个 word 以平均 6 bytes 来算，那么 10W 就是 600KB，似乎可接受，但是你还要 hash 的话，那空间占用得多上一些，看具体实现，是 Table 实现还是 Tree 实现。此外，还需要考虑扩展实现，如果后续关键词变多了，多了一个数量级，也是很可观的。
但是，在浏览别人的回复之后，我发现了一个熟悉的名词：Bloom Filter，第一次看到这个词的时候还在上大学，那时还是看到吴军博士的 《数学之美》里面，他当时就是以黑名单的应用来介绍 Bloom Filter 的，不过由于这么多年过去了，从没有真实应用过，所以也就将这技术忘记了。所以，在这篇文章中，我将和大家一起来回忆一番 Bloom Filter。
What’s Bloom Filter
Bloom Filter 可以认为是一种特殊的 Hash 函数，它的作用是用来确定一个元素是否在集合中；但是，因为它不保存原始的值，所以无法确定得到的结果是正确的，其实就是存在一定的误差，这个误差可以通过调整参数来减少，但相应得会增加空间。
Bloom Filter 的步骤大概是这样的：
- 设计一张长度为 N bits 的 Table
- 设计 K 个结果不同的普通 Hash 函数（MD5，SHA-1，MurmurHash 等都行），Hash 函数的结果介于 [0, N) 之间
- 对于输入 Val，分别使用 K 个 Hash 函数进行 hash 计算，得到结果：r1，r2…，rk
- 将 Table 中的 Bit[r1]，Bit[r2]…，Bit[rk] 设置为 1。
| 图 1：Bloom Filter |
|---|
|
| 图片摘抄自: Google 黑板报< 数学之美 > |
当你需要判断一个元素 x 是否在指定的集合中的时候，操作步骤是这样的：
- 计算 x 的 Hash 结果: r1，r2…，rk
- 判断 Bit[r1]，Bit[r2]…，Bit[rk] 是否都为 1，如果都为 1，我们可以认为这个元素就在这个集合中。
Bloom Filter 误差
从前面的介绍中可以发现，Bloom Filter 是存在一定的误差性的，因为可能一个元素不存在于集合中，但是因为 Hash 后的所有位都为 1 而被误判为存在，所以这里必须指出：Bloom Filter 不是完全匹配的。
那么既然如此，Bloom Filter 的误差有多大呢？别担心，专业的计算机科学家已经帮我们算过了，这里先假定一些前提：
- 所有的函数函数的结果都是随机的，值出现在值域的可能性都是相同的
- m 表示 Table 的 bit 数量，k 表示我们使用了几个 Hash 函数
- n 表示当前我们已经插入了几个元素
那么冲突的概率就是(摘抄自 wiki):
因此可以看出，如果我们想要减少误差率，可以增加 n 亦或者增加 k，但这都会带来额外的开销，具体使用多少，可以根据自己的业务去调参。
Bloom Filter 的应用
前面说了 Bloom Filter 的一个应用就是关键词(黑/白名单)过滤，那么是否还有其他比较好的应用可以让我们在平时开发中有一些实质性得收获呢？下面就介绍几个我觉得比较有价值的应用：
- DB 加速查询：我们知道在 DB 中，很多数据都是放在 Disk 里面的，而一般是放 Index 和热数据在内存中，而 Disk 的获取一般都不是单条数据直接 Load 出来的。根据 B 树的设计，一般一个查询可能会加载好几块的数据块，而最后发现数据其实不在 DB 中，所以就坑了。所以，如果在查询数据之前就先判断一遍，数据在不在 Disk 内，在了再获取就可以加速很多操作了，据说（我未考证）BigTable 和 Cassandra 都使用了这种方式；
- 垃圾邮件过滤：这个就是一个比较简单的黑/白名单操作了。
- 网络爬虫：对于一个比较庞大的爬虫系统来说，如何有效得判断是否已经抓取过一个 URL 以及这个 URL 的过期时间是个很关键的问题。对于是否已经抓取过 URL 这个场景，使用 Bloom Filter 倒是个不错的考虑，毕竟误判了也是重复抓了一遍，而且这种概率也不会很高。
Bloom Filter 实现
扯那么多没用的，还不如上点代码来得实际，下面我就以 Go 语言为例，介绍一个简化版的实现，希望对有兴趣的同学有所帮助。由于完整实现可能会比较复杂，我就抽取其中两个重要的操作进行简化编写，分别是：
- 添加 K/V 操作
- 查询 K 操作
哈希函数组合实现
- 这里的实现我使用 k = 2
Bloom Filter 添加 K/V
Bloom Filter 查询 Key
小结
OK，本文就是关于 Bloom Filter 的一些简单介绍，其实在实际应用中，我上面写的示例是一个 Pool 的实现，但是，对于熟悉 Redis 的同学来说，可能是有一些启发的。是的，如果在工业中想使用 Bloom Filter，可能 Redis 是一个非常有利的帮手，尤其是其对于 bit 操作的支持，相信有同学会给出漂亮的实践！