后端岗位面试题更新 2026-08-05

给定约400亿个整数,如何用位数组(位图)快速判断某个数是否存在?并说明内存占用和适用边界。

知乎后端开发互联网/IT性能优化技术原理方案权衡

考察说明

考察位图思想在大规模数据集合判重中的应用与内存估算

回答思路

  1. 说明位图的核心原理:每个数映射到1个bit表示存在性
  2. 准确估算400亿个数对应位图所需内存(约5GB)
  3. 讨论位图适用条件:取值范围有限且可接受散列映射
  4. 提及扩展:布隆过滤器处理取值范围过大时的替代
  5. 指出局限:位图无法直接支持删除或计数