Talk about the copyonwritearraylist of JUC

This blog introduction CopyOnWriteArrayList class , After reading this blog, you will understand ：

• CopyOnWriteArrayList Implementation principle of ( When writing copy );
• CopyOnWriteArrayList Usage scenarios of ;

We know ArrayList It's not thread safe .JDK1.5 Before , To achieve thread safe List, We can

1. Use Vector class
2. Use Collections.synchronizedList Return a synchronization proxy class ;
3. Realize it by yourself ArrayList Subclasses of , And synchronize / Lock .

The first two methods are equivalent to adding one ‘ Global lock ’, The obtained particle is too large , Poor performance . The first 3 Ways of planting , You have to implement it yourself , High complexity .

JDK1.5 when , With J.U.C A new collection tool class is introduced ——CopyOnWriteArrayList：

CopyOnWriteArrayList yes ArrayList Thread safe variant of , All variable operations （ add 、 set etc. ） It's all done by making a new copy of the underlying array . This is a kind of **“ When writing copy ”** Thought . The popular understanding is that when we need to modify （ increase / Delete / Change ） When the element in the list , Don't make changes directly , Instead, list first Copy, Then make changes on the new copy , After the modification is completed , Then point the reference from the original list to the new list .

CopyOnWriteArrayList Implementation principle of

Source code analysis ：

CopyOnWriteArrayList The fields of are simple ：

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    /** *  Exclusive lock ,  Used to synchronize modification operations  */
     final transient ReentrantLock lock = new ReentrantLock();
     /** *  Internal array  */
     private transient volatile Object[] array;

among ,lock Synchronize only when modifying again ,array Is an array that actually stores data inside .

Constructor definition

/**1. Null parameter constructor ： *  Create an empty array  */
public CopyOnWriteArrayList() {
    
    setArray(new Object[0]);
}


/** * 2. Create from an existing set  */
public CopyOnWriteArrayList(Collection<? extends E> c) {
    
   Object[] elements;
   if (c.getClass() == CopyOnWriteArrayList.class)
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
   else {
    
        elements = c.toArray();
   if (c.getClass() != ArrayList.class)
        elements = Arrays.copyOf(elements, elements.length, Object[].class);
   }
   setArray(elements);
}
/** * 3. Create... From an existing array  *Throws: NullPointerException – if the specified array is null */
public CopyOnWriteArrayList(E[] toCopyIn) {
    
     setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

The core approach

Inquire about ——get

private E get(Object[] a, int index) {
    
    return (E) a[index];
}
public E get(int index) {
    
    return get(getArray(), index);
}

You can see ,get Method is not locked , It directly returns the value of the corresponding index position of the internal array ：array[index]

add to ——add

/** * Append the specified element to the end of this list  */

public boolean add(E e) {
    
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
    
        Object[] elements = getArray();     // getArray() Get old array 
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);    //  Copy and create a new array 
        newElements[len] = e;               //  Insert the element at the end of the new array 
        setArray(newElements);              //  Inside array The reference points to the new array 
        return true;
    } finally {
    
        lock.unlock();
    }
}

add Method will lock first , Ensure that only one thread can make changes ; Then a new array will be created （ The size is n+1）, And copy the values of the original array to the new array , The new element is inserted at the end of the new array ; Last , Change the field array Point to the new array .

Above picture ,ThreadB Yes Array Because it is on the new array , So it won't be right ThreadA The read operation of .

Delete ——remove

/** * Remove the element at the specified position in this list . Move any subsequent elements to the left （ Subtract... From their index  1）. Returns the element removed from the list  * Throw out ：IndexOutOfBoundsException */
final ReentrantLock lock = this.lock;
    lock.lock();
    try {
    
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);  //  Get the elements in the old array ,  For return 
        int numMoved = len - index - 1;     //  How many elements need to be moved 
        if (numMoved == 0)                  // index When the position happens to be the last element , Just don't copy it ok 了 .
            setArray(Arrays.copyOf(elements, len - 1));
        else {
    
            Object[] newElements = new Object[len - 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index + 1, newElements, index, numMoved);// two copy When the index Position separation .
            setArray(newElements);
        }
        return oldValue;
    } finally {
    
        lock.unlock();
    }
}

Other statistical methods

public int size() {
    
    return getArray().length;
}

public boolean isEmpty() {
    
    return size() == 0;
}

iteration

CopyOnWriteArrayList When iterating over elements , Just return a snapshot of the current internal array , in other words , If another thread is modifying the element at this time , Not reflected in the iteration , Because the changes are made in the new array .

// 1.  The iterator returned is COWIterator
public Iterator<E> iterator() {
    
    return new COWIterator<E>(getArray(), 0);
}
// 2.  Member properties of iterator 
private final Object[] snapshot;
private int cursor;
// 3.  The construction method of iterator 
private COWIterator(Object[] elements, int initialCursor) {
    
    cursor = initialCursor;
    snapshot = elements;
}
// 4.  The method of iterator ...
public E next() {
    
    if (! hasNext())
        throw new NoSuchElementException();
    return (E) snapshot[cursor++];
}

//....  What we can find is that , All operations of iterators are based on snapshot Array , and snapshot It's passed in array Array 

Come here , We should be able to figure out ！CopyOnWriteArrayList When traversing with iterators , The operation is the original array ！ Other threads will generate a new array after modifying it , So it does not affect the previous array traversal . This is one of his characteristics fail-safe ( Security failure ) Mechanism , That is, the traversal is based on a clone of the container , That is, the modification of the contents of the container does not affect the traversal , That is, it will not throw CurrentModifyException;

3、 ... and 、 summary

CopyOnWriteArrayList On the whole, the idea and implementation of is relatively simple , It is suitable for handling **“ Read more and write less ”** The concurrent scenario of . Through the above pairs CopyOnWriteArrayList Analysis of , Readers should also be able to find some problems in this category ：

1. Memory usage
because CopyOnWriteArrayList Used “ When writing copy ”, So when writing , There will be two in the memory at the same time array Array , If the array memory is too large , Then it may cause frequent GC, therefore CopyOnWriteArrayList It is not suitable for scenarios with a large amount of data .

2. Data consistency
CopyOnWriteArrayList It can only guarantee the final consistency of data , There is no guarantee of real-time consistency of data —— The data read by the read operation is only a snapshot . So if you want to write data that can be read immediately , that CopyOnWriteArrayList Not suitable for .

Other netizens' summary ：

CopyOnWrite Container is the container copied on write . The popular understanding is that when we add elements to a container , Do not add... Directly to the current container , Instead, first, I'll do the current container Copy, Copy out a new container , Then add elements to the new container , After adding elements , Then point the reference of the original container to the new container .

CopyOnWriteArrayList in add/remove Wait for the writing method to be locked , The purpose is to avoid Copy Out N Copy out , Cause concurrent writes .

CopyOnWriteArrayList The method of reading in is unlocked .
The advantage of this is that we can treat CopyOnWrite The container reads concurrently , Of course , The data read here may not be up to date . because The idea of write time replication is to achieve the final consistency of data by delaying the update strategy Of , Not strong consistency .

therefore CopyOnWrite Container is an idea of separation of reading and writing , Read and write in different containers . and Vector Use the same container when reading and writing , Reading and writing are mutually exclusive , Only one thing can be done at the same time .

Reference resources

• https://segmentfault.com/a/1190000016214572
• https://www.cnblogs.com/54chensongxia/p/11728837.html