并发ArrayList

Question

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

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

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

大多数访问将是单线程读取.所以我问这是什么样的数据结构.

---

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

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

---

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

Answer 1

在您的情况下,您可以使用ReadWriteLock访问支持的列表,这允许多个线程读取您的列表.只有当一个线程需要写访问时,所有读者 - 线程必须等待操作完成.JavaDoc让它变得清晰:

ReadWriteLock维护一对关联的锁,一个用于只读操作,另一个用于写入.只要没有写入器,读锁定可以由多个读取器线程同时保持.写锁是独占的.

这是一个示例:

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();
        }
    }