bitmap 是位运算空间压缩技巧而非 java 集合类；jdk 无现成 bitmap 类，需用 long[] 或 bitset 手动实现；整数 x 映射到第 x/64 个 long 的第 x%64 位，通过 |= (1l
BitMap 本质不是 Java 集合，而是位运算空间压缩技巧
Java 标准库中没有叫 BitMap 的集合类——它是个通用算法思想，不是 ArrayList 或 HashSet 那种开箱即用的容器。你写不出 new BitMap()，得靠 long[] 或 BitSet 手动模拟。很多人卡在这一步：以为要找一个现成类，结果在 JDK 文档里翻半天没找到。
核心逻辑就三行：
- 整数 x 映射到第 x / 64 个 long 元素（因为 1 long = 64 bit）
- 再定位到该 long 的第 x % 64 位
- 用位运算 |= (1L 置 1，用 <code>& (1L 判断是否已存在
常见错误现象：
- 直接用 int 数组存布尔状态 → 内存暴增 32 倍（1 int = 32 bit，但只用 1 bit）
- 忘记处理负数 → BitSet 不支持负索引，long[] 方案会数组越界或位移异常
- 把 1 当成安全操作 → <code>x >= 32 时 1 在 <code>int 下溢出，必须写 1L
用 BitSet 处理 10 亿整数去重：内存够不够？怎么算？
BitSet 是最接近“开箱即用”的选择，但它不是万能的。10 亿个整数，若值域是 [0, 10^9)，那需要约 (10^9 + 63) / 64 ≈ 15.6M 个 long，即约 125 MB 内存（每个 long 8 字节）。这个数字很关键——不是“10 亿字节”，而是“125 MB”。很多人一听说“10 亿”就默认内存爆炸，其实只要值域集中、无稀疏大间隙，完全可行。
实操建议：
- 先确认数据范围：用 min 和 max 估算位图长度，别直接按 max 分配；比如数据全在 [999_999_000, 1_000_000_000) 内，只需 1000 位，不是 10^9 位
- 调用 BitSet.set(int index) 前，确保 index >= 0；负数得做偏移，比如全部 +10^9，再建 BitSet
- 不要用 BitSet.size() 看总容量，它返回的是已分配的位数（可能远大于实际使用），用 BitSet.length() 获取“最高置 1 位的索引+1”更实用
- 如果内存真吃紧（比如只有 64 MB），考虑分段处理：按值域切片，每片建一个 BitSet，最后合并
排序不是 BitMap 的本职，但可以 O(n) 输出有序序列
BitMap 本身不排序，但它天然按位索引升序排列。一旦所有数都 set 进去，遍历 BitSet.nextSetBit(0) 就能顺序拿到最小→最大值，时间复杂度是 O(值域大小)，不是 O(n log n)。对 10 亿个数，如果值域是 [0, 2^31)，那遍历 2^31 次显然不行；但如果实际只用了其中 1000 万个不同值，nextSetBit 只跳这 1000 万次，非常快。
常见陷阱：
- 直接 for 循环从 0 到 bitSet.length() → 即使只存了 10 个数，也要扫几亿次
- 忽略重复值：BitMap 天然去重，但如果你需要保留原始频次，它就不适用，得换 int[] 计数或布隆过滤器+哈希表组合
- 误以为 BitSet.stream() 是懒求值 → 它内部仍是遍历所有位，和手写循环没本质区别，别指望它自动跳过长段 0
示例片段（获取所有已存整数，升序）：
int next = bitSet.nextSetBit(0);<br>while (next != -1) {<br> System.out.println(next);<br> next = bitSet.nextSetBit(next + 1);<br>}
立即学习“Java免费学习笔记（深入）”；
为什么不用 HashSet？对比真实瓶颈在哪
10 亿个 Integer 存 HashSet，光对象头+引用就占至少 8 字节/元素（64 位 JVM 压缩指针关闭），加上哈希表扩容、链表/红黑树结构，轻松突破 8 GB 内存；而 BitMap 只需 ~125 MB。这不是“省一点”，是量级差异。
但代价明确：
- 只支持非负整数，且必须知道大致范围
- 不支持泛型、不能存字符串或自定义对象
- 并发不安全：BitSet 没有原子操作，多线程写要自己加锁或用 AtomicLongArray 手写
- 稀疏数据灾难：如果 10 亿个数实际分布在 [0, Long.MAX_VALUE) 里，BitMap 直接不可用，而 HashSet 至少还能跑（虽然慢）
真正容易被忽略的一点：
BitMap 的“去重”是确定性的，但它的“存在性判断”比 HashSet.contains() 快不了多少（都是 O(1) 常数时间），优势全在空间效率和顺序遍历能力。别为了“听起来快”就硬套，先看你的数据是不是真的适合位映射。
