Bitmap 存 100 个用户 ID，但 ID 范围很大，有什么问题？如何解决？

日期：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 与坐标压缩。