数据库必知词汇：布隆过滤器（Bloom Filter）

|名词定义|

布隆过滤器（Bloom Filter）是由Burton Bloom 在1970年提出的，其后在P2P上得到了广泛的应用。一个空的布隆过滤器是一个m位的位数组，所有位的值都为0。定义了k个不同的符合均匀随机分布的哈希函数，每个函数把集合元素映射到位数组的m位中的某一位。Bloom filter算法可用来查询某一数据是否在某一数据集合中。其优点是查询效率高、可节省空间。但其缺点是会存在一定的错误。因此Bloom filter 算法仅仅能应用于那些同意有一定错误的场合。可使用Bloom filter 算法的场合包含字典软件、分布式缓存、P2P网络和资源路由等等。

| 发展历程 |

1970年由Burton Bloom提出布隆过滤器（Bloom Filter）是一个空间效率比较高的数据结构，用于检测一个元素在集合中是否存在。Bloom Filter就被广泛用于拼写检查和数据库系统中。

近一二十年，伴随着网络的普及和发展，Bloom Filter在网络领域获得了新生，各种Bloom Filter变种和新的应用不断出现。可以预见，随着网络应用的不断深入，新的变种和应用将会继续出现，Bloom Filter必将获得更大的发展。

| 技术特点 |

使用布隆过滤器能够推断一个元素是否在某一个集合中。假设这个集合是使用线性结构存储的话。其查找的时间复杂度是O(n)；使用像二叉树或B-tree这种树形结构存储的话其查找的时间复杂度是O(logn)。而使用布隆过滤器在能够容忍一定错误率的情况下，其时间复杂度是O(1)。因此，与传统的权衡空间或时间的算法不同，布隆过滤器极其巧妙。通过引入一定的错误率来换取时间和空间，在某些应用大大提高了性能。

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。布隆过滤器存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性：

• 存在误判，可能要查到的元素并没有在容器中，但是Hash之后得到的k个位置上值都是1。如果布隆过滤器中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
• 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter。

| 相关词 |

Bloom_filter – 布隆过滤器

HBase – 数据库

Hash table – 哈希表

| 案例展示 |

• Google 的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的IO次数。
• Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器。
• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。
• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。
• Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。
• Google Guava - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
• Apache的HBase - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
• Apache_Cassandra - 使用bloom过滤器判断是否存在该行（rows）或（colums），以减少对磁盘的访问，提高数据库的访问性能
• 比特币 - 使用布隆过滤判断钱包是否同步OK

|资料来源|

Dillinger, Peter C.;Manolios, Panagiotis (2004a), "Fast and Accurate Bitstate Verification forSPIN", Proceedings of the 11thInternational Spin Workshop on Model Checking Software, Springer-Verlag, LectureNotes in Computer Science 2989

Kirsch, Adam; Mitzenmacher, Michael(2006), "Less Hashing, Same Performance: Building a Better BloomFilter", in Azar, Yossi; Erlebach, Thomas, Algorithms– ESA 2006, 14th Annual European Symposium (PDF), LectureNotes in Computer Science 4168,Springer-Verlag, Lecture Notes in Computer Science 4168, pp. 456–467, doi:10.1007/11841036, ISBN 978-3-540-38875-3

Mitzenmacher & Upfal (2005), pp. 109–111, 308.

BloomFilter基本概念和实现原理

https://blog.csdn.net/zq602316498/article/details/40660235

Bloom Filter 算法具体解释

https://www.cnblogs.com/lcchuguo/p/5254340.html

布隆过滤器(BloomFilter)的原理、实现和探究

https://my.oschina.net/LucasZhu/blog/1813110

大数据量下的集合过滤—Bloom Filter

https://www.cnblogs.com/z941030/p/9218356.html