并发下高效使用BitSet去重排序技巧

本文揭秘了在高并发场景下如何安全高效地使用 BitSet 实现去重与排序：由于原生 BitSet 非线程安全，直接加锁或套用同步集合会严重损害性能，正确解法是采用分段 BitSet（每段 65536 位）配合 LongAdder 或 AtomicLongArray 实现无锁写入——通过 value >>> 16 快速定位段、低位掩码操作精准置位，既规避竞态问题，又保留位图的内存与速度优势；更妙的是，输出时按段调用 nextSetBit(0) 即可天然获得升序结果，彻底省去额外排序开销，堪称固定范围整数去重排序的终极轻量方案。

BitSet 在并发场景下不能直接用

Java 的 BitSet 本身不是线程安全的。多线程同时调用 set()、get() 或 cardinality() 会触发数据错乱，比如位被漏设、计数不准，甚至抛出 ArrayIndexOutOfBoundsException（内部数组扩容时竞态导致引用未及时更新）。

常见错误现象：BitSet 显示已设置某位，但另一线程读不到；或 stream().mapToObj() 遍历时跳过某些值；高并发下 size() 返回负数（内部 wordsInUse 字段撕裂）。

• 别给 BitSet 加 synchronized 块封装——锁粒度太粗，吞吐暴跌，且无法解决迭代与修改的复合操作问题
• 别用 Collections.synchronizedSet(new HashSet()) 模拟位图——内存和时间开销完全失去 BitSet 的优势
• 如果只是去重+排序，且数据范围固定（如 0–1000000），优先考虑无锁替代方案

用 LongAdder + 分段 BitSet 实现无锁去重

核心思路是把大范围拆成多个小 BitSet（例如每段 65536 位），每个段配一个 LongAdder 记录该段已置位数量。线程根据数值哈希到对应段，只对该段加锁（或用 CAS 更新其 words 数组）。

实操建议：

• 分段大小选 2^16（65536）较均衡：太小则锁竞争多，太大则单段内 CAS 失败率高
• 用 AtomicReferenceArray 存储各段，避免初始化竞争；首次访问某段时用 compareAndSet(null, new BitSet())
• 写入时先算段索引：int segment = (int) (value >>> 16)，再对 segments[segment] 调用 set(value & 0xFFFF)
• 排序输出时按段遍历，每段内用 nextSetBit(0) 迭代，拼接结果——天然有序，无需额外排序

ConcurrentHashMap 不如 AtomicLongArray

有人想用 ConcurrentHashMap 存 key 做去重，但这是典型误用：key 是整数且范围可控时，ConcurrentHashMap 的哈希、节点创建、链表转红黑树等开销远超位操作；更关键的是它不提供顺序遍历能力，后续还得收集 key 再排序。

对比方案：

• AtomicLongArray（每个 long 当 64 位）更适合：支持 CAS 更新单个 long，配合位运算（getAndBitwiseOr(idx, 1L ）实现无锁 set；但需自己处理跨 long 的边界和统计
• java.util.concurrent.atomic.Striped（来自 Guava）可简化分段逻辑，但注意其默认条带数是 4，小数据量下反而增加哈希开销
• 若 JDK ≥ 21，可试 VirtualThread + 单个 BitSet 加 synchronized——仅当 QPS

去重后排序的本质是遍历顺序，不是算法

BitSet 本身不“排序”，它的 nextSetBit(start) 是从左到右扫描，返回最小满足条件的索引。所以只要原始数据映射到 bit 位置的方式是单调的（如 value 直接作 index），遍历结果自然升序。

容易踩的坑：

• 负数不能直接塞进 BitSet——必须偏移：如数据范围 [-1000, 9000]，统一加 1000 变成 [0, 10000]，否则 set(-1) 抛 IndexOutOfBoundsException
• 稀疏数据（如只用了 0–100 和 999999）用 BitSet 浪费内存；此时改用 ConcurrentSkipListSet 更省，且自带排序
• 如果业务允许误差，BloomFilter（如 guava BloomFilter）能以极低内存完成去重判断，但无法枚举全部去重结果

真正麻烦的从来不是“怎么排”，而是“怎么在不锁死的情况下让每位都准确落到该落的位置”。位图的并发本质是空间换原子性，不是加锁就能绕过去的。

本篇关于《并发下高效使用BitSet去重排序技巧》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！