“This is the 30th day of my participation in the First Challenge 2022. For details: First Challenge 2022”
- J3 – west
- Collection (source code # CopyOnWriteArrayList)
An implementation class under the List interface that is similar to ArrayList, but not so similar.
Multithreaded environment often need a thread-safe collection class to realize data storage, affirmation is the Vector of familiar, Collections. SynchronizedXXX, ConcurrentHashMap, etc. But the following I want to analyze CopyOnWriteArrayList is also a thread-safe environment can be used in the collection class, in the actual application is also useful, the following will take you together to analyze it!
Article all source code environment: JDK11
1, the introduction of
A thread-safe variant of ArrayList, in which all mutable operations (add, set, and so on) are implemented by a new copy of the underlying array.
Copying can be expensive in space, especially when there are a lot of elements in the collection. Mutable operations can be fatal in high-concurrency, very large projects, and hang up every minute.
In its implementation logic is reading and writing, speaking, reading and writing environment, the read operation is the original array itself, and the write operation will copy a copy from the original array, all the modification operations only on this copy to the original array does not have any effect, after last modified data will replace modify complete a copy of the original array, to complete a data change operation. The problem here is that data can not be modified and read in real time, that is, data consistency cannot be guaranteed in real time, only the final consistency of data.
By reading and writing separation, modify data also won’t appear when the loop iteration ConcurrentModificationException anomalies.
2. Attribute analysis
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
// The lock object on which data is dependent
final transient Object lock = new Object();
// An array of elements
private transient volatile Object[] array;
}
Copy the codeThe CopyOnWriteArrayList object has very few properties, just two:
lock: The lock object to be obtained when modifying data is modified by transient keyword, indicating that it has its own set of serialization logic. In JDK8, the lock object is not a lock but a ReentrantLock lock.arrayVolatile: Array type property that is volatile. In a multithreaded environment, one change is immediately visible to other threads.
constructor
public CopyOnWriteArrayList(a) {
// Set an array of length 0 to array without a constructor
setArray(new Object[0]);
}
// Construct a CopyOnWriteArrayList object that specifies the collection data directly
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); }// Construct a CopyOnWriteArrayList object that specifies an array directly
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Copy the codeAll of these constructors end up calling the setArray method as follows:
final void setArray(Object[] a) {
// Assign a value to the array and replace the reference to the array
array = a;
}
Copy the codeArray.copyof methods are explained in this article: 👉 ArrayList source code parsing for non-expert readers
4. Set method
public E set(int index, E element) {
/ / lock
synchronized (lock) {
// Get the array
Object[] es = getArray();
// Find the data elements according to the table below
E oldValue = elementAt(es, index);
// Determine whether the element at the subscript is equal to the element to be set
if(oldValue ! = element) {// Not equal, make a copy of the group
es = es.clone();
// Set the element at the corresponding subscript
es[index] = element;
}
// Ensure volatile write semantics even when oldvalue == element
// Set the manipulated array copy back
setArray(es);
// Return the old finger from index
return oldValue;
// Unlock and exit}}Copy the codeSynchronized method, which is used in JDK1.8 as a ReentrantLock, The reason for this is that SYNCHRONIZED performance is better than ReentrantLock in JDK11.
Set method implementation logic is very simple, first find the element at the corresponding subscript, determine whether the set element is equal to the old element, not equal to the array copy, operation copy and the completed copy assigned to array array; Otherwise, no setting operation is performed and the element at index is returned directly, ending the method.
One point to note is the copy method, which is a waste of memory and time. If you have a large set element and use set methods frequently, CopyOnWriteArrayList is not recommended.
5. Add method
public boolean add(E e) {
/ / lock
synchronized (lock) {
// Get an array object
Object[] es = getArray();
// Get the array length
int len = es.length;
// Copy the array with len + 1
es = Arrays.copyOf(es, len + 1);
// Add the element at the end of the array
es[len] = e;
// Set the array after the operation
setArray(es);
// Return success
return true; }}Copy the codeWhen adding data, a new array whose length is 1 longer than the original number is copied through the synchronized keyword, and data is added at the end to complete the operation of adding elements.
6. Add (int, E
public void add(int index, E element) {
/ / lock
synchronized (lock) {
// Get the array
Object[] es = getArray();
// Get the array length
int len = es.length;
// determine whether the subscript is illegal
if (index > len || index < 0)
throw new IndexOutOfBoundsException(outOfBounds(index, len));
/ / the new array
Object[] newElements;
// The number of elements to move
int numMoved = len - index;
// If the insert happens to be at the end of the array, just like the add method
if (numMoved == 0)
newElements = Arrays.copyOf(es, len + 1);
else {
// Insert elements in the middle section
// Create a new array that is only 1 larger than the original array
newElements = new Object[len + 1];
// Copy elements from the old array starting with 0-index into the new array
System.arraycopy(es, 0, newElements, 0, index);
// Copy elements from the old array starting with index-length into the new array
System.arraycopy(es, index, newElements, index + 1,
numMoved);
}
// Place the new element at index
newElements[index] = element;
// Set the array
setArray(newElements);
// Unlock to complete the element addition}}Copy the codeWhen you add an element to a specified subscript, it is inevitable to check whether the subscript is illegal.
The second point is that the element copies that piece of code, which is somewhat novel (I think). It still copies, but inserts an element and writes it back to the array property with as little copying and moving as possible.
Remove removes elements
public E remove(int index) {
/ / lock
synchronized (lock) {
// Get the array
Object[] es = getArray();
// Get the array length
int len = es.length;
// Index can be used to fetch elements from array ？？？？？
E oldValue = elementAt(es, index);
// Count the number of elements to move
int numMoved = len - index - 1;
// Define a new array
Object[] newElements;
if (numMoved == 0)
// This is the case where the last element is removed
newElements = Arrays.copyOf(es, len - 1);
else {
// Create an array of length len-1
newElements = new Object[len - 1];
// Copy the same as the add method
System.arraycopy(es, 0, newElements, 0, index);
System.arraycopy(es, index + 1, newElements, index,
numMoved);
}
// Set the array
setArray(newElements);
// Returns the removed value
return oldValue;
/ / unlock}}Copy the codeRemove the element by subscript, according to the source code is not complicated, find the element by subscript, and then copy the element to be removed into a new array that completes the element removal.
Instead of checking the subscript, we simply fetch elements from the array based on the index passed in. ? No problem will quote ArrayIndexOutOfBoundsException wrong.
Let’s look at another method of removing by element:
public boolean remove(Object o) {
// Get the array
Object[] snapshot = getArray();
// Loop through the array to find the subscript corresponding to o, if not, return -1
int index = indexOfRange(o, snapshot, 0, snapshot.length);
// Determine the subscript and start removing elements
return index >= 0 && remove(o, snapshot, index);
}
private boolean remove(Object o, Object[] snapshot, int index) {
/ / lock
synchronized (lock) {
// Get the array
Object[] current = getArray();
// Get the array length
int len = current.length;
// Whether the array has been changed (whether the array has been replaced by another thread)
if(snapshot ! = current) findIndex: {// Have been changed, take this logic
// Find the minimum array length
int prefix = Math.min(index, len);
// Start traversal
for (int i = 0; i < prefix; i++) {
The condition is true if the address of the I subscript element is different in the current and snapshot arrays, but the value is the same
if(current[i] ! = snapshot[i] && Objects.equals(o, current[i])) {// assign the removed element to index again at index I
index = i;
// Jump out of the if statement
breakfindIndex; }}// If index is greater than len, there is no need to remove it
if (index >= len)
return false;
// The index element in the current array is equal to o
if (current[index] == o)
break findIndex;
// If the index satisfies the index range of the current array, find the index of the o element in the current array again
index = indexOfRange(o, current, index, len);
// Check if subscripts are found in the current array
if (index < 0)
return false;
}
// Not changed, go to the following logic
// Create a new array
Object[] newElements = new Object[len - 1];
// Copy the same logic as add
System.arraycopy(current, 0, newElements, 0, index);
System.arraycopy(current, index + 1,
newElements, index,
len - index - 1);
// Set the array
setArray(newElements);
// Successfully removed
return true;
/ / unlock}}Copy the codeThis approach is complicated because it prevents concurrency problems.
Here’s the general idea:
- We first get the array object and the index of the element to be removed.
- Lock and get the array object again
- Determines whether the array object obtained twice is the same
- Case 1: no, it has been replaced by another thread, so compare the index of the first element to the length of the second array and take the smaller value prefix. Then the loop starts from 0 to prefix and compares to find out whether there are elements to be removed from the array objects acquired twice. If there are, record their subscripts and jump out of Step 4 and perform Step 5. Otherwise, check whether the subscript matches the length of the second array object. Otherwise, record the subscript and go to Step 5.
- Create a new array with a length minus one. Copy the elements to the new array and set the final new array to array as the add method.
Focus on the fourth step, combined with my code comments and ideas summary, complete understanding is not a problem.
I’m not going to analyze how to add CopyOnWriteArrayList, because the principle is so simple that I know how to get elements without reading the source code.
8, source analysis summary
This article does not say how thorough the introduction of CopyOnWriteArrayList, but it can be said that the key source is certainly analyzed to, the implementation of the idea is also introduced in detail, the following according to the analysis of this article on CopyOnWriteArrayList to do a source summary:
- CopyOnWriteArrayList uses the synchronized keyword in JDK11 to ensure thread safety.
- All 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), relatively low performance.
- The read operation of CopyOnWriteArrayList supports random access and the time complexity is O(1).
- CopyOnWriteArrayList uses the idea of read and write separation, read operation does not lock, write operation lock, and write operation occupies a large memory space, so it is suitable for the occasion of read more write less.
- CopyOnWriteArrayList only guarantees final consistency, not real-time consistency.
Well, that’s it for today, so follow me and we’ll see you next time.
Contact information:
QQ: 1491989462
WeChat: 13207920596
Be a good friend, a “like” friend.
-
Due to the lack of knowledge of the blogger, there will be mistakes, if you find mistakes or bias, please comment to me, I will correct it.
-
If you think the article is good, your retweets, shares, likes and comments are the biggest encouragement to me.
-
Thank you for reading. Welcome and thank you for your attention.
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
Personal site: J3
CSDN:J3
The nuggets:J3
Zhihu:J3
This is a technical average, but keen to share; Inexperienced but thick-skinned; Young and good-looking programmers who insist on talent for a living.
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^