Java中的ConcurrentBitSet使用小结

好的，我们来对 Java 中的 ConcurrentBitSet 进行一次全面的使用小结。

首先需要明确一个关键点：​Java 标准库中并没有直接提供一个名为 ConcurrentBitSet 的类。​​

我们通常所说的“并发 BitSet”，是指如何在多线程环境下安全、高效地使用 JDK 提供的 java.util.BitSet。由于 BitSet 本身不是线程安全的，直接使用会导致数据竞争和状态不一致。因此，我们需要通过一些技术手段来为它提供并发控制。

下面，我将围绕这个核心思想，从“为什么不安全”到“如何实现安全”进行详细解读。

---

1. 为什么 java.util.BitSet 不是线程安全的？

BitSet 的内部结构是一个 long[] words，所有对位（bit）的操作，如 set(int index), clear(int index), get(int index)，最终都会转化为对这个数组元素的读、改、写操作。

考虑一个简单的 set 操作：

1. 读取目标 word。
2. 对该 word 进行位运算（例如 word |= (1L << bitIndex)）。
3. 将新值写回 words 数组。

在多线程环境下，如果两个线程同时执行 set 操作，可能会发生：

• ​丢失更新​：两个线程同时读取到同一个旧的 word 值，然后各自修改后写回，导致其中一个线程的修改被覆盖。
• ​读到中间状态​：一个线程正在修改 word，另一个线程此时读取，可能会得到一个不完整的中间值。

因此，​任何试图在多个线程中不加同步地共享和修改同一个 BitSet 实例的行为都是错误的。

---

2. 实现线程安全 BitSet 的方案

我们有几种主流的方案来实现一个线程安全的 ConcurrentBitSet。

方案一：使用 synchronized 关键字（内置锁）

这是最直接、最简单的方案。我们通过同步代码块来保护对 BitSet 的所有访问。

public class SynchronizedBitSet {
    private final BitSet bitSet = new BitSet();
    
    // 对整个方法加锁
    public synchronized void set(int bitIndex) {
        bitSet.set(bitIndex);
    }
    
    // 或者对代码块加锁
    public void clear(int bitIndex) {
        synchronized(this) {
            bitSet.clear(bitIndex);
        }
    }
    
    public synchronized boolean get(int bitIndex) {
        return bitSet.get(bitIndex);
    }
    
    // 对于复合操作，比如“检查再设置”，synchronized 是必须的
    public synchronized boolean compareAndSet(int bitIndex, boolean expect, boolean update) {
        boolean current = bitSet.get(bitIndex);
        if (current == expect) {
            if (update) {
                bitSet.set(bitIndex);
            } else {
                bitSet.clear(bitIndex);
            }
            return true;
        }
        return false;
    }
}

​小结：​​

• ​优点​：实现简单，绝对安全，能保证原子性和可见性。
• ​缺点​：性能瓶颈明显。所有线程必须串行访问 BitSet，高并发场景下吞吐量很低。

方案二：使用 ReentrantReadWriteLock（读写锁）

BitSet 的典型使用场景中，​读操作远多于写操作。读写锁可以很好地利用这一点，允许多个读线程并发执行，只有在写操作时才互斥。

public class ReadWriteLockBitSet {
    private final BitSet bitSet = new BitSet();
    private final ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
    private final Lock readLock = lock.readLock();
    private final Lock writeLock = lock.writeLock();
    
    public void set(int bitIndex) {
        writeLock.lock();
        try {
            bitSet.set(bitIndex);
        } finally {
            writeLock.unlock(); // 必须在finally中释放锁
        }
    }
    
    public boolean get(int bitIndex) {
        readLock.lock();
        try {
            return bitSet.get(bitIndex);
        } finally {
            readLock.unlock();
        }
    }
    
    // 可以同时执行多个读操作
    public int cardinality() { // 返回被设置为true的位数
        readLock.lock();
        try {
            return bitSet.cardinality();
        } finally {
            readLock.unlock();
        }
    }
}

​小结：​​

• ​优点​：在读多写少的场景下，性能远优于 synchronized，大大提高了并发性。
• ​缺点​：实现稍复杂，需要小心处理锁的获取和释放（必须在 finally 块中）。写操作仍然是互斥的。

方案三：使用 AtomicIntegerArray 或 LongAdder 思想（分段锁/CAS）

这是最高级的方案，旨在实现无锁（Lock-Free）或细粒度锁，以获得极致性能。其核心思想是将大的 BitSet 分割成多个小的段（Segment），每个段用一个原子变量（如 AtomicLong）来管理。这样，不同线程操作不同段时，可以完全并行，互不干扰。

JDK 的 java.util.concurrent 包中的 ConcurrentHashMap 就使用了类似的“分段锁”思想。我们可以借鉴此思路手动实现一个简单的版本。

​示例：基于 AtomicLongArray 的简单实现​

假设我们的位集大小固定且不大。

public class ConcurrentBitSet {
    private final AtomicLongArray bits; // 使用原子数组，每个元素是AtomicLong
    private final int numBits;
    private final int numWords; // long的个数

    public ConcurrentBitSet(int nbits) {
        if (nbits <= 0) throw new IllegalArgumentException("nbits must be positive");
        this.numBits = nbits;
        // 计算需要多少个long来存储这些位
        this.numWords = (nbits - 1) / Long.SIZE + 1;
        this.bits = new AtomicLongArray(numWords);
    }

    public void set(int bitIndex) {
        validateIndex(bitIndex);
        int wordIndex = bitIndex / Long.SIZE;
        int bitInWord = bitIndex % Long.SIZE;
        long mask = 1L << bitInWord;
        
        // CAS 循环，直到成功为止
        while (true) {
            long oldWord = bits.get(wordIndex);
            long newWord = oldWord | mask;
            if (bits.compareAndSet(wordIndex, oldWord, newWord)) {
                return; // 设置成功
            }
            // 如果CAS失败，说明有其他线程修改了该word，重试
        }
    }
    
    public boolean get(int bitIndex) {
        validateIndex(bitIndex);
        int wordIndex = bitIndex / Long.SIZE;
        int bitInWord = bitIndex % Long.SIZE;
        long mask = 1L << bitInWord;
        long word = bits.get(wordIndex);
        return (word & mask) != 0;
    }
    
    public void clear(int bitIndex) {
        validateIndex(bitIndex);
        int wordIndex = bitIndex / Long.SIZE;
        int bitInWord = bitIndex % Long.SIZE;
        long mask = ~(1L << bitInWord); // 注意这里是取反
        
        while (true) {
            long oldWord = bits.get(wordIndex);
            long newWord = oldWord & mask;
            if (bits.compareAndSet(wordIndex, oldWord, newWord)) {
                return;
            }
        }
    }
    
    private void validateIndex(int bitIndex) {
        if (bitIndex < 0 || bitIndex >= numBits)
            throw new IndexOutOfBoundsException("bitIndex: " + bitIndex);
    }
}

​小结：​​

• ​优点​：性能最高。实现了真正的细粒度并发控制，不同段的位操作可以完全并行，是无锁编程思想的体现。
• ​缺点​：实现非常复杂，需要处理边界条件、CAS 失败重试等。并且对于 cardinality(), intersects() 等复合操作，保证其原子性和正确性难度极大，通常需要对整个对象加锁或使用更复杂的算法。

---

3. 第三方库的选择

如果不想自己造轮子，可以考虑成熟的第三方库：

1. ​Eclipse Collections​：
   • 提供了 ConcurrentBitMap，是一个功能强大且线程安全的位图实现。
   • 设计精良，性能优异，是生产环境的优秀选择。
2. ​Google Guava​：
   • Guava 的 com.google.common.util.concurrent.Striped 可以与其他集合结合使用，但它不直接提供一个 ConcurrentBitSet。不过，你可以用 Striped<Lock> 来实现分段锁，这是一种比 ReadWriteLock 更灵活的分段锁方案。

---

4. 使用小结与最佳实践

方案	适用场景	优点	缺点
​**synchronized**​	并发量极低，或对性能不敏感的场景。快速原型开发。	实现简单，绝对安全。	性能差，扩展性不佳。
​**ReadWriteLock**​	​通用场景，特别是读多写少。是平衡安全性和性能的首选推荐方案。	读并发性好，实现相对简单。	写操作仍互斥，高竞争下性能下降。
​CAS/分段锁​	超高并发场景，对性能有极致要求，且能接受实现的复杂性。	性能最佳，无锁化。	实现复杂，难以保证所有操作的原子性。
​第三方库​	生产环境，需要稳定、高效、功能丰富的位图操作。	功能全面，久经考验，省心省力。	引入外部依赖。

​最佳实践建议：​​

1. ​**默认选择 ReadWriteLock**​：在大多数应用中，ReadWriteLock 方案提供了最佳的性价比。它在保证线程安全的同时，极大地提升了读操作的并发能力。
2. ​优先使用不可变操作​：如果只是读取，确保使用读锁或无锁的 get 方法。
3. ​警惕复合操作​：像“如果A位为0，则设置B位”这样的逻辑，必须在同一把锁的保护下完成，否则会产生竞态条件。
4. ​评估第三方库​：如果项目已经使用了 Eclipse Collections 或类似库，优先考虑它们的并发位图实现。
5. ​只在必要时优化​：不要一开始就实现最复杂的 CAS 方案。先用 ReadWriteLock 实现功能，待遇到性能瓶颈时，再通过 profiling 工具定位，并考虑向更细粒度的并发控制迁移。

总而言之，虽然 Java 没有内置的 ConcurrentBitSet，但通过灵活的并发工具，我们可以轻松地为其构建出满足不同场景需求的线程安全包装器。​理解每种方案的权衡（Trade-off）是做出正确选择的关键。