preface
Today we’ll take a look at CopyOnWriteArrayList, a more secure collection than ArrayList, and analyze the source code with the following questions.
- How does CopyOnWriteArrayList ensure thread safety?
- What are the pros and cons of CopyOnWriteArrayList?
- What’s the difference between CopyOnWriteArrayList and ArrayList?
- Know CopyOnWriteArraySet?
Inheritance relationships
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable,
java.io.Serializable {
//......
}
Copy the codeCopyOnWriteArrayList implements List, RandomAccess, Cloneable and Serializable List and Serializable
Core fields
Final transient ReentrantLock lock = new ReentrantLock(); Private transient volatile Object[] array;Copy the codeFrom the above two core fields, you can guess that CopyOnWriteArrayList is internally locked to ensure thread-safety. So how does it work? So let’s move on.
A constructor
/** * the default constructor, which initializes an empty array */ publicCopyOnWriteArrayList() {
setArray(new Object[0]);
}
Copy the codeA quick look at the other two constructors is as follows:
public CopyOnWriteArrayList(Collection<? extends E> c) {
Object[] elements;
if(c.getClass() == CopyOnWriteArrayList.class) elements = ((CopyOnWriteArrayList<? >)c).getArray();else {
elements = c.toArray();
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elements.getClass() ! = Object[].class) elements = Arrays.copyOf(elements, elements.length, Object[].class); }setArray(elements);
}
public CopyOnWriteArrayList(E[] toCopyIn) {
setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
Copy the codeModify the
public E set(int index, E element) {final ReentrantLock lock = this.lock; lock.lock(); Try {// get old array Object[] elements = getArray(); E oldValue = get(elements, index); // If the old data is different from the new data insertedif(oldValue ! = element) { int len = elements.length; Object[] newElements = arrays.copyof (elements, len); newElements[index] = element; // Set array to newElementssetArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
returnoldValue; } finally {// unlock lock.unlock(); }}Copy the codeYou can see that writing data is thread safe by locking it, and by copying a new array. Then change the Value corresponding to index in the new array, and finally assign the new array to the underlying array of CopyOnWriteArrayList, which can also be said to point to the new array, as shown in the figure below:
- Get the old array
- Create a new array by copying the old array
- Make changes in the new array
- Array refers to the new array
add
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true; } finally { lock.unlock(); }}Copy the codeAs you can see, similar to the set() method, the lock is used to ensure thread-safety. Then a new array is created to add elements, and the new array is assigned to array.
To obtain
public E get(int index) {
return get(getArray(), index);
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
Copy the codeAs you can see from the get() method source, the element is not locked when obtained from CopyOnWriteArrayList. So we have to think about what happens when we write data, when we don’t finish writing data. To read the data, so can we get the data accurately? And the important thing is that in the get() method, you operate directly on the underlying array. That means that when we read the data, it’s possible that we’re getting old data. That is to say, CopyOnWriteArrayList can not guarantee the real-time data, the main reasons can be thought from the following points.
- There is no locking in the get() method
- It reads data from the underlying array
delete
Public E remove(int index) {final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; E oldValue = get(elements, index); int numMoved = len - index - 1;if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
returnoldValue; } finally {// unlock lock.unlock(); }}Copy the codeAs you can see, the remove() method is the same, with locks to ensure thread-safety.
Other methods
/** * Obtain the underlying array */ final Object[]getArray() {
returnarray; } /** * Set the underlying array */ final voidsetArray(Object[] a) { array = a; } /** * Get array size */ public intsize() {
returngetArray().length; } /** * Check whether the array is empty */ public BooleanisEmpty() {
return size() == 0;
}
Copy the codeAdvantages and disadvantages
By looking at the source code, we can see that CopyOnWriteArrayList’s biggest advantage is thread-safe, but also the most prominent advantage. It does not lock when it reads, but only when it writes. This also presents a disadvantage of CopyOnWriteArrayList, which is that it cannot read real-time data. Because it is possible that a read is performed before the write operation is complete, the old data will be read.
CopyOnWriteArraySet
Next we have a brief look at CopyOnWriteArrayList cousin CopyOnWriteArraySet, the main source code is as follows.
private final CopyOnWriteArrayList<E> al;
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
Copy the codeThe constructor initializes a CopyOnWriteArrayList, which means that CopyOnWriteArraySet is internally implemented using CopyOnWriteArrayList. Let’s look at a few other methods.
public boolean add(E e) {
return al.addIfAbsent(e);
}
public boolean remove(Object o) {
return al.remove(o);
}
Copy the codeAs you can see, add() and remove() are implemented by CopyOnWriteArrayList.
conclusion
By analyzing the source code, we understand the internal implementation of CopyOnWriteArrayList, and how it guarantees thread safety, but also understand CopyOnWriteArraySet.