请解释布隆过滤器的工作原理和优缺点。
简答题
请解释布隆过滤器的工作原理和优缺点。
答案：布隆过滤器通过一个很长的二进制向量和一系列随机映射函数记录元素是否在集合中。查询时，若元素映射的位都为1，则可能存在；若有0，则一定不存在。优点：占用内存小、查询效率高、不需要存储元素本身。缺点：有一定误判率（假阳性）、不能获取元素本身、一般不能删除元素。
解析
参考答案
- 原理：用位数组和多个哈希函数记录元素。查询时映射位全为 1 则“可能存在”，有 0 则“一定不存在”。
- 优点：内存占用小、查询和插入效率高、不存储元素本身。
- 缺点：存在假阳性误判；一般不能删除元素；无法获取元素本身。
得分点解析
- 位数组加哈希函数：这是核心结构，决定布隆过滤器只能判断“可能存在/一定不存在”，而非精确存在。
- 内存小、效率高：体现其适合海量数据判重、缓存穿透防护、URL 去重等场景。
- 误判、不能删除：明确使用边界。删除某元素可能把其他元素映射位清零，导致漏判，需用计数布隆等变体。
延伸
实际需权衡位数组长度与哈希函数个数；位太少误判率高，哈希太多则效率下降。