Art is long, life is long
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
-
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(1) the lock
Used to lock when modifying, use transient modifier to indicate not automatic serialization.
(2) array
Where elements are actually stored, use transient to indicate that they are not serialized automatically, and volatile to indicate that changes made by one thread to the field are immediately visible to another thread.
Question: Why is there no size field? Listen to the breakdown.
CopyOnWriteArrayList() 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 codeCopyOnWriteArrayList constructor
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(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 codeCopyOnWriteArrayList(E[] toCopyIn) constructor
Copy the toCopyIn element to the current list array.
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Copy the codeThe 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 the element array;
(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) Put the new 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) Unlock;
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 whether the element exists in the array snapshot;
AddIfAbsent (E E, Object[] snapshot) addIfAbsent(E E, Object[] snapshot)
(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 whose length is equal to the length of the original array plus 1, 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 the element array;
(2) Return the element 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) Get 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 the new array is assigned to the array property of the current object;
(4) If the last element is not removed, create a new len-1 array, copy the original array to 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 codeconclusion
(1) CopyOnWriteArrayList uses ReentrantLock to lock to ensure thread safety;
(2) The write operation of CopyOnWriteArrayList must first copy a new array, modify it in the new array, and then replace the old array with the new array after modification, so the space complexity is O(n), and the performance is low;
(3) The read operation of CopyOnWriteArrayList supports random access, and the time complexity is O(1);
(4) CopyOnWriteArrayList uses the idea of reading and writing separation, read operation without lock, write operation lock, and write operation occupies a large memory space, so it is suitable for read and write less occasion;
(5) CopyOnWriteArrayList only guarantees final consistency, not real-time consistency;
eggs
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.
The last
Author: Tong Brother
Reference: www.cnblogs.com/tong-yuan/