1 简介

布隆过滤器是一种节省空间的方式,用来存储有关键列表的信息。
在其中，有一个位图和一个哈希函数。

计算存储在 SST 中的键的哈希值，并将结果用于将位图中的某些位设置为“1”。当您想知道列表中是否存在某个键时，您可以通过哈希函数运行它并检查位图中的相应位是“1”还是“0”。

如果其中一个位是“0”，您确定该密钥不在列表中。如果所有位均为“1”，则可能存在该值。误报的概率仅取决于几个因素：

位图的大小
列表中的键数
每个键值设置为“1”的位数

布隆过滤器是具有空间效率和概率性的独特属性的数据结构。我们将在博客后面详细介绍这两个属性。

2 两个概念

为了更好地了解布隆过滤器，让我们阅读布隆过滤器所依赖的 2 个概念。

• 位数组

它是一种数组数据结构，其中仅存储布尔值。它用于将位数组中某个域的值与 {0， 1} 映射

    []  []  []  []  []
     1   2   3   4   5

• 哈希函数
  哈希函数与任何其他函数一样，接受输入并应用一些算法将输入更改为称为哈希值的输出。

  输入 --> 哈希函数 SHA-1 ---> 哈希值

哈希值有多种应用，最常见的应用之一是将哈希值存储在哈希表中以加快检索速度。应用于转换输入的算法的一个示例是 SHA-1。

哈希函数的特性使其成为将其用于布隆过滤器的理想选择：

无论输入是什么，输出的长度都保持不变。
每次传递相同的输入时，它都会给出相同的输出。
您可以阅读有关哈希函数的更多信息这里打开一个新窗口.

3 它是如何工作的？

为了了解布隆过滤器的工作原理，让我们举一个用例，我们想在位数组中存储单词“Marvel”。

让我们将其工作分解为几个步骤。

初始化位数组。
将参数传递到一组哈希函数中。
收集每个哈希函数的输出。
应用一些数学逻辑来获取要更新的位，在我们的例子中，我们使用模运算。
使用值 1 更新上一步中获得的位。
让我们看一下图表，看看同样的过程在运行。

我们已经初始化了大小为 100 的位数组，默认值为 0。

[] [] [] ... []
 1  2  3     100

将参数传递给一组哈希函数。 函数进行一些输出

输入 --->  哈希函数  ---> 4456326
    --->  哈希函数   ---> 4456326
    ...

现在我们将模运算应用于哈希函数的每个输出，我们将通过位数组的大小对其进行调制。

这些是我们需要更新以将“Marvel”存储在位数组中的位。

[1] [0] [1] [1] [0] [0] [0] [0] [0] [0]
 1   2   3   4   5   6   7   8   9   10

4 小结

在布隆过滤器的哈希函数将键映射到位图的特定位置，设置为1。

查询时，通过同样哈希函数检查位图，全1则可能存在，有0则肯定不存在。

误报概率与位图大小、键数量和哈希位数相关。其工作流程包括初始化位数组、应用哈希函数、更新位数组。

布隆过滤器在存储和查找时利用位数组和哈希函数的特性，实现概率性查找。

现在，如果我们想在布隆过滤器中搜索任何单词，我们遵循相同的过程，除了不是用 1 更新位，而是在这些位中获取存储的值，如果所有值均为 1，则意味着该元素存在于集合中。