大规模布隆过滤器的内存规划与持久化
答案要点
- 位数组大小 m = -n·ln p / (ln2)²,最优哈希数 k = (m/n)·ln2;十亿元素 1% 误判约需 1.2GB
- 持久化需保存位数组及 m、k、哈希函数与种子,保证重启后计算一致
- 可用定期快照加增量日志,快照时用写时复制减少对写入的阻塞
- 内存不足时用分块布隆过滤器,k 个位落在同一页,一次查询一次 IO,并用 LRU 缓存热块
- 置位操作幂等,可用原子或运算处理并发;标准布隆过滤器不支持删除
易错点
- 持久化只存位数组,不存哈希函数和参数,重启后无法正确查询
- 将普通布隆过滤器整体放到磁盘,每次查询产生 k 次随机 IO
- 元素数量远超设计容量仍继续使用,误判率失控
面试官常见追问
- 布隆过滤器需要删除怎么办?
- 元素数量超出预估怎么办?
- 能不能直接用 Redis 做大规模布隆过滤器?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。