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