布隆过滤器的原理
哪些公司问过
答案要点
- 结构:位数组 + k 个哈希函数
- 添加:k 个哈希位置全部置 1;查询:任一位为 0 → 一定不存在,全为 1 → 可能存在
- 有误判(假阳性),无漏判(假阴性);空间效率高,不存元素本身
- 不支持删除(位可能被多个元素共用);可用计数布隆过滤器或布谷鸟过滤器支持删除
- 误判率与 m、n、k 有关;应用:缓存穿透防护、爬虫 URL 去重、垃圾邮件过滤
易错点
- 说布隆过滤器“判断存在就一定存在”:只能说可能存在
- 说它会漏判:只有误判,没有漏判
- 忽略它不能删除
- 没有提容量规划:元素远超预估后误判率会急剧上升
面试官常见追问
- 如何降低布隆过滤器的误判率?
- 布隆过滤器判断存在但数据库其实没有,怎么处理?
- 为什么不支持删除?
- 和哈希表、HashSet 比有什么优势和劣势?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。