java - 自定义类队列数据结构的并发帮助

Question

我正在尝试实现一个以插入性能为中心的类队列数据结构，它必须满足以下要求:

1. 必须是线程安全的
2. 必须能够在不同步的情况下添加到队列
3. 必须能够获得队列的“快照” View

我的问题是以不需要同步插入的方式获取“快照” View 。由于我可以阻止删除并且元素只能添加到最后，所以获取元素应该不是问题。我一直遇到的问题是 LinkedList 的迭代器有一个不可抑制的并发修改快速失败烘焙，并且“LinkedList.get(int)”是 O(n)。

下面是一个精简的示例，说明了我应该如何完成一项相当简单的任务。

public class SnapshotableQueue<T> {
    private final LinkedList<T> queue = new LinkedList<>();
    private final Object removeLock = new Object();

    public void add(T element) {
        queue.add(element);
    }

    public T remove() {
        synchronized(removeLock) {
            return queue.remove();
        }
    }

    public List<T> getSnapshot() {
        synchronized(removeLock) {
            int length = queue.size();
            List<T> snapshot = new ArrayList<>(length);

            ???

            return snapshot;
        }
    }
}

Not Acceptable 解决方案 #1

for(int i = 0; i < length; i++)
    snapshot.add(snapshot.get(i));

'LinkedList.get(int)' 是 O(n)

Not Acceptable 解决方案 #2

Iterator<T> iterator = queue.iterator();
for(int i = 0; i < length; i++)
    snapshot.add(iterator.next());

不是线程安全的(抛出 ConcurrentModificationException)

Not Acceptable 解决方案 #3

Change queue to ArrayList

'ArrayList.remove(0)' 是 O(n)

Answer 1

不要重新发明轮子，使用 ConcurrentLinkedQueue 而不是 LinkedList 然后使用 iterator() 构建你的快照，它是原生线程安全。

您的方法 getSnapshot 将很简单

public List<T> getSnapshot() {
    return new ArrayList<>(queue);
}