布隆过滤器

布隆过滤器被定义为一种数据结构,旨在以快速且高效存储的方式识别一组元素的存在。

被称为概率数据结构的特定数据结构被实现为布隆过滤器。这种数据结构有助于我们识别某个元素在集合中存在或不存在。

位向量被实现为基本数据结构。 这是我们用来解释的一小部分

123456789101112131415

该表中的每个空白单元格都指定一个位及其下方的数字及其索引或位置。要将元素附加到Bloom过滤器,我们只需对其进行哈希处理几次,然后将这些哈希的位置或索引处的位向量中的位设置为1。

下面讨论了Bloom Filter的详细实现

布隆过滤器支持两种动作,首先是附加对象并跟踪对象,然后是验证以前是否曾见过对象。

将对象追加到Bloom过滤器

  • 我们计算要附加的对象的哈希值;

  • 我们实现这些哈希值以将某些位设置为Bloom过滤器状态(哈希值是要设置的位的位置)。

验证Bloom过滤器是否包含对象-

  • 我们计算要附加的对象的哈希值;

  • 接下来,我们验证是否将这些哈希值索引的位设置为布隆过滤器状态。

我们必须记住,对象的哈希值不会直接附加到Bloom过滤器状态;每个哈希函数仅确定要设置或验证的位。例如:如果仅使用一个哈希函数,则仅验证或检查一位。

以上是 布隆过滤器 的全部内容, 来源链接: utcz.com/z/321645.html

回到顶部