前言
本文是作者专门用来自测Java后端相关面试题的，所有问题都是在牛客、知识星球或网上找到的最近最新的面试题，全文回答都是作者按自己的真实水平仿照真实环境的回答，所以答案不一定真实（但回答一定真诚🤣），其他即将面试的小伙伴可以试试自测一下💪
布隆过滤器是什么
布隆过滤器（Bloom Filter）是一种空间效率很高的概率型数据结构，用于判断一个元素是否在一个集合中。它由Bruce Bloom在1970年提出，主要用于解决在大规模数据集中快速判断元素是否存在的问题。布隆过滤器的核心思想是允许一定的误判率（false positive），以换取更快的查询速度和更小的存储空间。
布隆过滤器的主要特点包括：
-
高效空间利用：
布隆过滤器使用位数组（bit array）来存储数据，相比于其他数据结构，它在存储空间上非常高效。 -
快速查询：
布隆过滤器的查询时间复杂度为O(k)，其中k是哈希函数的数量。由于k通常是一个较小的常数，这使得布隆过滤器的查询速度非常快。 -
不存在误判：
如果布隆过滤器判断一个元素不存在，那么该元素一定不在集合中，即不存在false negative。 -
存在误判：
布隆过滤器可能存在false positive，即判断一个元素存在，但实际上该元素不在集合中。但不存在false negative，即如果布隆过滤器说一个元素不存在，那么它就真的不存在。 -
不可删除：
布隆过滤器一旦添加了元素，就无法删除，因为删除操作可能会影响其他元素的判断结果。
布隆过滤器的工作原理是通过多个哈希函数将元素映射到位数组中的多个位置，并设置这些位置的值为1。查询时，如果所有对应的位置都为1，则认为元素可能存在；如果任何一个位置为0，则元素一定不存在。
布隆过滤器的应用场景包括：
-
缓存优化：
用于减少对数据库或缓存的访问次数，提高系统性能。 -
大数据去重：
在处理大规模数据流时，用于快速识别重复的数据项。 -
网络爬虫：
用于快速判断URL是否已经被访问过。 -
分布式系统中的数据同步：
用于减少不必要的数据传输。
布隆过滤器是一种在空间和时间效率之间做出权衡的数据结构，适用于那些可以容忍一定误判率的场景。
布隆过滤器原理
布隆过滤器的原理基于哈希函数和位数组的结合使用。它的核心思想是使用多个哈希函数将一个元素映射到位数组中的多个位置，并在这些位置上标记（通常是将位设置为1）。以下是布隆过滤器工作原理的详细步骤：
-
初始化：
布隆过滤器开始时是一个具有固定大小的位数组，初始状态全部为0。同时，布隆过滤器预设了k个不同的哈希函数。 -
添加元素：
当向布隆过滤器中添加一个元素时，这k个哈希函数会分别作用于该元素，产生k个哈希值，这些哈希值对应于位数组中的k个位置。然后将这些位置上的位设置为1。 -
查询元素：
当查询一个元素是否存在时，同样使用这k个哈希函数计算出k个哈希值，并查看位数组中对应的k个位置是否都为1。如果所有位置都为1，则认为元素可能存在于集合中；如果任何一个位置为0，则元素肯定不在集合中。 -
误判情况：
由于哈希函数的随机性和有限的位数组大小，不同的元素可能会映射到位数组的同一位置，这可能导致误判。即，一个元素查询结果为可能存在，但实际上它从未被添加到布隆过滤器中（false positive）。然而，如果布隆过滤器确定一个元素不存在，那么它就真的不存在（不存在false negative）。 -
参数调整：
布隆过滤器的性能可以通过调整位数组的大小、哈希函数的数量以及添加的元素数量来优化。这些参数会影响误判率和存储效率。
布隆过滤器的优势在于它的空间效率和查询速度，但它的缺点是不能精确地确定元素是否存在，且不能删除元素。因此，它适用于那些可以容忍一定误判率的场景，并且不需要从集合中删除元素的应用。
