Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "what is CopyOnWriteArrayList in the series of advanced concurrent programming". Many people will encounter this dilemma in the operation of actual cases, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

1. Test you

Before you look at the details, let's think about the following questions:

In the CopyOnWriteArrayList class name, there is the familiar ArrayList, so is there anything you need to pay attention to when using ArrayList in daily development?

When CopyOnWrite is translated into Chinese, it is copied when writing. What exactly is copying when writing?

Is there anything to pay attention to when it comes to the idea of copying while writing, in what scenarios are suitable for application?

With the above questions, let's start today's content together.

two。 Case 2.1.ArrayList stepped on the pit 2.1.1. Same ancestors, never forget each other.

The name of the CopyOnWriteArrayList class contains ArrayList, which indicates that they are related by blood and originated from an ancestral ancestor. Let's look at the class diagram first:

2.1.2.ArrayList can't be used like that.

From the class diagram, we can see that both CopyOnWriteArrayList and ArrayList implement the same interface. In order to make it easier for you to understand CopyOnWriteArrayList better, let's start with ArrayList.

Next I will use ArrayList in my daily development, and I will share with you some cases that need to be consciously avoided.

We know that the underlying implementation of ArrayList is based on array data structures, and its characteristics are that it has all the characteristics of an array and supports dynamic expansion. So when we use ArrayList, we actually use it as a container. Can you think of any common operations for containers?

Put an element in a container

Update an element in the container

Delete an element in the container

Get an element in the container

Loop through the elements in the container

The above are some of our high-frequency operations when using containers in the project. For each operation, I will not take you to demonstrate one by one, you should be very familiar with it. Here we focus on looping through the elements in the container.

We know that the container's loop traversal operation can be done through a for loop or an iterator loop. From the class diagram above, we know that the top level of ArrayList implements the Iterable interface, so it supports iterator operation, where the iterator design pattern is applied. Let's not delve into the content of design patterns for the time being. If time permits, I will share with you my understanding of object-oriented programming, design principles, design ideas and design patterns in the next series.

Next, there are a few things I need to pay attention to as I traverse through the ArrayList iterator. We go directly to the code (show me the code):

Package com.anan.edu.common.newthread.collection;import java.util.ArrayList;import java.util.Iterator;/** * details to pay attention to when demonstrating ArrayList iterator traversal * * @ author ThinkPad * @ version 1.0 * @ date 10:50 on 2020-12-26 * / public class ShowMeArrayList {public static void main (String [] args) {/ / create an ArrayList ArrayList list = new ArrayList () / / add elements list.add ("zhangsan"); list.add ("lisi"); list.add ("wangwu"); / * * normal loop iterative output * * / Iterator iter = list.iterator () While (iter.hasNext ()) {System.out.println ("the person currently obtained from the container is:" + iter.next ());}

Execution result:

The person currently obtained from the container is: zhangsan the person currently obtained from the container is: lisi, the person currently obtained from the container is: wangwu

By creating an ArrayList instance, add three elements: zhangsan, lisi, wangwu, and iterate through the output. In this way, we have prepared the case base case code.

Let's do some evolutionary operations:

During traversal, add or remove elements from the collection through ArrayList

Delete elements in the collection through the iterator Iterator during traversal

Show me code:

/ * * during traversal, through Iterator instance: delete element * expected result: normal execution * * / Iterator iter = list.iterator (); while (iter.hasNext ()) {/ / if the current traversal reaches lisi, we delete lisi from the collection String name = iter.next (); if ("lisi" .equals (name)) {iter.remove () / / No exception why?} System.out.println ("the person currently obtained from the container is:" + name);} System.out.println ("after deleting the element, there are still elements in the collection:" + list) / / the person who gets the execution result from the container is: zhangsan currently gets it from the container: lisi currently gets it from the container: after wangwu deletes the element There are also elements in the collection: [zhangsan, wangwu] / * * / / * * during traversal, add or delete elements through ArrayList instance * expected result: an exception is thrown through traversal * * / Iterator iter = list.iterator () While (iter.hasNext ()) {/ / if currently traversing lisi, we add to the collection: Xiaoming String name = iter.next (); if ("lisi" .equals (name)) {list.add ("Xiaoming"); / / after this line of code, the iterator continues to throw an exception why?} System.out.println ("the person currently fetched from the container is:" + name) } / / the person who gets the execution result from the container is: zhangsanException in thread "main" java.util.ConcurrentModificationException. The person currently obtained from the container is: lisi at java.util.ArrayList$Itr.checkForComodification (ArrayList.java:909) at java.util.ArrayList$Itr.next (ArrayList.java:859) at com.anan.edu.common.newthread.collection.ShowMeArrayList.main (ShowMeArrayList.java:31) 2.1.3. The logic behind it

The above example demonstrates that during the iterative operation of ArrayList, the program will not throw an exception when deleting elements through the iterator; adding and deleting through ArrayList will cause subsequent iterative operations to throw exceptions. Do you know the logic behind this?

On this issue, I would like to share with you from two angles:

Why are elements not allowed to be added or removed from the original collection during the iterator operation?

In ArrayList, how to control the iterative operation, how to detect whether the original collection has been added or deleted?

In order to clarify this problem, let's start with the picture (a picture is worth a thousand words):

Why is it not allowed to add or remove elements from the original collection during iterator operation? After this question, let's take a closer look at how ArrayList detects the control. During the iteration, the original set has the problem of adding or deleting operations.

Here I will show you the source code, which is what I suggest you should do frequently. Get into the habit of looking at the source code. We often say: there are no secrets under the source code.

/ * * ArrayList's iterator is an inner class * / / * An optimized version of AbstractList.Itr*/private class Itr implements Iterator {/ / iterator internal cursor that identifies the next array subscript of the element to be traversed, int cursor; / / index of next element to return / / identifies the last element that has been iterated, int lastRet =-1; / / index of last element returned -1 if no such / / Note: this variable is very important because it identifies the number of times the original collection was added and deleted during the iteration of the iterator / / the initial value is a member variable in the collection: modCount (set added and deleted operation count) int expectedModCount = modCount Itr () {}....} / * * iterator hasNext method * / public boolean hasNext () {/ / simply determine whether cursor is equal to size / / equal, then the traversal ends / / is not equal, then continue traversing return cursor! = size } / * * iterator next method * / public E next () {/ / key code: check whether the original collection has been added or deleted / / if there is an add or delete operation, then expectedModCount! = modCount / / throw exception checkForComodification (); int I = cursor; if (I > = size) throw new NoSuchElementException (); Object [] elementData = ArrayList.this.elementData; if (I > = elementData.length) throw new ConcurrentModificationException () Cursor = I + 1; return (E) elementData [lastRet = I];} / * * iterator checkForComodification method * / final void checkForComodification () {if (modCount! = expectedModCount) throw new ConcurrentModificationException ();}

Through the source code analysis of the ArrayList internal class iterator Itr, we can see that the source code implementation of the iterator is very simple, and congratulations! Unwittingly, you also learned the implementation of iterator design patterns.

Finally, we solve the problem of modCount member variables by looking at the source code of the add and remove methods in ArrayList:

/ * ArrayList's add method * / / * Appends the specified element to the end of this list.* @ param e element to be appended to this list* @ return true (as specified by {@ link Collection#add}) * / public boolean add (E) {/ / comment: will add 1 / / continue to look at the ensureCapacityInternal method ensureCapacityInternal (size + 1); / / Increments modCounting! The ensureCapacityInternal method of elementData [size++] = e; return true;} / * * ArrayList * focuses on the ensureExplicitCapacity method * / private void ensureExplicitCapacity (int minCapacity) {/ / add the modCount variable to 1 modCount++; / / overflow-conscious code if (minCapacity-elementData.length > 0) / / expansion operation, leaving you to see grow (minCapacity) Remove method of / * * ArrayList * / / * Removes the element at the specified position in this list.* Shifts any subsequent elements to the left (subtracts one from their* indices). * * @ param index the index of the element to be removed* @ return the element that was removed from the list* @ throws IndexOutOfBoundsException {@ inheritDoc} * / public E remove (int index) {rangeCheck (index); / / add the modCount variable to 1 modCount++; E oldValue = elementData (index); int numMoved = size-index-1 If (numMoved > 0) System.arraycopy (elementData, index+1, elementData, index, numMoved); elementData [--size] = null; / / clear to let GC do its work return oldValue;}

Through diagrams, and source code analysis, you should now have a better understanding of ArrayList and its internal iterator Itr, and make good use of ArrayList in your project.

This is what I want to share with you: keep learning, know what it is, and know why, a spirit of dedicated research. Young people browse less Douyin, Kuaishou and watch less live streaming. These things will not bring you any positive value except to consume your spirit.

2.2.CopyOnWriteArrayList explains the first experience of 2.2.1.CopyOnWriteArrayList in detail

In order to make it easier for you to understand CopyOnWriteArrayList, I take great pains to take you all the way to analyze ArrayList. Now let's take a visual look at CopyOnWriteArrayList. It is also through the previous case, that is, during the iterator iteration, to add or remove elements from the original collection.

When we demonstrated the case through ArrayList, you remember that an exception was thrown. As for the cause of the exception in the previous content, I took you to do a special analysis. If you don't remember, I suggest you go back and have a look.

Now I'll focus on demonstrating the case through CopyOnWriteArrayList to see if an exception will be thrown in the same scenario. You need to focus on this place.

Show me the code:

Package com.anan.edu.common.newthread.collection;import java.util.Iterator;import java.util.concurrent.CopyOnWriteArrayList;/** * details to pay attention to when demonstrating CopyOnWriteArrayList iterator traversal * * @ author ThinkPad * @ version 1.0 * @ date 10:50 on 2020-12-26 * / public class ShowMeCopyOnWriteArrayList {public static void main (String [] args) {/ / create a CopyOnWriteArrayList CopyOnWriteArrayList list = new CopyOnWriteArrayList () / / add elements list.add ("zhangsan"); list.add ("lisi"); list.add ("wangwu"); / * * during traversal, through the CopyOnWriteArrayList instance: add or delete elements * expected result: normal execution * * / Iterator iter = list.iterator () While (iter.hasNext ()) {/ / if currently traversing lisi, we add to the collection: Xiaoming String name = iter.next (); if ("lisi" .equals (name)) {list.add ("Xiaoming"); / / will not throw an exception why?} System.out.println ("the person currently fetched from the container is" + name). } System.out.println ("after adding elements, there are still elements in the collection:" + list);}}

Execution result:

The person currently obtained from the container is: zhangsan currently gets from the container: lisi currently obtains from the container: after wangwu adds elements, there are still elements in the collection: [zhangsan, lisi, wangwu, Xiao Ming]

As you can see from the execution results, using CopyOnWriteArrayList, a new element, Xiao Ming, is added to the original collection during the iterator iteration. The iterator continues to iterate without throwing an exception, and the final print shows that Xiaoming confirms that it has been added to the collection.

Are you a little surprised at this result? It doesn't feel like the same routine with ArrayList, right? How on earth does it come true?

2.2.2. Copy thought while writing

Just now we have done a case demonstration comparison between CopyOnWriteArrayList and ArrayList, and found that they are very different in the implementation results. The essential reason for the difference is the keyword in the name of the CopyOnWriteArrayList class: CopyOnWrite, which is translated into Chinese to copy when writing.

What exactly is copy-on-write? The so-called copy while writing, its intuitive meaning is:

I already have a set A when I need to add an element to set An or delete an element

Keep set A unchanged and copy a new set B from set A.

Corresponding to add or delete elements to the new set B, point A to the new B collection after the operation is completed, that is, replace the old collection with the new collection

You see, this is the idea copied when writing, and it is not difficult to understand. What's the advantage of doing this? The advantage is that when we access the collection through the iterator, we can add and delete collection elements to the collection at the same time, effectively avoiding the conflict between accessing the collection (read operation) and updating the collection (write operation). Maximize the concurrent access performance of the collection.

So with regard to CopyOnWriteArrayList, how does it maximize concurrent access? Its implementation principle is not complicated, since it is concurrent access, the issue of thread safety can not be avoided, you should also think that locking is necessary first.

In addition to locking, we also need to consider improving the ability of concurrent access. How to improve it? The implementation is also very simple, with locks for write operations and no locks for read operations. In this way, it maximizes the ability of concurrent access, which is very suitable for business scenarios with more reads and less writes. This is actually one of the main application scenarios where we use CopyOnWriteArrayList in the project.

2.2.3.CopyOnWriteArrayList source code analysis

Through the first two summaries, we have figured out the application scenario of CopyOnWriteArrayList and understood the idea of copying when writing. In your project, according to the business needs, when we design the business structure, we can learn from the idea of copying when writing to solve the actual business problems. Be sure to learn how to use it. As for how to play it, it will be left to you.

Next, let me take you to look at the source code implementation of the key methods of CopyOnWriteArrayList to further deepen your understanding of the idea of copying while writing. We look at it through two main set operations, which are:

Add collection element (write operation): add

/ * Appends the specified element to the end of this list.** @ param e element to be appended to this list* @ return {@ code true} (as specified by {@ link Collection#add}) * / public boolean add (E) {/ / write operation, need to lock final ReentrantLock lock = this.lock; lock.lock (); try {/ / copy the original collection and add the new element to the replication collection Object [] elements = getArray () Int len = elements.length; Object [] newElements = Arrays.copyOf (elements, len + 1); newElements [len] = e; / / replace the original set setArray (newElements) with the new collection; return true;} finally {lock.unlock ();}}

Access collection elements (read operation): get

/ * * {@ inheritDoc} * * @ throws IndexOutOfBoundsException {@ inheritDoc} * / public E get (int index) {/ / get the elements in the collection. Read operations do not require locking return get (getArray (), index);} private E get (Object [] a, int index) {return (E) a [index];}

Through the add, get method source code to verify the conclusion of our previous analysis: write operation locking, read operation does not need locking.

Finally, we end this sharing in the form of a question and answer. The idea of replication while writing is suitable for business scenarios with more reads and less writes to maximize the concurrent access ability of the collection. We say: everything has two sides. Do you know the limitations of the other side of it?

We give the answer directly, and the limitations of copying ideas when writing are:

More consumption of space resources, write operations from the old collection, copy to a new collection, that is, new and old collections exist at the same time, more memory resources

In addition, if the write operation is locked and the read operation is not locked, there will be the problem of overdue reading.

Combined with the above two points, when you apply the idea of replication when writing to a project for business architecture design, or when using CopyOnWriteArrayList, be sure to consider whether overdue reading is acceptable in the business.

This is the end of "what is CopyOnWriteArrayList in the Advanced concurrent programming Series". Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.