BitSet位图算法如何实现海量数据清洗中的超低内存去重过滤？

本文共计933个文字，预计阅读时间需要4分钟。

BitSet 不能直接用于海量数据。

BitSet.set(x) 为什么会 OOM？不是说它省内存吗

省的是有效数据所占的位空间，不是“按需分配”。BitSet 底层是 long[]，调用 set(1_000_000_000) 时，它必须确保索引 10⁹ 能被容纳，即至少分配 ⌈10⁹ / 64⌉ ≈ 15.6M 个 long，约 125 MB 连续堆内存。如果最大 ID 是 10 亿但只用了 1000 个，这 125 MB 仍全量分配。

• 真实错误现象：OutOfMemoryError: Requested array size exceeds VM limit（JVM 拒绝分配超 2GB 的数组）
• 别信“能存 21 亿个 bit”——那是理论上限，实际受限于堆大小和连续内存可用性
• 若原始数据含负数（如 long 类型用户 ID），直接传入 set() 会转成极大正数（比如 -1L → 18446744073709551615），瞬间触发 OOM

cardinality() 和手动计数，哪个更适合清洗流程

cardinality() 是全量扫描内部 long[] 统计 1 的个数，时间复杂度 O(n)，且每次调用都重新算；而清洗任务通常边读边判重边计数，高频更新下自己维护 uniqueCount 更快也更准。

• 正确模式：

  if (!bitSet.get(id)) { bitSet.set(id); uniqueCount++; }

• 错误模式：bitSet.set(id); uniqueCount++ —— 重复 ID 也会累加
• 注意：bitSet.get(i) 对越界索引（i >= bitSet.length()）返回 false，不抛异常，容易掩盖映射错误（比如哈希后值溢出）
• 最终校验阶段可用 cardinality() 复核，避免并发或逻辑漏更新导致偏差

多线程清洗时直接共享 BitSet 会丢数据

BitSet 所有方法（set、get、and 等）均无同步机制，不是线程安全的。两个线程同时对同一 bit 执行 set()，可能只有一个生效；cardinality() 结果也可能比实际少。

• 典型现象：输入 100 万唯一 ID，输出 cardinality() = 999872，且波动
• 别用 synchronized(bitSet)——锁住整个实例，吞吐归零
• 轻量解法：按 ID 取模分片，例如 bitSets[id % 64].set(id)，每片配独立 BitSet + ReentrantLock
• 更稳方案：改用 ConcurrentHashMap<integer boolean></integer>（内存略高但语义清晰），或直接上 RoaringBitmap（支持并发写）

什么时候该立刻放弃 BitSet，换 RoaringBitmap

只要出现以下任一条件，就该停手，引入 org.roaringbitmap:RoaringBitmap：

• 原始 ID 是 long 类型（如 Snowflake ID），且跨度 > 2³¹（即超 21.47 亿）
• 数据稀疏（比如只设了 10 万个位，但最大 ID 是 10 亿）——BitSet 强制分配 ~125 MB，RoaringBitmap 可能只用几 MB
• 需要交/并/差集运算后持久化或跨进程传输（RoaringBitmap 原生支持序列化、内存映射）
• 清洗链路本身已用 Spark/Flink——RoaringBitmap 有官方集成支持，BitSet 得自己封装

真正的坑不在“怎么用 BitSet”，而在没在读第一行数据前就确认：它的索引能不能覆盖你全部 ID 范围，以及这个覆盖代价你是否真的付得起。