假设你正在 Geekbook 上注册一个账号，想输入一个很酷的用户名。当你输入完后，系统提示“该用户名已被占用”。你又加上了生日，依然不行。接着你加上了大学学号，但还是收到“该用户名已被占用”的提示。这真的很令人沮丧，不是吗？
但你有没有想过，Geekbook 是如何在数百万个已注册的用户名中如此迅速地检查可用性的呢？有许多方法可以完成这项工作 ——
- 线性搜索 ：是个坏主意！
- 二分查找 ：按字母顺序存储所有用户名，将输入的用户名与列表中间的那个进行比较。如果匹配，则说明用户名已被占用；否则，判断输入的用户名应该在中间那个之前还是之后。如果在之后，则忽略中间（包括中间）之前的所有用户名。现在在中间之后继续搜索，重复此过程，直到找到匹配项或搜索结束未找到匹配项。这种技术更好且更有希望，但它仍然需要多个步骤。
但是，一定有更好的办法！！
布隆过滤器 是一种可以完成这项工作的数据结构。它本质上是一种空间优化的 哈希 版本，其中可能存在误报。其核心思想是不存储实际的键，而是只存储哈希值。它主要是一种概率性和空间优化的哈希技术，对于 1% 的误报率，每个键只需要不到 10 个比特，并且这独立于单个键的大小。
什么是布隆过滤器？
布隆过滤器是一种 节省空间的概率性 数据结构，用于测试一个元素是否是集合的成员。例如，检查用户名的可用性就是一个集合成员判定问题，这里的集合是所有已注册用户名的列表。我们为效率所付出的代价是它是概率性的，这意味着可能会产生一些 误报 结果。误报的意思是，它可能会提示给定的用户名已被占用，但实际上并没有。
布隆过滤器的有趣特性
- 与标准的哈希表不同，固定大小的布隆过滤器可以表示具有任意数量元素的集合。
- 添加元素永远不会失败。然而，随着元素的添加，误报率会稳步上升，直到过滤器中的所有位都被设置为 1，此时所有查询都会返回肯定结果（即都认为存在）。
- 布隆过滤器绝不会产生 假阴性 结果，即当用户名实际存在时，却告诉你它不存在。
- 无法从过滤器中删除元素，因为如果我们通过清除由 k 个哈希函数生成的索引处的位来删除单个元素，可能会导致其他几个元素也被删除。例如 – 如果我们要通过清除索引 1、4 和 7 处的位来删除“geeks”（在下面的示例中），我们可能最终把“nerd”也删掉了。因为索引 4 处的位变成了 0，布隆过滤器就会声称“nerd”不存在。
布隆过滤器的工作原理
一个空的布隆过滤器是一个有 m 个比特的 位数组，所有位都设置为零，就像这样 ——
!<a href="https://media.geeksforgeeks.org/wp-content/uploads/enptybitarray-300×56.png">emptybitarray
我们需要 k 个 哈希函数 来计算给定输入的哈希值。当我们想要向过滤器中添加一个项目时，我们需要将 k 个索引 h1(x), h2(x), … hk(x) 处的位设置为 1，其中这些索引是通过哈希函数计算出来的。
示例 – 假设我们要向过滤器中输入“geeks”，我们使用 3 个哈希函数和一个长度为 10 的位数组，最初所有位都设置为 0。首先，我们将计算哈希值如下：
h1(“geeks”) % 10 = 1
h2(“geeks”) % 10 = 4
h3(“geeks”) % 10 = 7
注意： 这些输出只是为了解释说明而随机生成的。
现在我们将索引 1、4 和 7 处的位设置为 1
我们要再次输入“nerd”，同样，我们将计算哈希值：
h1(“nerd”) % 10 = 3
h2(“nerd”) % 10 = 5
h3(“nerd”) % 10 = 4
将索引 3、5 和 4 处的位设置为 1
!nerd
现在，如果我们想检查“geeks”是否存在于过滤器中。我们将执行同样的过程，但这次顺序是相反的。我们使用 h1、h2 和 h3 计算相应的哈希值，并检查位数组中所有这些索引是否都被设置为 1。如果所有的位都被设置了，那么我们可以说“geeks” 大概率存在。如果这些索引中任何一个位是 0，那么“geeks” 绝对不存在。
布隆过滤器中的误报
问题来了，为什么我们要说 “大概率存在”，为什么会有这种不确定性？让我们通过一个例子来理解。假设我们要检查“cat”是否存在。我们将使用 h1、h2 和 h3 计算哈希值：
h1(“cat”) % 10 = 1
h2(“cat”) % 10 = 3
h3(“cat”) % 10 = 7