关于java:CopyOnWriteArrayList源码解析

1. 原理

CopyOnWriteArrayList 有点像线程平安的 ArrayList.

其实它的原理简略概括起来就是读写拆散. 写操作是在一个复制的数组上进行的, 读操作在原始数组中进行, 读写是拆散的. 写操作的时候是加锁了的, 写操作实现了之后将原来的数组指向新的数组.

上面咱们简略看下 add 和 get 办法是如何实现写读操作的.

/**
 * Appends the specified element to the end of this list.
 *
 * @param e element to be appended to this list
 * @return {@code true} (as specified by {@link Collection#add})
 */
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {lock.unlock();
    }
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {return (E) a[index];
}

/**
 * {@inheritDoc}
 *
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {return get(getArray(), index);
}

2. 实用场景

因为每次写数据的时候都会开拓一个新的数组, 这样就会消耗内存, 而且加锁了, 写的性能不是很好. 而读操作是十分迅速的, 并且还反对在写的同时能够读.

所以就非常适合读多写少的场景.

3. 毛病

• 内存耗费大: 每次写操作都须要复制一个新的数组, 所以内存占用是十分大的
• 数据不统一: 读数据的时候可能读取到的不是最新的数据, 因为可能局部写入的数据还未同步到读的数组中.

对内存敏感和实时性要求很高的场景都不适宜.

4. CopyOnWriteArraySet

在翻阅 CopyOnWriteArrayList 源码过程中, 偶然间发现 CopyOnWriteArraySet 的外部竟然就是用一个 CopyOnWriteArrayList 实现的.

public class CopyOnWriteArraySet<E> extends AbstractSet<E>
        implements java.io.Serializable {

    private final CopyOnWriteArrayList<E> al;

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element {@code e} to this set if
     * the set contains no element {@code e2} such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns {@code false}.
     *
     * @param e element to be added to this set
     * @return {@code true} if this set did not already contain the specified
     *         element
     */
    public boolean add(E e) {return al.addIfAbsent(e);
    }

}

而 CopyOnWriteArrayList 的 addIfAbsent 办法其实和 add 办法外部实现是差不多的 (都是新复制数组且上锁), 只不过多了层判断

 /**
 * Appends the element, if not present.
 *
 * @param e element to be added to this list, if absent
 * @return {@code true} if the element was added
 */
public boolean addIfAbsent(E e) {Object[] snapshot = getArray();
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

/**
 * A version of addIfAbsent using the strong hint that given
 * recent snapshot does not contain e.
 */
private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {Object[] current = getArray();
        int len = current.length;
        if (snapshot != current) {
            // Optimize for lost race to another addXXX operation
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        Object[] newElements = Arrays.copyOf(current, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {lock.unlock();
    }
}

5. 扩大 : CopyOnWriteHashMap

Java 没有提供相似 CopyOnWriteHashMap 的类, 可能是曾经有 ConcurrentHashMap 了吧. 明确了 CopyOnWriteArrayList 的思维, 咱们其实还能够模拟着写一个简略的 CopyOnWriteHashMap

import java.util.Collection;
import java.util.Map;
import java.util.Set;
 
public class CopyOnWriteHashMap<K, V> implements Map<K, V>, Cloneable {
    private volatile Map<K, V> internalMap;
 
    public CopyOnWriteHashMap() {internalMap = new HashMap<K, V>();
    }
 
    public V put(K key, V value) {synchronized (this) {Map<K, V> newMap = new HashMap<K, V>(internalMap);
            V val = newMap.put(key, value);
            internalMap = newMap;
            return val;
        }
    }
 
    public V get(Object key) {return internalMap.get(key);
    }
}

6. CopyOnWriteArrayList 为啥比 Vector 性能好?

在 Vector 外部, 增删改查都进行了 synchronized 润饰, 每个办法都要去锁, 性能会大大降低. 而 CopyOnWriteArrayList 只是把增删改加锁了, 所以 CopyOnWriteArrayList 在读方面显著好于 Vector. 所以 CopyOnWriteArrayList 最好是在读多写少的场景下应用.