Python wechat ordering applet course video

https://edu.csdn.net/course/detail/36074

Python practical quantitative transaction financial management system

https://edu.csdn.net/course/detail/35475

1, Abstract

Before introducing CopyOnWriteArrayList, let's take a look at the execution results of the following methods. The code content is as follows:

public static void main(String[] args) {
    List list = new ArrayList();
 list.add("1");
 list.add("2");
 list.add("1");
 System.out.println("original list Element:"+ list.toString());
 //Remove an element with content equal to 1 from the object
 for (String item : list) {
 if("1".equals(item)) {
 list.remove(item);
 }
 }
 System.out.println("After object removal list Element:"+ list.toString());
}

The implementation results are as follows:

original list Element:[1, 2, 1]
Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
	at java.util.ArrayList$Itr.next(ArrayList.java:859)
	at com.example.container.a.TestList.main(TestList.java:16)

Unfortunately, the result did not achieve the desired effect. After implementation, an error was reported directly! Throw ConcurrentModificationException!

Why throw this exception?

Let's take a look. foreach is actually written for list Iterator () is a shorthand for iterator, so we can analyze list Iterator () iterator to see why this exception is thrown.

Iterator iterator implementation in ArrayList class, source code content:

Through the code, we find that Itr is a private internal class defined in ArrayList. Every time the next and remove methods are called, the checkForComodification method will be called. The source code is as follows:

/**Modification times check*/
final void checkForComodification() {
	//Check that the number of modifications in the List is equal to the number of modifications in the iterator class
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

The checkForComodification method is actually used to check whether the number of modifications modCount in the List is equal to the number of modifications expectedModCount in the iterator class. If not, a ConcurrentModificationException will be thrown!

The problem is basically clear. The reason why the above run result throws this exception is that the number of modifications in the List is different from the number of modifications in the iterator class, expectedModCount!

Friends who have read the collection source code may think of the Vector class. Isn't it a thread safe version of ArrayList in JDK?

OK, in order to see for real, let's replace ArrayList with Vector to test. The code is as follows:

public static void main(String[] args) {
    Vector list = new Vector();
 //Simulate 10 threads to add content to the list and read the content
 for (int i = 0; i < 5; i++) {
 final int j = i;
 new Thread(new Runnable() {
 @Override
 public void run() {
 //Add content
 list.add(j + "-j");

 //Read content
 for (String str : list) {
 System.out.println("Content:" + str);
 }
 }
 }).start();
 }
}

Execute the program, and the running results are as follows:

The same result is the exception thrown. Although Vector is thread safe, it just adds the synchronized keyword, but the iteration problem is not solved at all!

Continue to return to the CopyOnWriteArrayList class to be introduced in this article. Let's try to replace the above example with the CopyOnWriteArrayList class. The source code is as follows:

public static void main(String[] args) {
    //Replace ArrayList with CopyOnWriteArrayList
    CopyOnWriteArrayList list = new CopyOnWriteArrayList<>();
 list.add("1");
 list.add("2");
 list.add("1");
 System.out.println("original list Element:"+ list.toString());

 //Remove an element equal to 11 from the object
 for (String item : list) {
 if("1".equals(item)) {
 list.remove(item);
 }
 }
 System.out.println("After object removal list Element:"+ list.toString());
}

The results are as follows:

original list Element:[1, 2, 1]
After object removal list Element:[2]

Eh, the execution was successful and no error was reported! Isn't it amazing

Of course, there are many examples like the above. For example, writing 10 threads to add elements to the list and read the contents will also throw the above exception. The operation is as follows:

public static void main(String[] args) {
    final List list = new ArrayList<>();
 //Simulate 10 threads to add content to the list and read the content
 for (int i = 0; i < 10; i++) {
 final int j = i;
 new Thread(new Runnable() {
 @Override
 public void run() {
 //Add content
 list.add(j + "-j");

 //Read content
 for (String str : list) {
 System.out.println("Content:" + str);
 }
 }
 }).start();
 }
}

There are many similar operation examples, so we won't give them one by one here.

CopyOnWriteArrayList is actually a thread safe operation class of ArrayList!

As can be seen from its name, CopyOnWrite does not modify the original content when writing, but copies the original content to a new array, and then moves the memory pointer to point to the latest location after writing data to the new array.

2, Introduction

From jdk1 5 started Java and provided two concurrent containers implemented by CopyOnWrite mechanism in the contract, namely CopyOnWriteArrayList and CopyOnWriteArraySet.

From the name, CopyOnWriteArrayList is mainly for dynamic arrays, a thread safe version of ArrayList!

CopyOnWriteArraySet is mainly used for sets. CopyOnWriteArraySet can be understood as a thread safe operation class of HashSet. We all know that HashSet is implemented based on Hash HashMap, but CopyOnWriteArraySet is not implemented based on hash, but based on CopyOnWriteArrayList dynamic array!

On this point, we can draw a conclusion from its source code. Part of the source code content:

It can be seen from the source code that during the default initialization of CopyOnWriteArraySet, the CopyOnWriteArrayList class is instantiated. Most methods of CopyOnWriteArraySet, such as add and remove, are implemented based on CopyOnWriteArraySet!

The biggest difference between the two is that CopyOnWriteArrayList allows duplicate elements, while CopyOnWriteArraySet does not allow duplicate elements!

OK, continue to BB the CopyOnWriteArrayList class to be introduced in this article

Open the source code of CopyOnWriteArrayList class, as follows:

You can see the array variable of the storage element of CopyOnWriteArrayList. The volatile keyword is used to ensure the visible rows of data under multithreading; At the same time, ReentrantLock is used to re-enter the lock object to ensure the safety of thread operation.

In the initialization phase, CopyOnWriteArrayList initializes an object for the array by default. Of course, there are many initialization methods, such as the following initialization method we often use. The source code is as follows:

This method means that if we pass in an ArrayList array object, we will copy the object content into the new array, and then initialize it. The operation is as follows:

List list = new ArrayList<>();
...
//CopyOnWriteArrayList copies the contents of the list and creates a new array
CopyOnWriteArrayList copyList = new CopyOnWriteArrayList<>(list);

CopyOnWriteArrayList is used to copy and then write the contents of the original array. Is there a conflict in multi-threaded operations?

Let's look at its implementation again!

3, Common methods

3.1 adding elements

The add() method is the entry of the added element of CopyOnWriteArrayList!

CopyOnWriteArrayList can ensure safe operation under multithreading. The add() method is indispensable. The source code is as follows:

The operation steps are as follows:

• 1. Obtain the object lock;
• 2. Get the contents of the array;
• 3. Copy the contents of the original array to the new array;
• 4. Write data;
• 5. Point the array variable address to the new array;
• 6. Release the object lock;

In Java, there are two ways to ensure thread operation safety in terms of exclusive lock. One is to use synchronized provided by virtual machine to ensure concurrency safety, and the other is to use reentrant lock under JUC package to ensure thread operation safety.

CopyOnWriteArrayList uses ReentrantLock to ensure the safety of thread operation. At the same time, array variable array uses volatile to ensure the visible rows of data under multithreading!

In addition, there are methods to add subscripts, such as add(int index, E element). The operation is similar. First find the location to be added. If it is an intermediate location, take the added location as the dividing point, copy it twice, and finally write data!

3.2. Removing elements

The remove() method is the entry of the removed element of CopyOnWriteArrayList!

The source code is as follows:

The operation is similar to the adding method. The steps are as follows:

• 1. Obtain the object lock;
• 2. Get the contents of the array;
• 3. Judge whether the removed element is the last element of the array. If it is the last element, directly copy the contents of the old element to the new array and reset the array value;
• 4. If it is an intermediate element, take index as the dividing point and copy it in two sections;
• 5. Point the array variable address to the new array;
• 6. Release the object lock;

Of course, the removal method also includes object-based remove(Object o). The principle is the same. First find the subscript of the element, and then perform the removal operation.

3.3. Query elements

The get() method is the entry of the query element of CopyOnWriteArrayList!

The source code is as follows:

public E get(int index) {
    //Get the contents of the array directly through the subscript
    return get(getArray(), index);
}

Because the query does not involve data operations, it does not need to be processed with locks!

3.4 traversal elements

As we mentioned above, the number of modifications is basically inconsistent with the number of modifications in the iterator when traversing the element, resulting in throwing exceptions during inspection. Let's take a look at the implementation of CopyOnWriteArrayList iterator.

Open the source code and you can find that the iterator returned by CopyOnWriteArrayList is COWIterator. The source code is as follows:

public Iterator iterator() {
    return new COWIterator(getArray(), 0);
}

Open the COWIterator class, which is actually a static internal class of CopyOnWriteArrayList. The source code is as follows:

It can be seen that when using the iterator, the traversal elements come from the object array passed in by the getArray() method above, that is, the array array passed in!

It can be seen that CopyOnWriteArrayList operates on the original array when traversing with the iterator. It does not judge the number of modifications as above, so it will not throw exceptions!

Of course, it can also be concluded from the source code that when traversing elements using the iterator of CopyOnWriteArrayList, you cannot call the remove() method to remove elements, because this operation is not supported!

If you want to remove an element, you can only use the remove() method provided by CopyOnWriteArrayList instead of the remove() method of the iterator. You should pay attention to this!

4, Summary

CopyOnWriteArrayList is a typical dynamic array operation class with read-write separation!

When writing data, copy the contents of the old array, then write data to the new array, and finally return the new array memory address to the array variable; The removal operation is similar, except that the method is to remove elements rather than add elements; The query method is not locked because it does not involve thread operation!

Because the contents of CopyOnWriteArrayList are not locked, the data can also be read when writing data, so the performance is greatly improved, but there are also defects. In the case of reading and writing, the latest data may not be read in real time, such as the following operations:

public static void main(String[] args) throws InterruptedException {
    final CopyOnWriteArrayList list = new CopyOnWriteArrayList<>();
 list.add("a");
 list.add("b");
 for (int i = 0; i < 5; i++) {
 final int j =i;
 new Thread(new Runnable() {
 @Override
 public void run() {
 //Write data
 list.add("i-" + j);
 //Read data
 for (String str : list) {
 System.out.println("thread -" + Thread.currentThread().getName() + "，Read content:" + str);
 }
 }
 }).start();
 }
}

Create five new threads and add elements to the list. The execution results are as follows:

You can see that the reading contents of the five threads are different!

Therefore, CopyOnWriteArrayList is very suitable for application scenarios with more reading and less writing!

5, Reference

1,JDK1. 7&JDK1. 8 source code

2,Nuggets - embrace your dreams - talk about CopyOnWriteArrayList in Java