面试题库 › C++ / 后端 › 大规模布隆过滤器的内存规划与持久化

大规模布隆过滤器的内存规划与持久化

难度 ★★★在 1 场真实面经中被问到 方向:C++ / 后端考点:TopK与海量数据

常见岗位:C/C++ 软件开发

答案要点

  1. 位数组大小 m = -n·ln p / (ln2)²,最优哈希数 k = (m/n)·ln2;十亿元素 1% 误判约需 1.2GB
  2. 持久化需保存位数组及 m、k、哈希函数与种子,保证重启后计算一致
  3. 可用定期快照加增量日志,快照时用写时复制减少对写入的阻塞
  4. 内存不足时用分块布隆过滤器,k 个位落在同一页,一次查询一次 IO,并用 LRU 缓存热块
  5. 置位操作幂等,可用原子或运算处理并发;标准布隆过滤器不支持删除

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题