brief introduction

CopyOnWriteArrayList is a thread safe version of ArrayList. It is also implemented internally through arrays. Each time the array is modified, a new array is completely copied to modify it. After modification, the old array is replaced. In this way, only write operations are blocked, read operations are not blocked, and read-write separation is realized.

Inheritance system

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable 
    {...}

• CopyOnWriteArrayList implements List, RandomAccess, Cloneable, Java io. Serializable and other interfaces.
• CopyOnWriteArrayList implements List and provides basic operations such as addition, deletion and traversal.
• CopyOnWriteArrayList implements RandomAccess and provides the ability of random access.
• CopyOnWriteArrayList implements Cloneable and can be cloned.
• CopyOnWriteArrayList implements Serializable and can be serialized.

Source code analysis

attribute

/** Used to lock when modifying */
final transient ReentrantLock lock = new ReentrantLock();

/** The place where elements are actually stored can only be accessed through getArray()/setArray() */
private transient volatile Object[] array;

• Lock: lock when modifying. Use the transient modifier to indicate that it is not automatically serialized.
• array: where elements are stored, the transient modifier is used to indicate that they are not automatically serialized, and the volatile modifier is used to indicate that one thread modifies this field, and another thread is immediately visible.

Construction method

Create an empty array.

public CopyOnWriteArrayList() {
    // All operations on array are performed through setArray() and getArray()
    setArray(new Object[0]);
}

final void setArray(Object[] a) {
    array = a;
}

public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // If c is also CopyOnWriteArrayList type
        // Then take its array directly and use it
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        // Otherwise, call its toArray() method to convert the collection elements into arrays
        elements = c.toArray();
        // Here, the type returned by c.toArray() is not necessarily Object []
        // See the analysis in ArrayList for detailed reasons
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}

• If c is CopyOnWriteArrayList type, directly assign its array to the array of the current list. Note that this is a shallow copy, and the two sets share the same array.
• If c is not of CopyOnWriteArrayList type, copy all the elements of c into the array of the current list.

public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

• Copy the toCopyIn element to the array of the current list.

Add (E) method

Add an element to the end.

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // Lock
    lock.lock();
    try {
        // Get old array
        Object[] elements = getArray();
        int len = elements.length;
        // Copy the old array elements to the new array
        // The new array size is the old array size plus 1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // Put element last
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        // Release lock
        lock.unlock();
    }
}

1. Locking;
2. Get element array;
3. Create a new array whose size is the length of the original array plus 1, and copy the elements of the original array to the new array;
4. Put the newly added element at the end of the new array;
5. Assign the new array to the array attribute of the current object and overwrite the original array;
6. Unlock.

add(int index, E element) method

Adds an element at the specified index.

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // Lock
    lock.lock();
    try {
        // Get old array
        Object[] elements = getArray();
        int len = elements.length;
        // Check whether it is out of bounds, which can be equal to len
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // If the insertion position is the last one
            // Then copy an n+1 array, and its first n elements are consistent with the old array
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // If the insertion position is not the last one
            // Then create a new n+1 array
            newElements = new Object[len + 1];
            // Copy the elements of index before the old array to the new array
            System.arraycopy(elements, 0, newElements, 0, index);
            // Move the index and its subsequent elements back one bit and copy them into the new array
            // This way, the position is empty
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // Place the element at index
        newElements[index] = element;
        setArray(newElements);
    } finally {
        // Release lock
        lock.unlock();
    }
}

1. Locking;
2. Check whether the index is legal. If not, throw an IndexOutOfBoundsException exception. Note that index equals len is also legal here;
3. If the index is equal to the length of the array (that is, the last bit of the array plus 1), copy an array of len+1;
4. If the index is not equal to the array length, create a new len+1 array and divide it into two parts according to the index position. The part before (not included) the index is copied to the part before (not included) the new array index, and the position after (included) the index is copied to the position after (not included) the new array index. The position of the index is left blank;
5. Assign the index position to the element to be added;
6. Assign the new array to the array attribute of the current object and overwrite the original array;
7. Unlock;

Addifabsent (E) method

Add an element if it does not exist in the collection.

public boolean addIfAbsent(E e) {
    // Get the element array, named snapshot
    Object[] snapshot = getArray();
    // Check that if the element does not exist, it returns false directly
    // If so, call the addIfAbsent() method to add the element
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    // Lock
    lock.lock();
    try {
        // Retrieve old array
        Object[] current = getArray();
        int len = current.length;
        // If the snapshot is inconsistent with the array just obtained
        // The description has been modified
        if (snapshot != current) {
            // Recheck whether the element is in the array just obtained
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                // This method indicates that the element is not in the snapshot
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        // Copy an n+1 array
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // Put element last
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        // Release lock
        lock.unlock();
    }
}

1. Check whether this element exists in the array snapshot;
2. If it exists, it directly returns false. If it does not exist, it calls addifabsent (E, object [] snapshot) for processing;
3. Locking;
4. If the current array is not equal to the incoming snapshot, it indicates that it has been modified. Check whether the element to be added exists in the current array. If so, return false directly;
5. Copy a new array whose length is equal to the length of the original array plus 1, and copy the elements of the original array to the new array;
6. Add the new element to the last bit of the array;
7. Assign the new array to the array attribute of the current object and overwrite the original array;
8. Unlock;

get(int index)

Gets the element of the specified index, supports random access, and the time complexity is O(1).

public E get(int index) {
    // Getting elements does not require locking
    // Returns the element of the index position directly
    // There is no cross-border check here, because the array itself will cross-border check
    return get(getArray(), index);
}

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

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

1. Get element array;
2. Returns the element at the specified index position of the array;

remove(int index) method

Deletes the element at the specified index location.

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    // Lock
    lock.lock();
    try {
        // Get old array
        Object[] elements = getArray();
        int len = elements.length;
        E oldValue = get(elements, index);
        int numMoved = len - index - 1;
        if (numMoved == 0)
            // If the last bit is removed
            // Then directly copy a new array of n-1, and the last bit will be deleted automatically
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // If not the last one removed
            // Then create a new n-1 array
            Object[] newElements = new Object[len - 1];
            // Copy the elements of the previous index to the new array
            System.arraycopy(elements, 0, newElements, 0, index);
            // Move the element after index (not included) forward one bit
            // This just overwrites the index position, which is equivalent to deleting it
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // Release lock
        lock.unlock();
    }
}

1. Locking;
2. Gets the old value of the element at the specified index position;
3. If the last element is removed, copy the first len-1 element of the original array to the new array, and assign the new array to the array attribute of the current object;
4. If the removed element is not the last element, create a new len-1 length array, copy all the elements of the original array except the specified index position into the new array, and assign the new array to the array attribute of the current object;
5. Unlock and return the old value;

size() method

Returns the length of the array.

public int size() {
    // No lock is required to obtain the number of elements
    // Returns the length of the array directly
    return getArray().length;
}

put questions to

Why does CopyOnWriteArrayList have no size attribute?

Because each modification is to copy an array that can store the target number of elements, the size attribute is not required. The length of the array is the size of the set, unlike ArrayList, the length of the array is actually greater than the size of the set. For example, in the add (E) operation, first copy an array of n+1 elements, and then put the new element in the last bit of the new array. At this time, the length of the new array is len+1, that is, the size of the set.

summary

1. CopyOnWriteArrayList uses ReentrantLock to lock and ensure thread safety;
2. CopyOnWriteArrayList needs to copy a new array first, modify it in the new array, and then replace the old array with the new array after modification. Therefore, the space complexity is O(n), and the performance is relatively low;
3. The read operation of CopyOnWriteArrayList supports random access, and the time complexity is O(1);
4. CopyOnWriteArrayList adopts the idea of separation of reading and writing. The read operation is not locked, the write operation is locked, and the write operation occupies a large memory space, so it is suitable for occasions with more reading and less writing;
5. CopyOnWriteArrayList only guarantees final consistency, not real-time consistency.