No one reads the series. Source code analysis of copyonwritearraylist

• J3 - The west
• aggregate （ Source code # CopyOnWriteArrayList ）

List An implementation class under the interface , and ArrayList Very similar , But not so similar .

A thread safe collection class is often needed to store data in multithreaded environment , You must be familiar with Vector 、Collections.synchronizedXXX 、ConcurrentHashMap etc. . But what I want to analyze below CopyOnWriteArrayList It is also a collection class that can be used in a thread safe environment , It is also useful in practical application , Let's take you to analyze it ！

Article all source environment ：JDK11

1、 brief introduction

ArrayList A thread safe variant of , All of these variable operations ( add to 、 Settings, etc ) It is realized by a new copy of the basic array .

Copying means that the cost of space will be high , Especially when there are many elements in the set, the variable operation is carried out , In high concurrency and very large projects, it is often very fatal , Hang up in minutes .

In the read-write environment, the logic of its implementation is the separation of read and write , The read operation is the original array itself , The write operation will copy a copy from the original array , All modification operations only work on this copy , It has no effect on the original array , Finally, after modifying the data, the modified copy will replace the original array , Complete a data modification operation . The problem here is that the data can not be modified and read in real time , namely There is no guarantee of real-time consistency of data , It can only guarantee the final consistency of data .

Separated by reading and writing , Then the modified data will not appear when iterating over the loop ConcurrentModificationException abnormal .

2、 Attribute analysis

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    
    private static final long serialVersionUID = 8673264195747942595L;
    //  When modifying data , Dependent lock object 
    final transient Object lock = new Object();
    //  Array of storage elements 
    private transient volatile Object[] array;
}

CopyOnWriteArrayList Object has very few properties , Just two ：

1. lock： The lock object to be obtained when modifying data , By transient Keyword decoration indicates that it has its own set of serialization logic . stay JDK8 The lock object is not lock It is ReentrantLock lock , The reason is not the focus of this time , No analysis .
2. array： By volatile Decorated array type attribute , Ensure one modification in a multithreaded environment , Other threads are immediately visible .

3、 Constructors

public CopyOnWriteArrayList() {
    
    //  Parameterless constructors , Directly set a length of  0  The array of is given to  array
    setArray(new Object[0]);
}

//  Directly construct a specified set of data  CopyOnWriteArrayList  object 
public CopyOnWriteArrayList(Collection<? extends E> c) {
    
    Object[] es;
    if (c.getClass() == CopyOnWriteArrayList.class)
        es = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
    
        es = c.toArray();
        if (c.getClass() != java.util.ArrayList.class)
            es = Arrays.copyOf(es, es.length, Object[].class);
    }
    setArray(es);
}

//  Directly construct a specified array  CopyOnWriteArrayList  object 
public CopyOnWriteArrayList(E[] toCopyIn) {
    
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}

These constructors eventually call setArray Method , The code is as follows ：

final void setArray(Object[] a) {
    
    //  Assign value to array , Replace  array  Reference to 
    array = a;
}

as for Arrays.copyOf The analysis of methods is described in detail in this article ：《 Non professional interpretation of ArrayList Source depth analysis 》

4、set Method

public E set(int index, E element) {
    
    //  lock 
    synchronized (lock) {
    
        //  Get array 
        Object[] es = getArray();
        //  Find the data elements according to the following table 
        E oldValue = elementAt(es, index);
        //  Judge whether the element at the subscript is equal to the element to be set 
        if (oldValue != element) {
    
            //  It's not equal , Copy an array 
            es = es.clone();
            //  Mark the setting element under the corresponding 
            es[index] = element;
        }
        // Ensure volatile write semantics even when oldvalue == element
        //  Set the manipulated array copy back 
        setArray(es);
        //  return  index  My old finger 
        return oldValue;
        //  Unlock exit 
    }
}

Methods by synchronized Keyword to lock and unlock , stay JDK1.8 I didn't use this when I was , It is ReentrantLock Reentrant lock , As for the reason, I think it should be JDK11 Of synchronized Better performance than the ReentrantLock .

set The method implementation logic is very simple , First find the element at the corresponding subscript , Judge whether the setting element is equal to the old element , If it is not equal, copy the array , Operate the copy and assign the completed copy to array Array ; Otherwise, the setting operation will not be carried out , Go straight back to index Place element , The ending method .

One thing worth noting is the replication method , This is a waste of memory and time , If there are many collection elements and they are carried out frequently set Method , ... is highly discouraged CopyOnWriteArrayList.

5、add Method

public boolean add(E e) {
    
    //  Lock 
    synchronized (lock) {
    
        //  Get array object 
        Object[] es = getArray();
        //  Get array length 
        int len = es.length;
        //  Copy the array , The length of the new array is  len + 1
        es = Arrays.copyOf(es, len + 1);
        //  Add an element at the end of the array 
        es[len] = e;
        //  Set the array after the operation  
        setArray(es);
        //  Return to success 
        return true;
    }
}

adopt synchronized Keyword lock , When adding data, you copy a copy longer than the original number 1 The new array comes out , Finally, add data and complete the operation of adding elements .

6、add(int, E) Method

public void add(int index, E element) {
    
    //  Lock 
    synchronized (lock) {
    
        //  Get array 
        Object[] es = getArray();
        //  Get array length 
        int len = es.length;
        //  Determine whether the subscript is illegal 
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException(outOfBounds(index, len));
        //  New array 
        Object[] newElements;
        //  Number of elements to move 
        int numMoved = len - index;
        //  If you insert exactly the end of the array , Direct sum  add  The method is the same 
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len + 1);
        else {
    
            //  Insert the element in the middle 
            //  Create a new array that is only larger than the original array 1
            newElements = new Object[len + 1];
            //  Remove the elements from the old array  0 - index  Start copying to the new array 
            System.arraycopy(es, 0, newElements, 0, index);
            //  Remove the elements from the old array  index - length  Start copying to the new array 
            System.arraycopy(es, index, newElements, index + 1,
                             numMoved);
        }
        //  Put the new element in  index  The subscript place 
        newElements[index] = element;
        //  Set array 
        setArray(newElements);
        //  Unlock , Complete element addition 
    }
}

Add an element at the specified subscript , It is inevitable to check whether the subscript is illegal .

Another point is , Element copies that piece of code , It can be said that it is a little novel （ I think ）. Although it is still copied , However, the number of copying and moving is reduced as much as possible, and an element is inserted and written back to array Attribute , The specific operation diagram is as follows .

7、remove Remove elements

public E remove(int index) {
    
    //  Lock 
    synchronized (lock) {
    
        //  Get array 
        Object[] es = getArray();
        //  Get array length 
        int len = es.length;
        //  There is no judgment  index  Get elements directly from the array , Aren't you afraid of subscript out of bounds errors ？？？？？
        E oldValue = elementAt(es, index);
        //  Calculate the number of elements that need to be moved 
        int numMoved = len - index - 1;
        //  Define a new array 
        Object[] newElements;
        if (numMoved == 0)
            //  In this case, the last element is removed 
            newElements = Arrays.copyOf(es, len - 1);
        else {
    
            //  Create a length of  len -1  Array of 
            newElements = new Object[len - 1];
            //  and  add  Copy in the same way 
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index,
                             numMoved);
        }
        //  Set array 
        setArray(newElements);
        //  Returns the removed value 
        return oldValue;
        //  Unlock 
    }
}

Press the subscript to remove the element , According to the source code, it is not complicated , Find the element according to the subscript , Then copy the elements to be removed to the new array, that is, complete the element removal .

But it's a little strange , There is no subscript check , Instead, we get the elements directly from the array according to the incoming subscript , this …？ A proper report will be made ArrayIndexOutOfBoundsException wrong .

Let's analyze a method of removing elements ：

public boolean remove(Object o) {
    
    //  Get array 
    Object[] snapshot = getArray();
    //  Loop through groups , find  o  The corresponding subscript , If not found, return  -1
    int index = indexOfRange(o, snapshot, 0, snapshot.length);
    //  Judging subscripts , Start removing elements 
    return index >= 0 && remove(o, snapshot, index);
}

private boolean remove(Object o, Object[] snapshot, int index) {
    
    //  Lock 
    synchronized (lock) {
    
        //  Get array 
        Object[] current = getArray();
        //  Get array length 
        int len = current.length;
        //  Whether the array has been changed （ Whether it has been replaced by other threads  array）
        if (snapshot != current) findIndex: {
    
            //  Changed , Take this logic 
            //  Find the minimum array length 
            int prefix = Math.min(index, len);
            //  To traverse the 
            for (int i = 0; i < prefix; i++) {
    
                // i  The address of the subscript element is  current  and  snapshot  The addresses in the array are different , But the values are the same , Then the condition holds 
                if (current[i] != snapshot[i]
                    && Objects.equals(o, current[i])) {
    
                    //  Indicates that the removed element is still in the subscript  i  It's about , Assign to  index 
                    index = i;
                    //  Jump out of  if  sentence 
                    break findIndex;
                }
            }
            //  If  index  Greater than  len  There is no need to remove , Remove failed 
            if (index >= len)
                return false;
            // current  Array  index  The element at the subscript is equal to  o  Then jump out  if  Branch , Proceed to remove 
            if (current[index] == o)
                break findIndex;
            // index  Still satisfied with  current  Array subscript range , Then start again from  current  Find... In the array  o  Element subscript 
            index = indexOfRange(o, current, index, len);
            //  Judgment in  current  Whether the index is found in the array 
            if (index < 0)
                return false;
        }
        //  Not changed , Take the following logic 
        //  Create a new array 
        Object[] newElements = new Object[len - 1];
        //  and  add  The same replication logic 
        System.arraycopy(current, 0, newElements, 0, index);
        System.arraycopy(current, index + 1,
                         newElements, index,
                         len - index - 1);
        //  Set array 
        setArray(newElements);
        //  Removed successfully 
        return true;
        //  Unlock 
    }
}

This method is more complicated , The reason is to prevent concurrency problems .

Tell me the general idea ：

1. Get the array object for the first time , And the subscript of the element to be removed .
2. Lock , Get the array object again
3. Judge whether the array object obtained twice is the same
4. Situation 1 ： Dissimilarity , Replaced by another thread , Compare the element subscript obtained for the first time with the array length obtained for the second time, and take the smaller value prefix . Then from 0 Start cycle to prefix, Compare whether the array object obtained twice has elements to be removed , If there is, record its subscript , Jump out step 4 Execution steps 5; Otherwise, judge whether the subscript conforms to the length of the second array object , Noncompliance removal failed , On the contrary, record the subscript , Execution steps 5.
5. Situation two ： equally , Description the array is not replaced , Then follow the normal removal process , Create a new array with length minus one , and add Method to copy the elements to the new array and set the final new array to array Then complete the element removal .

Focus on the fourth step , Combined with my code comments and ideas summary , It's not a problem to fully understand .

about CopyOnWriteArrayList I'm not going to analyze , Because the principle is very simple , I don't know how to get elements without looking at the source code .

8、 Source analysis summary

This article is not right CopyOnWriteArrayList How thorough the introduction is , But it can be said that the key source code is definitely analyzed , The idea of its implementation is also introduced in detail , Then, according to the analysis of this article, I will make a comment on CopyOnWriteArrayList Make a summary of the source code ：

1. CopyOnWriteArrayList stay JDK11 Use synchronized Keyword lock , Ensure thread safety .
2. CopyOnWriteArrayList All write operations must first copy a new array , Make changes in the new array , After modification, replace the old array with the new one , So the spatial complexity is O(n) , Relatively low performance .
3. CopyOnWriteArrayList Read operation supports random access , Time complexity O(1).
4. CopyOnWriteArrayList Using the idea of separation of reading and writing , Read operations are not locked , Write and lock , And write operation takes up more memory space , So it's suitable for reading more and writing less .
5. CopyOnWriteArrayList Only final consistency can be guaranteed , There is no guarantee of real-time consistency .

Okay , Today's content is over here , Pay attention to me , See you next time .

Contact information ：

QQ：1491989462

WeChat ：13207920596

Be a good friend , Have a nice turn .

---

• Due to the blogger's lack of talent and learning , It's hard to avoid mistakes , If you find something wrong or biased , I'd like to leave a message and point it out to me , I'll fix it .

• If you think the article is good , Your forwarding 、 Share 、 give the thumbs-up 、 The message is the biggest encouragement to me .

• Thank you for reading , Thank you for your attention .

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Personal site ：J3

CSDN：J3

Nuggets ：J3

You know ：J3

This is a general technology , Be keen on sharing ; Little experience , But thick skinned enough ; Obviously young and beautiful , But programmers who have to rely on talent .

^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^