First look and then like, give yourself a little time to think, wechat search [Silent King 2] focus on this talented programmer. This article has been collected at GitHub github.com/itwanger, along with interview questions compiled by top companies, and my series of articles.

In my few interview experiences, an interviewer surnamed Ma impressed me deeply. Nine years later, I can still remember his few posts.

Old Horse: “Brother, is ArrayList thread safe?” Wang 2: “no.” Old horse: “that have thread safe List?” Wang 2: “Yes, Vector.” Old horse: “anything else?” Wang er: “Isn’t Vector enough?” The old horse looked at his watch on his left wrist and said, “That’s about it for today. You go home and wait for notice.”

(No, didn’t I just come in, answer three questions, and that’s it?)

Now I can’t help but blush when I recall how confused I looked at that time. What Ma meant was to tell me about Java’s CopyOnWriteArrayList. Unfortunately, I hardly used this class at that time, and I didn’t know it was a thread-safe List.

Are there any holes in the ground? I want to jump in.

True warriors are brave enough to face the worst of the past. After years of hard work, my technical skills have greatly improved, and it’s time to unleash a wave of damage. I hope this article can help students who are not familiar with CopyOnWriteArrayList and give the interviewer a good look.

Note: I’m using OpenJDK 14.

01, the Vector

The source documentation for Vector states bluntly, “If thread safety is not required, ArrayList is recommended instead of Vector.” To be honest, I rarely used Vector in my decade-plus programming career, because its thread-safety was based on adding the synchronized keyword to each method, and its high granularity meant poor performance.

public synchronized boolean add(E e) {
    modCount++;
    add(e, elementData, elementCount);
    return true;
}

public synchronized E remove(int index) {
    modCount++;
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
    E oldValue = elementData(index);

    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}
Copy the code

Even the method such as size() is synchronized, which can be imagined how extravagant and wasteful Vector is and how luxurious and luxurious it is.

If you’re not familiar with the synchronized keyword, click on the link below to check out an article I wrote earlier.

Oh, my god, you can’t use synchronized

In high-concurrency situations, performance is often required, and Vector is clearly not up to the task, so it deserves to be forgotten.

02, SynchronizedList

That some students may say, you can use the Collections. SynchronizedList ArrayList () be thread-safe.

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
            new Collections.SynchronizedRandomAccessList<>(list) :
            new Collections.SynchronizedList<>(list));
}
Copy the code

SynchronizedRandomAccessList and SynchronizedList, they are not to use the synchronized keyword at the method level, but inside the method using the synchronized block (this).

public void add(int index, E element) {
    synchronized (mutex) {list.add(index, element);}
}
public E remove(int index) {
    synchronized (mutex) {return list.remove(index);}
}
Copy the code

Where mutex is the this keyword, which is the current object.

final Object mutex;     // Object on which to synchronize

SynchronizedCollection(Collection<E> c) {
    this.c = Objects.requireNonNull(c);
    mutex = this;
}
Copy the code

03, ConcurrentModificationException

ConcurrentModificationException this exception don’t know if the students have encountered? So LET me just type in a little code and make it happen once, so you can see it.

List<String> list = new ArrayList<>();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("A programmer with a really fucking interesting article.");

for (String str : list) {
    if ("Silent King II.".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);
Copy the code

Run this code would throw ConcurrentModificationException:

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1012)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:966)
Copy the code

You can look up the stack information for the exception, which occurred in the checkForComodification() method of the ArrayList’s internal Itr class.

final void checkForComodification(a) {
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the code

That is to say, in the execution checkForComodification () method, found modCount and expectedModCount, will throw ConcurrentModificationException anomalies.

Why is that? The previous code did not call the checkForComodification() method.

That leaves us with the decomcompiled bytecode, which turns out that for-each is implemented through Iterator.

List<String> list = new ArrayList();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("A programmer with a really fucking interesting article.");
Iterator var3 = list.iterator();

while (var3.hasNext()) {
	String str = (String) var3.next();
	if ("Silent King II.".equals(str)) {
		list.remove(str);
	}
}

System.out.println(list);
Copy the code

When you execute list.iterator(), you return the inner Itr class of ArrayList.

public Iterator<E> iterator(a) {
    return new ArrayList.Itr();
}
Copy the code

The Iterator Iterator is fail – fast, if in any way (including the remove and add) to modify the Iterator, will throw ConcurrentModificationException.

The iterator increments modCount by one when it executes the remove() method. The fastRemove() method is called inside the remove() method.

private void fastRemove(Object[] es, int i) {
    modCount++;
    final int newSize;
    if ((newSize = size - 1) > i)
        System.arraycopy(es, i + 1, es, i, newSize - i);
    es[size = newSize] = null;
}
Copy the code

When the checkForComodification() method is executed next(), the modCount is 4 and the expectedModCount is 3, so an exception is thrown.

The reason in the case of a single thread throw ConcurrentModificationException, is in order to in the case of multi-threaded concurrent, don’t take any risk, avoid off the possibility of another thread to modify a List in advance.

The iterators returned by ArrayList are fail-fast, as are those returned by Vector, and SynchronizedList. This means that they have problems adding and deleting things through for-each traversal in a multi-threaded environment.

04, CopyOnWriteArrayList

See how much work I did to get CopyOnWriteArrayList out.

List<String> list = new CopyOnWriteArrayList();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("A programmer with a really fucking interesting article.");

for (String str : list) {
    if ("Silent King II.".equals(str)) {
        list.remove(str);
    }
}

System.out.println(list);
Copy the code

Replace the ArrayList with CopyOnWriteArrayList, and the program executes, as shown below.

[Silent King iii, a programmer with really funny articles]Copy the code

Don’t throw ConcurrentModificationException, because CopyOnWriteArrayList is fail – safe, iterators iterate through the array of original Remove is a copy of the new array, and then assign the new array to the original array.

However, any changes made to CopyOnWriteArrayList after the iterator is retrieved will not be reflected in the iterator in time.

CopyOnWriteArrayList<String> list1 =
        new CopyOnWriteArrayList<>(new String[] {"Silent King II."."Silent King three."});
Iterator itr = list1.iterator();
list1.add("The Silent King iv.");
while(itr.hasNext()) {
    System.out.print(itr.next() + "");
}
Copy the code

Silent King iv does not appear in the output.

Two Kings of Silence three Kings of SilenceCopy the code

The iterator Itr of ArrayList supports remove.

List<String> list = new ArrayList();
list.add("Silent King II.");
list.add("Silent King three.");
list.add("A programmer with a really fucking interesting article.");
Iterator var3 = list.iterator();

while (var3.hasNext()) {
    String str = (String) var3.next();
    if ("Silent King II.".equals(str)) {
        var3.remove();
    }
}

System.out.println(list);
Copy the code

The output of the program is as follows:

[Silent King iii, a programmer with really funny articles]Copy the code

The iterator COWIterator of CopyOnWriteArrayList does not support remove.

public void remove(a) {
            throw new UnsupportedOperationException();
        }
Copy the code

CopyOnWriteArrayList implements the List interface, however, not in the java.util package, but in the java.util. Concurrent package, which counts as an enhanced, thread-safe version of ArrayList.

As the name suggests, CopyOnWriteArrayList is copied first when writing operations (add, set, remove), and the underlying implementation is array copy.

In Java 8, CopyOnWriteArrayList’s add, delete, and modify operations used a ReentrantLock (ReentrantLock).

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 code

By Java 14, it had been changed to synchronized blocks.

public boolean add(E e) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        es = Arrays.copyOf(es, len + 1);
        es[len] = e;
        setArray(es);
        return true; }}Copy the code

Where lock is an Object Object.

/** * The lock protecting all mutators. (We have a mild preference * for builtin monitors over ReentrantLock when either  will do.) */
final transient Object lock = new Object();
Copy the code

Use ReentrantLock for better performance, or use synchronized blocks for better performance. However, Java 14 is written more succinct than Java 8 in other respects, including the absence of the creation of a newElements variable.

Now look at the set() method:

public E set(int index, E element) {
    synchronized (lock) {
        Object[] es = getArray();
        E oldValue = elementAt(es, index);

        if(oldValue ! = element) { es = es.clone(); es[index] = element; }// Ensure volatile write semantics even when oldvalue == element
        setArray(es);
        returnoldValue; }}Copy the code

The synchronized block is also used, and a copy is made by calling the wrapped clone() method.

Then look at the remove() method:

public E remove(int index) {
    synchronized (lock) {
        Object[] es = getArray();
        int len = es.length;
        E oldValue = elementAt(es, index);
        int numMoved = len - index - 1;
        Object[] newElements;
        if (numMoved == 0)
            newElements = Arrays.copyOf(es, len - 1);
        else {
            newElements = new Object[len - 1];
            System.arraycopy(es, 0, newElements, 0, index);
            System.arraycopy(es, index + 1, newElements, index,
                    numMoved);
        }
        setArray(newElements);
        returnoldValue; }}Copy the code

Synchronized blocks are required, as is system.arrayCopy ().

Unlike Vector, CopyOnWriteArrayList’s get() and size() methods are not locked.

public int size(a) {
    return getArray().length;
}

public E get(int index) {
    return elementAt(getArray(), index);
}
Copy the code

First, when CopyOnWriteArrayList is modified, it copies a new array, the modification is done in the new array, and the new array is assigned to the original array reference. Second, the write of CopyOnWriteArrayList is locked, but the read is not.

CopyOnWriteArrayList has a lot of advantages, but array copying is heavy, and if you have a lot of writes and a lot of reads, you’re going to use up a lot of memory; In addition, CopyOnWriteArrayList does not guarantee that data is synchronized in real time, because the read and write operations are separated, with the write operations being based on the new array being copied and the original array being read.

05, finally

If I had read an article like this nine years ago, I would not have been picked on by Ma. I am sure I could have put off another half hour for twenty more questions. But I think the students must be luckier than me, at least now see, not too late, right?

I am the Silent King 2, a programmer with good looks but mediocre talent. Attention can improve learning efficiency, don’t forget three even ah, like, favorites, leave a message, I don’t pick, Ollie.

Note: If there are any problems with the article, please kindly correct them.

If you feel the article to you some help welcome wechat search “silent king ii” first time to read, reply to “small white” more have my liver 40,000 + words Java small white manual 2.0 version, this article GitHub github.com/itwanger has included, welcome star.