多线程场景下如何无锁实现从集合中获取唯一元素？

我有一个存储不重复字符串的集合，最初尝试用CopyOnWriteArrayList或ConcurrentLinkedQueue实现多线程下获取唯一字符串的逻辑，但运行时多数情况会出现多个线程拿到相同值的问题。目前我用锁实现了可行的版本，代码如下：

public class SomeClass {

  ReentrantLock lock = new ReentrantLock();
  // 该集合保证元素无重复
  private List<String> bookingIds;

  public String read() {
    lock.lock();
    if (Objects.isNull(bookingIds)) {
      bookingIds = bookingInfoUtil.findDistinctId();
    }
    if (! bookingIds.isEmpty()) {
      String bookingId = bookingIds.remove(0);
      lock.unlock();
      return bookingId;
    }
    lock.unlock();
    return null;
  }
}

想请教如何用无锁机制实现该需求，最好基于线程安全集合。

核心思路 #

要解决你的问题，需要同时满足两个线程安全要求：

1. 集合仅初始化一次，避免多线程重复加载数据导致元素重复
2. 从集合中获取并移除元素的操作是原子性的，确保每个元素只被一个线程拿到

推荐实现：ConcurrentLinkedQueue + AtomicReference #

ConcurrentLinkedQueue是基于CAS实现的无锁线程安全队列，其poll()方法天生是原子操作——会从队列头部取出并移除元素，多线程调用时绝不会出现重复获取同一元素的情况。配合AtomicReference可以实现集合的原子性懒加载，避免重复初始化。

代码示例：

import java.util.concurrent.ConcurrentLinkedQueue;
import java.util.concurrent.atomic.AtomicReference;

public class SomeClass {
    // 用AtomicReference保证队列初始化的原子性
    private final AtomicReference<ConcurrentLinkedQueue<String>> bookingIdsRef = new AtomicReference<>();

    public String read() {
        ConcurrentLinkedQueue<String> bookingIds = bookingIdsRef.get();
        // 懒加载初始化，仅第一次调用时执行
        if (bookingIds == null) {
            // 先加载数据
            ConcurrentLinkedQueue<String> newQueue = new ConcurrentLinkedQueue<>(bookingInfoUtil.findDistinctId());
            // CAS操作：只有当引用还为null时，才将新队列赋值进去
            if (bookingIdsRef.compareAndSet(null, newQueue)) {
                bookingIds = newQueue;
            } else {
                // 其他线程已经完成初始化，直接取已存在的队列
                bookingIds = bookingIdsRef.get();
            }
        }
        // poll()原子性获取并移除队首元素，空队列返回null
        return bookingIds.poll();
    }
}

为什么之前的尝试会失败？ #

你之前用CopyOnWriteArrayList或ConcurrentLinkedQueue出问题，大概率是初始化环节没有做原子性控制——多个线程同时进入初始化逻辑，重复调用findDistinctId()生成了多份相同数据的集合，导致不同线程从不同集合（或重复初始化的同一集合）中拿到相同元素。而上面的方案通过AtomicReference的CAS操作，确保了集合只会被初始化一次，从根源上避免了数据重复问题。

其他可选方案 #

如果偏好List结构，可以用CopyOnWriteArrayList配合AtomicInteger实现原子性索引递增：

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.atomic.AtomicInteger;

public class SomeClass {
    private final AtomicInteger index = new AtomicInteger(0);
    private volatile List<String> bookingIds;

    public String read() {
        // 双重检查锁初始化（这里用volatile保证可见性）
        if (bookingIds == null) {
            synchronized (this) {
                if (bookingIds == null) {
                    bookingIds = new CopyOnWriteArrayList<>(bookingInfoUtil.findDistinctId());
                }
            }
        }
        int currentIndex = index.getAndIncrement();
        // 检查索引是否越界
        if (currentIndex < bookingIds.size()) {
            return bookingIds.get(currentIndex);
        }
        return null;
    }
}

不过这个方案本质上是用“取索引”代替“移除元素”，元素不会被真正移除，且如果集合后续有修改会有风险，性能也不如ConcurrentLinkedQueue的无锁poll操作，更推荐第一种方案。

内容的提问来源于stack exchange，提问作者Rahul Raj