有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步,认准https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。 https://store.amazingmemo.com/chapterDetail/1685324709017001`

布隆过滤器（Bloom Filter）

布隆过滤器是一种空间效率极高的概率型数据结构，用于判断一个元素是否在一个集合中。它的特点是高效地插入和查询，但是有一定的误判率。换句话说，布隆过滤器可能会告诉你一个元素在集合中，即使它实际上不在（假阳性），但它绝不会告诉你一个元素不在集合中，如果它实际上是在的（无假阴性）。

布隆过滤器的底层原理

布隆过滤器背后的核心原理是使用多个哈希函数对元素进行处理，并将结果映射到一个固定大小的位数组中。

工作流程

1. 初始化：创建一个m位的位数组（bit array），所有位初始值为0，以及k个哈希函数。
2. 添加元素：当添加一个元素时，将该元素通过k个哈希函数进行哈希，得到k个数组位置，将这些位置的位都设为1。
3. 查询元素：当查询一个元素是否存在时，同样通过k个哈希函数得到k个数组位置，如果所有这些位置的位都是1，则认为该元素可能存在；如果任何一个位不是1，则该元素一定不存在。

误判率

布隆过滤器的误判率取决于位数组的大小、哈希函数的个数以及插入的元素数量。可以通过调整这些参数来平衡误判率和空间效率。

布隆过滤器的应用场景

布隆过滤器因其高效和空间节省的特性，在很多场景下都非常有用：

网络系统

• Web缓存：判断一个资源是否被缓存。
• 分布式系统：快速检查分布式存储系统中一个数据是否存在，以减少不必要的数据传输。

数据库

• 数据库索引：用于快速判断数据是否存在于某个数据库表中，减少磁盘I/O操作。
• Anti-Caching：在内存数据库中判断数据是否被逐出到磁盘。

网络爬虫

• URL去重：检查一个URL是否已经被爬取过，以避免重复处理。

广告系统

• 广告过滤：快速检查用户是否已经看过某个广告，以决定是否展示新广告。

安全领域

• 恶意URL检测：检查URL是否在已知的恶意网站列表中。
• 垃圾邮件过滤：检查邮件特征是否匹配已知的垃圾邮件特征。

其他

• 比特币网络：用于比特币网络中的轻量级节点，快速检查交易是否存在。
• 分布式系统的数据同步：检查数据是否已经同步到其他节点。

总结

布隆过滤器是一个非常实用的数据结构，尤其适合于那些可以容忍一定误判率的场景。通过合理选择参数，布隆过滤器可以在保持较低误判率的同时，显著减少内存的使用，提高系统的性能。然而，需要注意的是，布隆过滤器不支持从集合中删除元素，这是因为将位设置回0可能会影响其他元素的判断。如果需要删除功能，可以考虑使用布隆过滤器的变种，如计数布隆过滤器。