布隆过滤器

布隆过滤器（Bloom Filter）是一种空间效率高、时间效率快的概率型数据结构，主要用于判断一个元素是否属于一个集合

它是由布隆（Burton Howard Bloom）在1970年提出的，用于解决大规模数据集合的查找效率问题。

1、位数组：布隆过滤器使用一个长度为 m 的位数组，初始化时所有位都设为 0。

2、多个哈希函数：布隆过滤器使用 k 个不同的哈希函数，每个哈希函数可以将输入元素映射为位数组中的一个位置。

3、插入操作：当一个元素被插入时，通过 k 个哈希函数计算出 k 个哈希值，将对应的位数组位置设置为 1。

4、查询操作：当查询一个元素是否在布隆过滤器中时，同样通过 k 个哈希函数计算出 k 个哈希值，检查对应的位数组位置是否都为 1。

如果都为 1，则可能存在于集合中；如果有任何一个位置为 0，则肯定不存在于集合中。

由于可能存在哈希冲突，布隆过滤器具有一定的误判率。但在实际应用中，这一误判率可以通过调整位数组的长度 m 和哈希函数的数量

k 来进行控制。

1、空间效率高：布隆过滤器占用的空间相比于其他数据结构（如散列表）较小。

2、查询效率高：查询一个元素是否存在时，时间复杂度是常量级别，与集合大小无关。

3、支持动态扩容：可以动态调整位数组的大小。

1、缓存击穿问题：用于缓存查询，避免因为缓存失效而导致数据库等后端系统压力过大。

2、防止爬虫重复爬取：用于存储已经爬取过的 URL，防止爬虫重复抓取相同的页面。

3、黑名单过滤：用于存储一些可能的非法或恶意的数据，例如IP地址、URL等。

caution

需要注意的是，布隆过滤器在删除元素的操作上存在困难，因为删除一个元素可能会影响到其他元素的判断结果。

因此，通常情况下，布隆过滤器主要用于支持元素的插入和查询操作。