java 并发数组列表

Concurrent ArrayList

提问by maaartinus

I need an ArrayList-like structure allowing just the following operations

我需要一个类似 ArrayList 的结构，只允许以下操作

• get(int index)
• add(E element)
• set(int index, E element)
• iterator()

• get(int index)
• add(E element)
• set(int index, E element)
• iterator()

Because of the iterator being used in many places, using Collections#synchronizedListwould be too error-prone. The list can grow to a few thousand elements and gets used a lot, so I'm pretty sure, that CopyOnWriteArrayListwill be too slow. I'll start with it to avoid premature optimizations, but I'd bet it won't work well.

由于迭代器在很多地方使用，使用Collections#synchronizedList会太容易出错。该列表可以增长到几千个元素并被大量使用，所以我很确定，这CopyOnWriteArrayList太慢了。我将从它开始以避免过早的优化，但我敢打赌它不会很好地工作。

Most accesses will be single-threaded reads. So I'm asking what's the proper data structure for this.

大多数访问将是单线程读取。所以我在问什么是合适的数据结构。

---

---

I though that wrapping the synchronizedListin something providing a synchronized iterator would do, but it won't because of the ConcurrentModificationException. Concenrning concurrent behavior, I obviously need that all changes will be visible by subsequent reads and iterators.

我虽然将 包装synchronizedList在提供同步迭代器的东西中会做，但它不会因为ConcurrentModificationException. 关于并发行为，我显然需要所有更改都可以通过后续读取和迭代器看到。

The iterator doesn't have to show a consistent snapshot, it may or may not see the updates via set(int index, E element)as this operation gets used only to replace an item with its updated version (containing some added information, which is irrelevant for the user of the iterator). The items are fully immutable.

迭代器不必显示一致的快照，它可能会也可能不会看到更新，set(int index, E element)因为此操作仅用于将项目替换为其更新版本（包含一些附加信息，这与迭代器的用户无关）。这些项目是完全不可变的。

---

---

I clearly stated why CopyOnWriteArrayListwould not do. ConcurrentLinkedQueueis out of question as it lacks an indexed access. I need just a couple of operations rather than a fully fledged ArrayList. So unless any java concurrent list-relatedquestion is a duplicate of this question, this one is not.

我清楚地说明了为什么CopyOnWriteArrayList不这样做。ConcurrentLinkedQueue毫无疑问，因为它缺乏索引访问。我只需要几个操作，而不是一个完全成熟的ArrayList. 因此，除非任何与 Java 并发列表相关的问题与此问题重复，否则此问题不是。

回答by Chriss

In your case you can use a ReadWriteLockto access a backed List, this allows multiple Threads to read your list. Only if one Thread needs write access all reader-Thread must wait for the operation to complete. The JavaDoc make's it clear:

在您的情况下，您可以使用ReadWriteLock访问支持列表，这允许多个线程读取您的列表。只有当一个 Thread 需要写访问时，所有的 reader-Thread 必须等待操作完成。JavaDoc 清楚地说明了这一点：

A ReadWriteLock maintains a pair of associated locks, one for read-only operations and one for writing. The read lock may be held simultaneously by multiple reader threads, so long as there are no writers. The write lock is exclusive.

ReadWriteLock 维护一对关联的锁，一个用于只读操作，一个用于写入。只要没有写者，读锁就可以被多个读者线程同时持有。写锁是独占的。

Here is a sample:

这是一个示例：

public class ConcurrentArrayList<T> {

    /** use this to lock for write operations like add/remove */
    private final Lock readLock;
    /** use this to lock for read operations like get/iterator/contains.. */
    private final Lock writeLock;
    /** the underlying list*/
    private final List<T> list = new ArrayList();

    {
        ReentrantReadWriteLock rwLock = new ReentrantReadWriteLock();
        readLock = rwLock.readLock();
        writeLock = rwLock.writeLock();
    }

    public void add(T e){
        writeLock.lock();
        try{
            list.add(e);
        }finally{
            writeLock.unlock();
        }
    }

    public void get(int index){
        readLock.lock();
        try{
            list.get(index);
        }finally{
            readLock.unlock();
        }
    }

    public Iterator<T> iterator(){
        readLock.lock();
        try {
            return new ArrayList<T>( list ).iterator();
                   //^ we iterate over an snapshot of our list 
        } finally{
            readLock.unlock();
        }
    }