日期：2026-07-11
标签：#面试 #八股 #后端 #Bitmap #场景题
一句话答案
普通 Bitmap 空间取决于最大 ID 而不是元素个数，100 个极稀疏大 ID 会浪费巨量空间；可用 HashSet、RoaringBitmap、分段位图或坐标压缩解决。
面试口语版
普通 Bitmap 直接用 ID 当 bit 下标，如果最大 ID 是 10^12，即使只有 100 个用户也需要约 125GB，所以不适合稀疏大值域。只存 100 个 ID 最简单是 HashSet 或排序数组；若仍需要集合交并和压缩位图能力，可用 RoaringBitmap，它按高位分桶，桶内根据密度选择数组容器、位图容器或运行长度编码。数据集固定时还可以把 100 个 ID 排序后映射到 0～99 做坐标压缩，但要保存映射。
方案对比
| 方案 | 优点 | 适用场景 |
|---|---|---|
| HashSet | 简单、稀疏友好 | 小集合、点查询 |
| 排序数组 | 紧凑、可二分 | 读多写少 |
| RoaringBitmap | 压缩且集合运算快 | 大规模稀疏/稠密混合 |
| 坐标压缩 | 极省空间 | ID 集合固定或可维护映射 |
关键细节
- 分段位图只为出现的高位段分配底层块。
- Bloom Filter 更省空间但有假阳性，不能替代精确集合。
- 选择方案还要看增删频率、集合运算和序列化需求。
面试官追问
- RoaringBitmap 为什么适合稀疏数据？
- 坐标压缩有什么限制？
- Bloom Filter 可以替代吗？
面试官追问参考答案
1. RoaringBitmap 为什么适合稀疏数据？
它按高位划分 16 位低位容器，稀疏容器只保存排序整数，稠密后切换为固定 Bitmap，还可对连续区间使用 Run 容器，因此不会按全局最大 ID 分配整个位图。
2. 坐标压缩有什么限制？
需要维护原 ID 到紧凑下标的映射；新增任意 ID 时可能重建或使用动态映射，多集合之间若映射不同就不能直接做位运算。适合静态或批处理数据，不一定适合高频在线新增。
3. Bloom Filter 可以替代吗？
若只需快速判断“肯定不存在/可能存在”可以，但它有假阳性，不能精确枚举元素或直接做严格去重。要求精确成员关系时仍需 HashSet 或压缩位图。
学习清单
- 理解位图空间由值域决定。
- 能比较 HashSet、RoaringBitmap 与坐标压缩。
Maintained by · YihuiEdit on GitHub