布隆过滤器

布隆过滤器被定义为一种数据结构，旨在以快速且内存高效的方式识别元素是否在一个集合中存在。

布隆过滤器实现了一种名为**概率数据结构**的特定数据结构。这种数据结构帮助我们识别一个元素是存在还是不存在于一个集合中。

**位向量作为基础数据结构实现。** 以下是一个我们将用来解释的小例子

表中的每个空单元格指定一个位，下面的数字是其索引或位置。要将元素追加到布隆过滤器中，我们只需对其进行几次哈希运算，并将位向量中这些哈希值的位置或索引处的位设置为 1。

布隆过滤器的详细实现将在以下内容中讨论

布隆过滤器支持两种操作，首先是追加对象并跟踪对象，其次是验证之前是否已见过某个对象。

将对象追加到布隆过滤器

• 我们计算要追加的对象的哈希值；
• 我们使用这些哈希值来设置布隆过滤器状态中的某些位（哈希值是要设置的位的位置）。

验证布隆过滤器是否包含某个对象 -

• 我们计算要追加的对象的哈希值；
• 接下来，我们验证布隆过滤器状态中这些哈希值索引的位是否已设置。

我们必须记住，对象的哈希值不会直接追加到布隆过滤器状态；每个哈希函数仅确定要设置或验证哪个位。例如：如果只使用一个哈希函数，则只验证或检查一个位。

Arnab Chakraborty

更新于： 2020年1月3日

3K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

开始学习