1, ArrayList is not secure
1. Fault phenomenon
public class NotSafeDemo {
public static void main(String[] args) {
List<String> list = new ArrayList();
for (int i = 0; i < 30; i++) {
//Multiple threads modify the collection at the same time
new Thread(() -> {
//Add content to collection
list.add(UUID.randomUUID().toString().substring(0, 8));
//Get content from collection
System.out.println(list);
}, String.valueOf(i)).start();
}
}
}
Operation results:
An exception occurred during the operation. The exception information is: Java util. ConcurrentModificationException.
If only one thread operates ArrayList, there is no problem.
2. Analyze the causes
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!! Here will modCount++
elementData[size++] = e;
return true;
}
You can see that the add() method is not synchronized, and thread safety cannot be guaranteed.
In the internal class Itr of ArrayList, there is such a method:
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Here, judge whether the real modCount is equal to the expected modCount. If not, a concurrent modification exception will be thrown to prevent multiple threads from operating on ArrayList.
So how to solve the thread safety problem of List type?
2, Scheme I
1. Use Vector
Inheritance structure:
Vector is a vector queue, which is jdk1 Class added by version 0. It inherits from AbstractList and implements List, randomaccess and clonable interfaces. Vector inherits AbstractList and implements List; Therefore, it is a queue that supports related functions such as addition, deletion, modification and traversal.
Vector implements RandmoAccess interface, which provides random access function. RandmoAccess is implemented by List in java to provide fast access for List. In vector, we can quickly obtain the element object through the element serial number; This is fast random access. Vector implements the clonable interface, that is, the clone() function. It can be cloned.
Unlike ArrayList, operations in Vector are thread safe.
2. Code implementation
/**
* List Collection thread safety case
*/
public class SafeListDemo {
public static void main(String[] args) {
List<String> list = new Vector<>();
for (int i = 0; i < 30; i++) {
//Multiple threads modify the collection at the same time
new Thread(() -> {
//Add content to collection
list.add(UUID.randomUUID().toString().substring(0, 8));
//Get content from collection
System.out.println(list);
}, String.valueOf(i)).start();
}
}
}
3. Principle analysis
View the add method of Vector
/**
* Appends the specified element to the end of this Vector.
*
* @param e element to be appended to this Vector
* @return {@code true} (as specified by {@link Collection#add})
* @since 1.2
*/
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
The add method is synchronized, thread safe! Therefore, there are no concurrent exceptions.
3, Scheme II
1. Use Collections tool class
Collections provides the method synchronizedList to ensure that the list is thread safe.
2. Code implementation
public class SafeListDemo {
public static void main(String[] args) {
List<String> list = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < 30; i++) {
//Multiple threads modify the collection at the same time
new Thread(() -> {
//Add content to collection
list.add(UUID.randomUUID().toString().substring(0, 8));
//Get content from collection
System.out.println(list);
}, String.valueOf(i)).start();
}
}
}
3. Principle analysis
View method source code:
/**
* Returns a synchronized (thread-safe) list backed by the specified
* list. In order to guarantee serial access, it is critical that
* <strong>all</strong> access to the backing list is accomplished
* through the returned list.<p>
*
* It is imperative that the user manually synchronize on the returned
* list when iterating over it:
* <pre>
* List list = Collections.synchronizedList(new ArrayList());
* ...
* synchronized (list) {
* Iterator i = list.iterator(); // Must be in synchronized block
* while (i.hasNext())
* foo(i.next());
* }
* </pre>
* Failure to follow this advice may result in non-deterministic behavior.
*
* <p>The returned list will be serializable if the specified list is
* serializable.
*
* @param <T> the class of the objects in the list
* @param list the list to be "wrapped" in a synchronized list.
* @return a synchronized view of the specified list.
*/
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
You can see that it helps us create a synchronized collection.
Take synchronized list as an example:
/**
* @serial include
*/
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
SynchronizedList(List<E> list, Object mutex) {
super(list, mutex);
this.list = list;
}
public boolean equals(Object o) {
if (this == o)
return true;
synchronized (mutex) {return list.equals(o);}
}
public int hashCode() {
synchronized (mutex) {return list.hashCode();}
}
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
synchronized (mutex) {return list.remove(index);}
}
public int indexOf(Object o) {
synchronized (mutex) {return list.indexOf(o);}
}
public int lastIndexOf(Object o) {
synchronized (mutex) {return list.lastIndexOf(o);}
}
public boolean addAll(int index, Collection<? extends E> c) {
synchronized (mutex) {return list.addAll(index, c);}
}
public ListIterator<E> listIterator() {
return list.listIterator(); // Must be manually synched by user
}
public ListIterator<E> listIterator(int index) {
return list.listIterator(index); // Must be manually synched by user
}
public List<E> subList(int fromIndex, int toIndex) {
synchronized (mutex) {
return new SynchronizedList<>(list.subList(fromIndex, toIndex),
mutex);
}
}
@Override
public void replaceAll(UnaryOperator<E> operator) {
synchronized (mutex) {list.replaceAll(operator);}
}
@Override
public void sort(Comparator<? super E> c) {
synchronized (mutex) {list.sort(c);}
}
/**
* SynchronizedRandomAccessList instances are serialized as
* SynchronizedList instances to allow them to be deserialized
* in pre-1.4 JREs (which do not have SynchronizedRandomAccessList).
* This method inverts the transformation. As a beneficial
* side-effect, it also grafts the RandomAccess marker onto
* SynchronizedList instances that were serialized in pre-1.4 JREs.
*
* Note: Unfortunately, SynchronizedRandomAccessList instances
* serialized in 1.4.1 and deserialized in 1.4 will become
* SynchronizedList instances, as this method was missing in 1.4.
*/
private Object readResolve() {
return (list instanceof RandomAccess
? new SynchronizedRandomAccessList<>(list)
: this);
}
}
The methods in this class are also synchronized by implementing synchronized synchronization locks, which is not efficient.
4, Scheme III (key)
1. Use CopyOnWriteArrayList
First, we will learn about CopyOnWriteArrayList. Its features are as follows:
It is equivalent to a thread safe ArrayList. Like ArrayList, it is a variable array; However, unlike ArrayList, it has the following features:
(1) it is most suitable for applications with the following characteristics: the List size is usually kept very small, read-only operations are far more than variable operations, and conflicts between threads need to be prevented during traversal;
(2) it is thread safe;
(3) because it is usually necessary to copy the entire basic array, variable operations (add(), set(), remove(), etc.) are expensive;
(4) the iterator supports immutable operations such as hasNext(), next(), but does not support immutable operations such as remove();
(5) traversal using iterators is fast and does not conflict with other threads. When constructing an iterator, the iterator depends on an invariant array snapshot;
2. Code implementation
public class SafeListDemo {
public static void main(String[] args) {
List<String> list = new CopyOnWriteArrayList<>();
for (int i = 0; i < 30; i++) {
//Multiple threads modify the collection at the same time
new Thread(() -> {
//Add content to collection
list.add(UUID.randomUUID().toString().substring(0, 8));
//Get content from collection
System.out.println(list);
}, String.valueOf(i)).start();
}
}
}
3. Core idea
Core idea: low efficiency of exclusive lock: the idea of separation of read and write is adopted to solve it
The write thread obtains the lock, and other write threads are blocked.
Copy ideas:
When we add elements to a container, instead of directly adding them to the current container, we first Copy the current container, Copy a new container, and then add elements to the new container. After adding elements, we point the reference of the original container to the new container.
At this time, a new problem will be thrown out, that is, the problem of inconsistent data. If the write thread has not had time to write memory, other threads will read dirty data.
This is the idea and principle of CopyOnWriteArrayList.
4. Cause analysis: dynamic array and thread safety
Next, the principle of CopyOnWriteArrayList is further explained from the two aspects of "dynamic array" and "thread safety".
Dynamic array mechanism:
(1) it has a "volatile array" to hold data. When "add / modify / delete" data, an array will be created, and the updated data will be copied to the new array, and then the
Array is assigned to "volatile array", which is why it is called CopyOnWriteArrayList;
(2) because it creates new arrays when "adding / modifying / deleting" data, CopyOnWriteArrayList is inefficient when it involves modifying data; However, it is more efficient to only perform traversal search.
Thread safety mechanism:
(1) implemented by volatile and mutex.
(2) save data through "volatile array". When a thread reads the volatile array, it can always see the last write of the volatile variable by other threads; In this way, the "read" function is provided through volatile
The data obtained is always up-to-date.
(3) protect data through mutual exclusion lock. When you add / modify / delete data, you will first "obtain the mutex", and then update the data to the "volatile array" after modification, and then "release the mutex"
Lock "to achieve the purpose of protecting data.
5. "Copy on write"
(1) improve the performance without locking and make mistakes; The locking data is consistent and the performance is degraded;
(2) CopyOnWriteArrayList definition:
/**
* 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 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();
}
}