This article focuses on the potential problems and solutions of synchronous container classes. We can't help but wonder if synchronization containers must be truly thread-safe. Not always. Because it may throw the following two exceptions.

1. ArrayIndexOutBoundsException exception
2. Concurrent ModificationException exception

Well, in this article we will discuss the causes of these two anomalies and the solutions.

Synchronization strategy

Okay, now let's look at the synchronization container classes mentioned in the last article, so let's first understand their synchronization strategies. They are mainly:

• HashTable
• Vector
• Stack
• Synchronized wrapper: [Collections. synchronized Map (), Collections. synchronized List ()]

Part of the source code for Vector is as follows:

  //...
  public synchronized E get(int index) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);
    }

    public synchronized E set(int index, E element) {
        if (index >= elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }
    //...

From the source code of the synchronization container, we can see that they encapsulate the state, synchronize each method, and only one thread can access the container at a time.

ArrayIndexOutBoundsException exception

Synchronized container classes are theoretically thread-safe, but in some cases, they still make mistakes. Let's use Vector as an example, for example, to delete the last element in Vector now. If there are multiple threads concurrently performing this deletion operation at this time, can it be executed properly?

import java.util.Vector;

public class VectorTest {

    //Define a way to delete the last element
    public static void deleteLast(Vector list) {
        int lastindex = list.size() - 1;
        list.remove(lastindex);
    }

    public static void main(String[] args) {

        Vector v = new Vector(); //Create a Vector

        //Add 10,000 elements to the container
        for(int i = 0; i < 10000; i++) {
            v.add(i);
        }

        //Start N threads to perform deletion
        for(int i = 0; i < 900; i++) {
            new Thread(new Runnable() {
                @Override
                public void run() {
                    deleteLast(v);//Delete the last element
                }
            }).start();
        }
        System.out.println("end");
    }
}

Implementation results:

The execution result is an exception thrown [Array Index Outbounds Exception], and the array subscript crosses the bounds. Because in this program, the size of Vector is decreasing. Maybe one element has been deleted and another element has been deleted again, but the element no longer exists, so an exception is thrown.

Of course, this situation can only be solved by locking the client. Fortunately, Vector's synchronization strategy is to use its own built-in lock. So our code can run by modifying it as follows:

synchronized (v) {
    deleteLast(v);//Delete the last element
}

//Pay attention to locking when iterating
synchronized (v) {
    for(int i = 0; i < v.size(); i++) {
        doSomeThing(v.get(i));
    }
}

Concurrent ModificationException exception

Let's look at the following code:

import java.util.Iterator;
import java.util.Vector;

public class VectorTest {

    public static void main(String[] args) {

        Vector v = new Vector(); //Create a Vector

        //Add 100 elements to the container
        for(int i = 0; i < 100; i++) {
            v.add(i);
        }

        //Using iterator traversal, delete an element while traversal
        Iterator it = v.iterator();
        while(it.hasNext()) {
            Integer integer = (Integer) it.next();
            if(integer == 5) {
                v.remove(integer); //Delete an element
            }
        }

        System.out.println(v.toString());
    }
}

The results of implementation are as follows:

In checkForComodification, it.next() checks whether the two variables (modCount, expectedModCount) are equal, and throws the exception if they are unequal. Calling v.remove() directly updates the value of modCount, but does not update the value of expectedModCount, so an exception is thrown. These two variables are located in the container class as follows:

To solve this problem, change v.remove(integer) to delete it.remove() using an iterator. The method in the iterator can update the two values at the same time to ensure equality. Interested friends can check the source code of Itr to see exactly.

if(integer == 5) {
    it.remove(); //If traversed by iterator, deleted by iterator
}

Above all, exceptions occur in the case of a single thread. So the question arises. Is everything going well with multi-threading after correcting the above?

The answer is No. Because the operation of different threads may lead to different values read by the two variables in different threads, because these two variables are not volatile variables, there may be invisibility between threads.

In the case of multithreading, let's look at the following example:

import java.util.Iterator;
import java.util.Vector;

public class VectorTest {

    public static void main(String[] args) {

        Vector v = new Vector(); //Create a Vector

        //Add 100 elements to the container
        for(int i = 0; i < 100; i++) {
            v.add(i);
        }
        //Create a thread to traverse Vector
        new Thread(new Runnable() {
            @Override
            public void run() {
                Iterator it = v.iterator();
                while(it.hasNext()) {
                    Integer integer = (Integer) it.next(); //Call next
                    try {
                        Thread.sleep(100);    //sleep
                    } catch (InterruptedException e) {
                        // TODO Auto-generated catch block
                        e.printStackTrace();
                    }
                }
            }
        }).start();
        //Create a thread to traverse Vector
        new Thread(new Runnable() {
            @Override
            public void run() {
                //Using iterator traversal, delete an element while traversal
                Iterator it = v.iterator();
                while(it.hasNext()) {
                    Integer integer = (Integer) it.next();
                    if(integer == 5) {
                        it.remove(); //Delete an element and update the value of the variable modCount, expectedModCount.
                    }
                }
            }
        }).start();
    }
}

The results are as follows:

When concurrent iteration modifications are made to synchronous containers such as Vector, the iterator may report a Concurrent ModificationException exception.

For multi-threaded situations, there are generally two solutions to avoid exceptions:

1) Use synchronized or Lock to synchronize when iterator iteration is used;
2) Use the concurrent container CopyOnWriteArrayList instead of ArrayList and Vector.
　　
Now let's use client locking as an example, where each thread holds a container lock during an iteration.

//Using iterator traversal, delete an element while traversal
synchronized(v) {
Iterator it = v.iterator();
while(it.hasNext()) {
    Integer integer = (Integer) it.next();
    if(integer == 5) {
        it.remove(); //Delete an element and update the value of the variable modCount, expectedModCount.
    }
}

Hidden Iterator

Although locking can avoid modCount exceptions in iterators, it is important to remember that locks are used everywhere in a shared container where iterations may occur. Because sometimes iterators are hidden.

For example, the toString() implementation in a standard container iterates over each element in the container. Similarly, container hashCode, equal, containsAll, removeAll and retainAIl all iterate over the container and throw Concurrent ModificationException.

This is what we should pay attention to.

Well, that's all for today, and the concurrent container will be covered in the next article.