概率数据结构
概率数据结构
布隆过滤器是一种概率数据结构，它提供了一种有效的方式来验证一个条目是否肯定不在一个集合中。这使得它在尝试搜索昂贵访问资源（如通过网络或磁盘）上的项目时特别理想：如果我有一个大型磁盘数据库，并且我想知道键foo 是否存在于其中，我可以先查询布隆过滤器，它会告诉我有确定性地确定它是否可能存在（然后可以继续进行磁盘查找）或它是否不存在，在这种情况下，我可以放弃昂贵的磁盘查找，并简单地向堆栈发送一个否定回复。
虽然可以使用其他数据结构（如哈希表）来执行此操作，但布隆过滤器在占用空间方面非常小，每个元素通常以位（而不是字节！）数来衡量。存在一定比例的误报率（可控），但对于集合中是否存在键的初步测试，它们提供了极快的速度，最重要的是极高的空间效率。
布隆过滤器被广泛应用于各种应用中，例如广告投放 - 确保用户不会太频繁地看到广告；类似地，在内容推荐系统中 - 确保推荐不会出现得太频繁，在数据库中 - 快速检查表中是否存在条目，然后再从磁盘上访问它，等等。
布隆过滤器的工作原理
大多数关于布隆过滤器的文献都使用高度符号化和/或数学描述来描述它。如果您像我一样对数学不太擅长，您可能会发现我的解释更有用。
布隆过滤器是一个由许多位组成的数组。当将一个元素“添加”到布隆过滤器时，该元素被哈希化。然后，bit[hashval % nbits]被设置为1。这看起来与哈希表中存储桶的映射方式非常相似。为了检查一个项目是否存在，计算其哈希值，并检查过滤器中相应位是否被设置。
当然，这会受到冲突的影响。如果发生冲突，过滤器会返回一个误报 - 表明条目确实被找到（注意，布隆过滤器永远不会返回一个误报，也就是说，它不会声称一个不存在的东西实际上存在）。
为了降低发生冲突的风险，一个条目可以使用多个位：该条目被哈希化bits_per_element (bpe)次，每次迭代使用不同的种子生成不同的哈希值，并且对于每个哈希值，设置相应的hash % nbits位。为了检查条目是否存在，候选键也被哈希化bpe次，如果任何相应的位被取消设置，那么就可以确定地判断该项目不存在。
bpe的实际值是在创建过滤器时确定的。通常，每个元素的位数越多，误报的可能性就越低。
在上面的例子中，所有三个位都需要被设置，以便过滤器返回一个正值。
另一个影响布隆过滤器精度的值是其填充率，即过滤器中实际上被设置的位数。如果过滤器中大多数位都被设置，则任何特定查找返回 false 的可能性会降低，因此过滤器返回误报的可能性会增加。
可扩展的布隆过滤器
通常，布隆过滤器必须在事先知道要包含多少个条目时创建。bpe数需要固定，同样，位数组的宽度也需要固定。与哈希表不同，布隆过滤器不能被“重新平衡”，因为没有办法知道哪些条目是过滤器的一部分（过滤器只能确定给定条目是否不存在，但它不会实际存储存在的条目）。
为了使布隆过滤器能够“扩展”并能够容纳比设计数量更多的元素，它们可以被堆叠。一旦单个布隆过滤器达到容量，就会在其上创建一个新的过滤器。通常，新过滤器的容量比之前的过滤器更大，以降低需要堆叠另一个过滤器的可能性。
在可堆叠（可扩展）的布隆过滤器中，检查成员资格现在涉及检查每一层是否存在。添加新项目现在涉及检查它是否事先存在，并将其添加到当前过滤器中。然而，哈希仍然只需要计算一次。
在创建布隆过滤器时 - 即使是可扩展的布隆过滤器，也要了解它预期包含多少个项目。初始层只能包含少量元素的过滤器会显著降低性能，因为它需要更多层才能达到更大的容量。