概率数据结构
概率数据结构
| Redis 堆栈 |
|---|
Bloom 过滤器是一种概率数据结构，它提供 验证条目是否肯定不在集合中的有效方法。这 使其在尝试搜索 项目时特别理想 昂贵的访问资源（例如通过网络或磁盘）：如果我 有一个大型磁盘数据库，我想知道键 foo 是否存在 在其中，我可以先查询 Bloom 筛选器，它通过 确定它是否存在（然后磁盘查找可以 continue），或者它不存在，在这种情况下，我可以放弃 昂贵的磁盘查找，然后简单地在堆栈上发送否定回复。
虽然可以使用其他数据结构（例如哈希表） 为了实现这一点，Bloom 过滤器也特别有用，因为它们 每个元素占用的空间非常小，通常以位数（不是字节数）计算。存在一定百分比的误报 （这是可控的），但用于 key 是否存在的初始测试 在一组中，它们提供了出色的速度，最重要的是出色的 空间效率。
Bloom filters 用于各种应用程序，例如广告 Serving - 确保用户不会太频繁地看到广告;同样在 内容推荐系统 - 确保推荐不会显示 在数据库中，快速检查条目是否存在于 表，然后在磁盘上访问它，依此类推。
Bloom 滤镜的工作原理
大多数关于 Bloom filter 的文献都使用高度符号和/或 数学描述来描述它。如果你在数学上 像你一样受到挑战，你可能会发现我的解释更有用。
Bloom 过滤器是一个包含许多位的数组。当元素被 “添加” 到 bloom filter，则元素会进行哈希处理。那么 bit[hashval % nbits] 是 设置为 1。这看起来与哈希表中的存储桶非常相似 映射。要检查项目是否存在，将计算哈希值，然后 filter 查看是否设置了相应的 bit。
当然，这很容易发生冲突。如果发生冲突， filter 返回误报 - 指示条目为 确实找到（请注意，布隆过滤器永远不会返回 false 否定的，即当某物成为事实时，声称某物不存在 存在）。
为了降低冲突风险，一个条目可能会使用超过 1 位：条目经过哈希 bits_per_element （BPE） 次，其中 每次迭代的种子不同，导致哈希值不同， 对于每个哈希值，设置相应的哈希 % nbits 位。自 检查是否存在条目，候选 key 也是经过 BPE 次哈希处理的， 如果任何相应的位未设置，则可以用 确定该项目不存在。
bpe 的实际值是在过滤器 创建。通常，每个元素的位数越多，可能性就越低 的误报。
在上面的示例中，需要按顺序设置所有三个位 filter 返回正结果。
影响 Bloom 过滤器准确性的另一个值是其填充 ratio，或者 filter 中实际设置的位数。如果过滤器具有 绝大多数位集，任何特定查找的可能性 返回 false 会减少，因此过滤器的可能性也会降低 返回的误报数会增加。
可扩展的 Bloom 过滤器
通常，创建 Bloom 过滤器时必须预先知道有多少 条目。bpe 编号需要固定，并且 同样，位数组的宽度也是固定的。 与哈希表不同，Bloom 过滤器不能“再平衡”，因为存在 无法知道哪些条目是过滤器的一部分（过滤器可以 仅确定给定条目是否不存在，但 Does Not 实际存储存在的条目）。
为了允许 Bloom 过滤器 “扩展” 并能够容纳 元素数量多于其设计目标，则它们可能会堆叠。一旦 单个 Bloom 过滤器达到容量，则会在其上创建一个新过滤器。 通常，新过滤器的容量比以前的过滤器大 一个以减少需要堆叠另一个的可能性 滤波器。
在可堆叠（可扩展）Bloom 过滤器中，现在检查成员资格 涉及检查每一层是否存在。立即添加新项目 包括事先检查它是否存在，并将其添加到 当前筛选器。但是，哈希仍然只需要计算一次。
创建 Bloom 过滤器时 - 即使是可扩展的过滤器，重要的是 清楚地知道它应该包含多少项。过滤器 其初始层只能包含少量元素 性能会显著降低，因为它需要更多的层才能 达到更大的容量。