This is the sixth day of my participation in the First Challenge 2022. For details: First Challenge 2022.

Introduction to the

CopyOnWriteArrayList is a thread-safe version of ArrayList, which is also implemented internally by arrays. Each change in the array copies a new array to modify, and then replaces the old array. This ensures that only the write operation is blocked, but not the read operation, and achieves read-write separation.

Inheritance system

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

  • CopyOnWriteArrayList implements List, RandomAccess, Cloneable, Java.io.Serializable and other interfaces.

  • CopyOnWriteArrayList implements List and provides basic add, delete, iterate, and so on.

  • CopyOnWriteArrayList implements RandomAccess and provides RandomAccess.

  • CopyOnWriteArrayList implements Cloneable and can be cloned.

  • CopyOnWriteArrayList implements Serializable and can be serialized.

The source code parsing

attribute

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

/** Where the elements are actually stored can only be accessed through getArray()/setArray()
private transient volatile Object[] array;
Copy the code

  • Lock: Lock when modified, use transient modifier to indicate that automatic serialization is not performed.

  • Array: Places where elements are stored. Use transient to indicate that serialization is not automatic, and volatile to indicate that changes made by one thread to a field are immediately visible to another thread.

A constructor

Create an empty array.

public CopyOnWriteArrayList(a) {
    SetArray () and getArray() are used for all operations on the array
    setArray(new Object[0]);
}

final void setArray(Object[] a) {
    array = a;
}
Copy the code
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // If C is also CopyOnWriteArrayList
        // Just use the arrayelements = ((CopyOnWriteArrayList<? >)c).getArray();else {
        // Otherwise, call its toArray() method to convert the collection elements to arrays
        elements = c.toArray();
        C. toarray () does not necessarily return an Object[]
        // See ArrayList for detailed reasons
        if(elements.getClass() ! = Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); } setArray(elements); }Copy the code

  • If C is CopyOnWriteArrayList, assign its array directly to the array of the current list. Note that this is a shallow copy. Both collections share the same array.

  • If C is not CopyOnWriteArrayList, copy all elements of C into the current list array.

public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Copy the code
  • Copy the toCopyIn element to the current list array.

The add (E, E) method

Add an element to the end.

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

  1. Lock;

  2. Get an array of elements;

  3. Create an array with the size of the original array plus 1, and copy the elements of the original array into the new array.

  4. Place the newly added element at the end of the new array;

  5. Assign the new array to the array property of the current object, overwriting the original array.

  6. Unlocked.

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 the old array
        Object[] elements = getArray();
        int len = elements.length;
        // Check if it is out of bounds, can equal 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 digit
            // Copy an array of n+1 elements that are identical to the old array
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // If the insertion position is not the last digit
            // Create an array of n+1
            newElements = new Object[len + 1];
            // Copy the index element from the old array to the new array
            System.arraycopy(elements, 0, newElements, 0, index);
            // Copy the index and the element after it one bit back into the new array
            // the index position is empty
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // Place the element at index
        newElements[index] = element;
        setArray(newElements);
    } finally {
        / / releases the locklock.unlock(); }}Copy the code

  1. Lock;

  2. Check whether the index is legal, if not legally throwing IndexOutOfBoundsException abnormalities, note here it is lawful to index equal len.

  3. If the index is equal to the length of the array (that is, the last digit of the array plus 1), copy the array with len+1;

  4. If the index is not equal to the length of the array, then create a new array of len + 1, and according to the index position is divided into two parts, the index before (not included) part of the copy to the new array index before (not included), after the index (included) after the location of the copy to the new array index (not included), index location blank;

  5. Assign the index position to the element to be added;

  6. Assign the new array to the array property of the current object, overwriting the original array.

  7. Unlock;

AddIfAbsent (E, E) method

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

public boolean addIfAbsent(E e) {
    // Get an array of elements, named snapshot
    Object[] snapshot = getArray();
    // Check that if the element does not exist, return false
    // If so, call addIfAbsent() 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 the 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 if the element is in the array you just got
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                // 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 array of n+1
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // Place the element last
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        / / releases the locklock.unlock(); }}Copy the code

  1. Check if the element exists in the array snapshot;

  2. AddIfAbsent (E E, Object[] snapshot) if addIfAbsent(E E, Object[] snapshot) does not exist

  3. Lock;

  4. If the current array is not equal to the snapshot passed in, it is modified. Check whether the element to be added exists in the current array. If so, return false.

  5. Copy a new array equal to the length of the original array plus one, and copy the elements of the original array into the new array.

  6. Add the new element to the last bit of the array;

  7. Assign the new array to the array property of the current object, overwriting the original array.

  8. Unlock;

get(int index)

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

public E get(int index) {
    // Get elements without locking
    // Return the element at index directly
    // There is no out of bounds check here, because the array itself does out of bounds checks
    return get(getArray(), index);
}

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

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

  1. Get an array of elements;

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

Remove (int index) method

Deletes the element at the specified index position.

public E remove(int index) {
    final ReentrantLock lock = this.lock;
    / / lock
    lock.lock();
    try {
        // Get the 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 digit is removed
            // Then copy the new array of n-1, the last bit is deleted automatically
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // If the last digit is not removed
            // Create a new array of n-1
            Object[] newElements = new Object[len - 1];
            // Copy the previous index element into the new array
            System.arraycopy(elements, 0, newElements, 0, index);
            // Move the element after index (not included) one bit forward
            // The index position is deleted
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        / / releases the locklock.unlock(); }}Copy the code

  1. Lock;

  2. Gets the old value of the element at the specified index position.

  3. If the last element is removed, the first len-1 element of the original array is copied to the new array and assigned to the array property of the current object.

  4. If not the last element is removed, create a new len-1 array, copy all of the original array except the elements at the specified index position into the new array, and assign the new array to the array properties of the current object.

  5. Unlock and return the old value;

The size () method

Returns the length of the array.

public int size(a) {
    // Get the number of elements without locking
    // Return the length of the array directly
    return getArray().length;
}
Copy the code

Ask questions

Why does CopyOnWriteArrayList have no size property?

Since each change is copying an array that can store exactly the number of elements, the size property is not needed. The length of the array is the size of the collection, unlike an ArrayList whose length is actually greater than the size of the collection. For example, add(E, E) copies an array of n+1 elements and places the new element at the end of the array. The new array is len+1, which is the size of the collection.

conclusion

  1. CopyOnWriteArrayList uses ReentrantLock to lock, ensuring thread safety;

  2. CopyOnWriteArrayList write operations must first copy a new array, make changes in the new array, and then replace the old array with the new array, so the space complexity is O(n), low performance;

  3. The read operation of CopyOnWriteArrayList supports random access and the time complexity is O(1).

  4. CopyOnWriteArrayList uses the idea of read and write separation, read operation without lock, write operation lock, and write operation occupies a large memory space, so it is suitable for read more write less occasions;

  5. CopyOnWriteArrayList only guarantees final consistency, not real-time consistency.