The article directories

        • 1. The introduction of
        • 2. Source code analysis
        • 3. Summary

1. The introduction of

We all know that ArrayList under the java.util package is not thread-safe. If you want to use ArrayList in multi-threaded and competitive scenarios, you need some logic to make it thread-safe. Common solutions to ArrayList thread safety issues include:

  • Vector: Similar to the relationship between HashMap and Hashtable, guaranteed by using the synchronized keyword directly in ways that might cause thread-safety problems

    public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

 public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
Copy the code

    However, the granularity of locks is too large, resulting in low concurrency efficiency. Therefore, locking is not recommended

  • SynchronizedList: Similar to synchronizedMap, methods compete for mutex with synchronized prior to execution, and the lock granularity is also larger

    public E get(int index) {
   synchronized (mutex) {return list.get(index);}
}

public E set(int index, E element) {
   synchronized (mutex) {return list.set(index, element);}
}

public void add(int index, E element) {
   synchronized (mutex) {list.add(index, element);}
}

public E remove(int index) {
   synchronized (mutex) {return list.remove(index);}
}
Copy the code

A better option is to use CopyOnWriteArrayList under JUC, which stands for ArrayList for copying writes. Blind guessing ensures thread safety through an idea similar to COW mechanism, namely:

  • There is no thread safety problem when multithreading read, do not need to lock, can read concurrently
  • In multithreaded writes, you’re actually operating on a copy of the ArrayList, so the write request doesn’t block the read request

Is that true or not?

2. Source code analysis

For CopyOnWriteArrayList, write operations need to be locked, and concurrent writing of methods results in data loss. Instead of operating directly on the original array, it copies an array and assigns the copied array to the original array after the write operation. CopyOnWriteArrayList allows both write operations and read operations, greatly improving read operation performance.

Let’s take a look at the source implementation of the common collection method to see how it can be thread-safe. It first defines the ReentrantLock lock object and the array of objects that are volatile in the property field:

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess.Cloneable.java.io.Serializable {
    private static final long serialVersionUID = 8673264195747942595L;

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;
Copy the code

For get(), since there is no thread-safety issue, we can return the element corresponding to the index directly:

 private E get(Object[] a, int index) {
	return (E) a[index];
}
Copy the code

Get () is implemented as follows:

public boolean add(E e) {
    final ReentrantLock lock = this.lock;  / / acquiring a lock
    lock.lock();   / / lock
    try {
        Object[] elements = getArray();  // Get the array defined by the property field
        int len = elements.length;  // Get the array length
        Object[] newElements = Arrays.copyOf(elements, len + 1);   // Get a copy of the array
        newElements[len] = e;   // Perform the add operation on the replica
        setArray(newElements);    // Copy the copy to the original array
        return true;
    } finally {
        lock.unlock();    / / releases the lock}}Copy the code

The getArray() and setArray() methods are implemented as follows:

final Object[] getArray() {
    return array;
}

/** * Sets the array. */
final void setArray(Object[] a) {
    array = a;
}
Copy the code

The logic of add() is as follows:

  • Obtain the ReentrantLock object and lock it to ensure thread safety
  • Gets a copy of the array and adds the new element to the end of the array
  • Copies the copy to the original array
  • Release the lock

The logic of the add() method that adds a new element to the specified index is similar, and the source code implementation is as follows:

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        if (index > len || index < 0)   // Invalid index throw exception
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)  // If the index position is the end of the array, get the copy directly
            newElements = Arrays.copyOf(elements, len + 1);
        else {   // Otherwise the array elements need to be moved
            newElements = new Object[len + 1];
            System.arraycopy(elements, 0, newElements, 0, index);
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        newElements[index] = element;  // Insert a new element
        setArray(newElements);
    } finally{ lock.unlock(); }}Copy the code

Other approaches to thread-safety issues require the use of ReentrantLock and array replication to ensure thread-safety, detailed implementation of visible source code.

3. Summary

In general, CopyOnWriteArrayList requires the use of ReentrantLock to lock and release locks to keep threads safe. Therefore, it is suitable for the application scenarios with more read and less write, but not for the memory-sensitive scenarios with high requirements on real-time data. The disadvantages are:

  • Memory footprint: The new array to be copied takes up memory space
  • Data inconsistency: The read operation cannot read real-time data, that is, the read operation cannot read the data that the write operation has not synchronized to the source array