布隆过滤器

布隆过滤器(英语：Bloom Filter)是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。主要用于判断一个元素是否在一个集合中。

通常我们会遇到很多要判断一个元素是否在某个集合中的业务场景，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表(又叫哈希表，Hash table)等等数据结构都是这种思路。但是随着集合中元素的增加，我们需要的存储空间也会呈现线性增长，最终达到瓶颈。同时检索速度也越来越慢，上述三种结构的检索时间复杂度分别为O(N)，O(log(N))，O(1)。

这个时候，布隆过滤器(Bloom Filter)就应运而生。

今天，我们将探索Bloom过滤器-一种设计简单而优雅的数据结构。我们将深入研究Bloom过滤器的基本原理，了解其优点和缺点，并引导您完成使用Python实现Bloom过滤器的过程。 布隆过滤器是计算机科学中的一个热门话题，特别是在系统设计和优化以及技术面试中。了解这种数据结构以及如何实现它是展示您作为工程师的技能的绝佳方式。

问题

Bloom过滤器要解决的问题很简单-确定元素是否属于数据集。当数据集太大以至于无法放入单个计算机的内存甚至硬盘上时，这项任务变得具有挑战性，特别是在数据存储在多个节点上的分布式系统中。在这种情况下，与磁盘访问相关联的通信开销使任务更具挑战性。

一种概率数据结构的方法

传统的方法，例如迭代数据集并比较每个元素，在大型数据集中可能非常耗时且不切实际(即使我们使用MapReduce或Spark等分布式框架)。我们更喜欢提供接近实时结果的解决方案。

一种可能的解决方案是使用与数据库中使用的索引类似的索引。这些索引包含排序的键和指向数据库中相应元素的指针，这允许我们通过键快速找到元素。然而，在我们的例子中，我们甚至不需要元素的实际值;我们只需要知道给定键的值是否存在。存储实际值将浪费存储空间。

如果我们不需要实际的值，我们可以用一些东西来压缩元素，以避免浪费存储空间。接下来想到的是散列函数的使用，即将任意大小的数据映射到固定大小的数据的函数。我们简单地计算每个元素的哈希值，并在给定的偏移量处将一些值写入数组。在这种情况下，偏移量是哈希值除以数组大小的余数。或者在伪代码中，它看起来像这样： array[hash(element) % size] = 1 逻辑与常规哈希表相同，除了我们不存储具有相同哈希值的元素链以保存空间。 这种方法大大压缩了搜索数据，使其成为我们大型数据集的理想选择。要检查一个元素是否在数据集中，我们只需计算潜在成员的哈希值，并检查相应的数组值是否未设置为零。

要检查元素是否在数据集中，正如您已经猜到的那样，只需计算潜在成员的哈希值并确保相应的数组值未设置为零即可。

但这里有一个缺点... 散列函数在多对一的基础上工作，这意味着多个元素可以具有相同的散列值，但每个元素只有一个唯一的散列。这可能会导致冲突，其中多个元素具有相同的散列值，并且由于这些冲突而导致在搜索阵列时的误报。 在这种情况下，我们接受误报的可能性，而不采取任何额外的措施。更有可能的是，数据集中不存在元素，即使数据集很大，因为并非所有可能的元素通常都存在。我们的数据结构保证正确地确定元素不存在，因为否则哈希函数将产生我们拥有的值。这就是我们如何得出这个数据结构的概率性质。

更多改进

我们现在有什么?就速度而言，该算法将工作得很好-最多我们只计算散列函数并获取偏移值，但就空间而言，meh -可能不是。因为如果我们想最小化误报的概率，我们需要一个大的数组。 为了解决这个问题，让我们使用bitmask，其中我们在与哈希函数的值相对应的偏移处拾取位。在逻辑方面没有区别，但在内存使用方面有很大的提高。 为了进一步最小化误报的概率，我们将使用几个哈希函数，并在我们的位掩码中提高与它们的值相对应的几个位。为了检查，我们将计算相同的哈希函数并检查位。如果所有的位都被提升，那么很可能我们有一个元素(或者可能因为冲突而没有)。如果至少有一个位没有被提升-那么我们肯定没有它。 通过这些改进，我们现在有了一个Bloom过滤器。

一点理论

布隆过滤器是用于确定元素是否属于集合的概率数据结构。

其基本思想是使用一个固定大小的位数组和一组散列函数将元素从数据集映射到位数组。每个散列函数将元素映射到位阵列中的一个或多个位置。当向数据集添加元素时，位数组中的相应位被设置为1。为了检查元素是否在数据集中，使用相同的散列函数将元素映射到位数组，并检查相应的位。如果所有位都是1，则该元素可能在数据集中(具有一定的误报概率)。如果任何一个位为0，则该元素肯定不在数据集中。

最好的部分?Bloom过滤器保证永远不会有假阴性。这意味着，如果元素不在集合中，布隆过滤器将永远不会说它是。然而，可能存在假阳性。但是不用担心，误报的概率可以通过改变用于Bloom过滤器的表的大小以及改变散列函数的数量来控制。布隆过滤器操作

操作

您可以使用布隆过滤器对集合执行操作，方法是创建多个布隆过滤器，每个布隆过滤器对应一个要处理的集合，然后对过滤器位应用按位操作。

例如，要执行两个集合的交集，您可以为每个集合创建一个Bloom过滤器，然后对两个过滤器的位执行按位 AND 操作。仅当在两个原始滤波器中的位位置为1时，所得到的滤波器的位位置才为1。类似地，要联合收割机两个集合(执行联合操作)，您可以为每个集合创建两个布隆过滤器，然后对两个过滤器的位执行逻辑 OR 。如果在原始滤波器中的至少一个中该位置是1，则所得滤波器将在该位位置中具有1。但是等等，有个问题。所得到的过滤器将是概率性的，这意味着结果中可能存在假阳性。

下面是最重要的一点：你甚至可以用Bloom过滤器估计原始数据集的大小!您所需要的只是过滤器的大小和提升位的数量。请继续关注实施细节。

哈希函数

哈希函数是Bloom过滤器的关键组成部分，选择正确的哈希函数对于获得最佳性能至关重要。Bloom过滤器通常使用更快的非加密散列函数，如MurmurHash或FNV，而不是使用像MD5这样的加密散列函数，这是很慢的。

但速度并不是唯一需要考虑的因素。散列函数的独立性对于确保准确的结果至关重要。它指的是散列函数的输出应该尽可能不相关的属性。如果散列函数不是独立的，那么它们很有可能对给定的输入产生相同的结果，从而导致更多的冲突和误报。

解决办法?使用多个哈希函数来增加独立性。组合不同的算法或使用不同的种子可以帮助确保散列函数产生唯一的输出，从而降低冲突概率并提高过滤器的准确性。

优点和缺点

优点：空间效率

Bloom过滤器的主要优点是它非常紧凑。我们只需要存储位掩码，而不是存储实际值，这占用的空间要少得多。例如，您可以表示1000万条记录，占用大约40MB的空间。这使得它对于无法容纳在单个计算机的内存中甚至硬盘上的大型数据集特别有用。

优点：速度

Bloom过滤器是一种快速的工具，用于检查集合中元素的存在。只需快速计算哈希函数并检查位数组中的相应位，就可以确定是否存在时间和空间复杂度为O(k)的元素，其中k是哈希函数的数量。这意味着即使散列函数的数量增加，速度也保持不变。

另外，向Bloom过滤器添加元素也同样快速，只需要O(k)常数时间。即使搜索在第一次尝试时没有找到元素，经过良好调整的Bloom过滤器通常也会在一次或两次额外的尝试中找到它，使搜索操作与插入操作一样快。

优点：可伸缩性

布隆过滤器的构造可以被有效地并行化。这意味着我们可以将原始数组划分为多个部分，在每个部分上并行构建一个单独的过滤器，然后合并它们。这不仅有助于避免一个地方的瓶颈，例如在Spark驱动程序上，而且还允许在多个节点上进行并行处理。

缺点：概率数据结构

虽然Bloom过滤器是一个强大的工具，但重要的是要记住它的潜在限制。一个关键的缺点是它是一个概率数据结构，这可能导致误报。当散列函数导致一个不在集合中的元素被错误地识别为它是集合时，就会发生这种情况。

可以通过使用多个散列函数和更大的位阵列来降低误报的可能性。请记住，这样做会增加布隆过滤器的空间需求。

缺点：不支持删除元素

布隆过滤器的另一个缺点是它不支持从集合中移除元素。一旦你把东西加到布景里，它就永远留在那里了。 这个问题可以通过选择计数Bloom过滤器来解决，它不仅允许您向集合中添加元素，而且还允许您通过减少位数组中的相应位来删除它们。因此，您可以两全其美-布隆过滤器的速度和效率，以及根据您的需要管理您的集合的灵活性。

缺点：有限的调整大小功能

Bloom过滤器的一个缺点是它们很难有效地调整大小。与其他直接存储元素的数据结构不同，Bloom过滤器不保留它们所看到的元素的记录。因此，如果你想构建一个更大的Bloom过滤器，你需要从永久存储中检索所有的原始密钥。 然而，有一个解决这个挑战的办法。可扩展的Bloom过滤器，顾名思义，是可以随着过滤器中元素数量的增长而自动调整大小的Bloom过滤器。这是通过使用一系列较小的布隆过滤器来实现的，每个布隆过滤器具有固定的大小，并组合成一个链。随着过滤器中元素数量的增加，更多的Bloom过滤器被添加到链中，从而有效地增加了其大小。

实现

现在我们已经对Bloom过滤器的工作原理有了很好的理解，让我们深入研究一下实现。一个基本的Bloom过滤器很容易实现。 使用的哈希函数的数量由 num_hashes 参数指定，位数组的大小由 size 参数指定。 salt 参数允许哈希值的额外随机化。 add 方法设置对应于元素的散列值的位，并且 __contains__ 方法检查是否设置了对应于元素的散列值的所有位。 在该实现中， BloomFilter 类使用SHA1散列函数将元素映射到位数组中的位，所有这些位最初都设置为0。它只是相同的哈希函数具有不同的salt，即添加到哈希值的值。在我们的实现中，第一个哈希函数添加 0 ，第二个添加 1 ，依此类推。 为了清楚起见，我们在这里使用了一个整数列表，但真实的实现中每个元素只占用一位。同样为了可读性，示例使用大小等于20。典型的真实的生活中的布隆过滤器具有大约9的大小。集合中元素的预期数量的6倍。这给出了约1%的假阳性率。

使用

●网络：Bloom过滤器用于分布式系统中，以检查某个数据是否存在于远程主机上，而无需传输数据。这在内存有限的情况下特别有用，例如网络路由器，网络数据包分析工具和互联网缓存。

●缓存：Bloom过滤器用于在从源检索数据之前快速检查某些数据是否在该高速缓存中。通过使用Bloom过滤器，您可以显着减少磁盘上的负载，同时只花费少量的RAM。例如，如果您想将负载减少10倍，则每个密钥只需要存储大约5位信息。如果你想把它减少100倍，你需要每个密钥大约10位。选择权在你!这个用例的一个众所周知的例子是Cassandra。

●数据库：Bloom过滤器用于在执行更昂贵的操作(如全表扫描)之前检查数据库中是否存在记录。通过使用Bloom过滤器，您可以避免昂贵的操作并加快数据库查询。

●大数据：Bloom过滤器已成为处理大型数据集的系统的首选解决方案。在需要哈希表功能但没有足够空间的情况下，它们的效率使它们成为网络和分布式数据库中的流行选择。例如，Google在其BigTable中使用Bloom过滤器来减少磁盘访问次数。这是因为BigTable本质上是一个很大的、非常稀疏的多维表，所以大多数键都不指向任何东西。

替代方案

Cuckoo Filter和Hyperloglog是Bloom filter的两个替代方案。它们都用于概率集成员测试，并且与Bloom Filter相比具有自己独特的优点和缺点。 让我们从布谷鸟过滤器开始。这个名字的灵感来自于布谷鸟和它的侵略行为，在接管其他鸟类的巢。就像布谷鸟一样，布谷鸟过滤器以其积极利用空间和有效接管内存的能力而闻名。与Bloom过滤器相比，该过滤器被设计为使用更少的空间，但是具有更高的误报率的折衷。 接下来，让我们看看Hyperloglog。Hyperloglog这个名字来源于它使用对数和对数缩放的事实。与Bloom过滤器和Cuckoo过滤器不同，Hyperloglog不是为了测试集合成员关系而设计的，而是为了估计集合的基数。这意味着它可以用来计算集合中唯一元素的数量。Hyperloglog被设计为高度准确，即使是非常大的数据集，但与Bloom过滤器相比，增加了内存使用量。例如，分布式SQL查询引擎Presto使用HyperLogLog来获取单个项目的近似数量。

总结

总之，Bloom过滤器是大数据领域的无名英雄，它为大型数据集中的成员资格检查提供了一种紧凑而高效的解决方案。它巧妙的设计，平衡了准确性和速度，使其成为从网络到分布式数据系统的各个行业的主要产品。由于能够提高系统效率，难怪Bloom过滤器已成为数据工程师和计算机科学专业人员的重要工具。 但是，尽管它的优势，布隆过滤器确实有一些限制，如误报的可能性和无法从集合中删除项目。然而，这些权衡往往被Bloom过滤器带来的好处所抵消。