海量数据判断是否存在:位图与布隆过滤器
哪些公司问过
答案要点
- 位图:每个整数对应一位,存在置 1;查询 O(1)
- 一亿 QQ 号用约 40 亿位(约 500MB);50 亿个整数约 600MB,在内存限制内
- 内存更紧或元素不是整数:布隆过滤器,节省空间,有误判无漏判
- 分治:按哈希值把数据分到多个小文件,分别处理
- 位图适合范围可控的整数;元素非整数则先哈希
易错点
- 位图空间估算错,忘了除以 8
- 对非整数、范围很大的数据直接用位图
- 把布隆过滤器的误判说成漏判
- 没有考虑数据分布导致哈希分片不均
面试官常见追问
- 位图的空间怎么估算?
- 位图和布隆过滤器有什么区别?
- 数据量太大放不进内存怎么办?
- 如何用位图找出不重复的数或做去重?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。