布隆过滤器(Bloom Filter)

定义

布隆过滤器是一种空间高效的概率型数据结构，用来判断一个元素是否在集合中。它可能产生假阳性（误判存在），但绝不会产生假阴性（判断不存在则一定不存在）。

原理

它由一个位数组和 k 个独立哈希函数组成。插入元素时，用 k 个哈希函数算出 k 个位置并全部置 1。查询时同样计算 k 个位置，若有任一位为 0 则元素一定不存在；若全为 1 则可能存在。随着插入元素增多，置 1 的位越来越多，误判率上升。标准布隆过滤器不支持删除，可改用计数布隆过滤器。

复杂度

• 插入：O(k)
• 查询：O(k)
• 空间复杂度：远小于直接存储所有元素

应用场景

• 缓存穿透防护
• 爬虫 URL 去重
• 数据库与存储引擎的存在性预判
• 垃圾邮件与黑名单过滤