1. 什么是布隆过滤器

以下定义来至百度百科：

  • 布隆过滤器（英语：Bloom Filter）是1970年由伯顿·霍华德·布隆（Burton Howard Bloom）提出的。它实际上是由一个很长的二进制向量和一系列随机映射函数组成的。布隆过滤器可以用于检索一个元素是否在一个集合中。 它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。

由此我们可知布隆过滤器主要由两个部分组成：位数组和多个映射函数（哈希函数）。

  • 位数组：初始化为一组固定长度的二进制位（默认全为 0）。
  • 哈希函数：使用多个独立的哈希函数（如 k 个），对输入元素进行哈希处理，生成 k 个哈希值。

Bloom Filter 使用一个较大的bit数组进行保存所有的数据，数组中的每个元素都只占用1 bit，并且每个元素只能是 0 或者 1，这也是布隆过滤器节省内存的核心所在。
我们设想1000w个元素，它只需要 1000000Bit / 8 = 125000 Byte = 125000 / 1024 KB ≈ 122 KB 的空间。显然它非常的节省内存，但是如果所有的二进制位数全部占完，接下不管来什么它都会返回1，也就是说添加到集合中的元素越多，误报的可能性就越大

2. 布隆过滤器的原理介绍

插入操作：

  1. 当插入一个元素时，使用 k 个哈希函数计算出 k 个哈希值。
  2. 将这 k 个哈希值对应的位数组的索引位置设置为 1。

如上图所示，当输入一个“hello”，预设3个哈希函数，将输出2，5，6，我们把相应位置为 1。假设另一个输入“word”，哈希函数输出6，9，10。此时你应该注意到，索引6已经被先前的“hello”标记了。此时，我们已经使用了”hello“和”word”两个输入值，填充了位向量，当前向量的标记状态为：

查询操作：

  1. 当查询一个元素是否在集合中时，使用相同的 k 个哈希函数计算出 k 个哈希值。
  2. 检查这 k 个位置的值：
    • 如果所有对应的位都是 1，则该元素可能在集合中（可能误判）。
    • 如果任何一个位为 0，则该元素肯定不在集合中。

前面我们已经添加了两个输入值，这时我们使用3个哈希函数对“搜索的值”进行哈希函数，并查看其生成的索引值。假设，当我们搜索“java”时，3个哈希函数输出的3个索引值分别是5，6，9：

从上图我们可以发现，相应的索引位都被置位 1 ，这意味着我们可以说“java”可能已经插入到集合中。当然明显这是错误的的，产生的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。好在布隆过滤器有个可预测的误判率（FFP）：

  • n 是已经添加的元素的数量
  • k 是哈希的次数
  • m 布隆过滤器的长度（如比特数组的大小）

有上可知，在极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 m 需要远远大于 n 。

实际情况中，布隆过滤器的长度 m 可以根据给定的误判率（FFP）的和期望添加的元素个数 n 的通过如下公式计算：

了解完上述的内容，我们可以得出一个结论：当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。

3. 优缺点

  • 优点：

    • 空间效率高：相对于存储实际元素，布隆过滤器所需的内存占用非常少，适合处理大规模数据。
    • 快速查询：布隆过滤器的查询操作时间复杂度为 O(k)，k 通常是一个小的常数，因此查询速度非常快。

  • 缺点：

    • 误判：布隆过滤器可能会误判元素存在（即返回 true 的情况下，元素实际上不在集合中），无法准确判断。
    • 无法删除：标准的布隆过滤器不支持删除操作，因为删除某个元素可能会影响其他元素的存在性判断。

4. 应用场景

布隆过滤器广泛应用于许多场景，特别是在需要快速判断元素存在性且资源有限的情况下，例如：

  • 网络爬虫：用于判断 URL 是否已被访问，避免重复抓取。
  • 数据库：在执行查询前先检查数据是否存在，以减少对数据库的无效请求。（针对解决缓存穿透的问题）
  • 分布式系统：在分布式缓存中使用，减少跨节点的请求。
  • 大数据处理：在数据流处理和实时分析中，快速判断数据是否已处理。

5. 总结

布隆过滤器是一种非常实用的数据结构，尤其适用于高效存储和查询大规模数据。尽管它存在误判的风险，但在许多场景中，其空间和时间效率使其成为一种理想的选择。在实际应用中，合理配置哈希函数和位数组的大小，可以有效控制误判率，进一步提升布隆过滤器的性能。