JavaBrushUp4U: Concurrent Collection

Concurrent collection classes are very useful and efficient when you are writing code for multi-threading environment.

1. What is CopyOnWriteArrayList?

Answer: CopyOnWriteArrayList is concurrent(thread-safe) version of ArrayList. It allows modification by multiple thread at same time unlike ArrayList. Write Operation like add(), set() first take lock of ReentrantLock at start and release the same at end of method in order to ensure write operation is being perform by one thread at once. Also before adding value to underlying array it copies entire array instead of updating existing array directly.
Note : Only one thread at a time can execute write(add(), set() etc) operations on the list but read operations(get()) can be performed by multiple threads simultaneously.
Write operations lock entire list hence only one thread can write at once all the other thread need to wait till that time but multiple thread can read simultaneously. Simultaneously one write and multiple read operations is also possible, in this case threads that are reading values will see the latest data as it was before the current write operation.

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CopyOnWriteArrayListExample {
 public static void main(String[] args) throws InterruptedException {
  List<Integer> list = new ArrayList<>();
  list.add(0);
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  Thread th1 = new Thread(new Runnable() {
   @Override
   public void run() {
    for(int i = 5 ; i < 10; i++)
     list.add(i);
   }
  });
  Thread th2 = new Thread(new Runnable() {
   @Override
   public void run() {
    for(int i = 10 ; i < 15; i++)
     list.add(i);
   }
  });
  Thread th3 = new Thread(new Runnable() {
   @Override
   public void run() {
    for(int i = 15 ; i < 20; i++)
     list.add(i);
   }
  });
  th1.start();
  th2.start();
  th3.start();
  th1.join();
  th2.join();
  th3.join();
  Collections.sort(list);
  System.out.println("Items: "+list + "\nSize : "+list.size());
 }
}

If you run above code multiple times you will get different outputs. Since we are using ArrayList which is getting modified by three threads simultaneously. Desired output is at the end list should contain all values from 0 to 20 and size should be 20, but if we run above code multiple times then in some cases you may get size less than 20 and some missing values.
But if you use CopyOnWriteArrayList instead you will get same consistent output(size 20) every time. Since write operation is thread safe in CopyOnWriteArrayList unlike ArrayList.

2. What is ConcurrentHashMap and how it works?

Answer: ConcurrentHashMap is a thread safe version of HashMap. Multiple thread can work with ConcurrentHashMap with consistent result. If you use HashMap in a multi-threading environment then you can not predict write(desired) outcome since it is not thread safe. But if you use ConcurrentHashMap instead then you will get consistent result every time.
ConcurrentHashMap takes locks of one bucket location object. For write operation a thread doesn't take lock of entire map instead it locks only one desired bucket location object. If a thread has to perform put operation It will first find desired bucket location same as HashMap, then thread will take lock of that bucket location object only. So no other thread can access that specific bucket location till first thread completes it's operation. But mean while some different thread can perform put operation on a different bucket location.
Default(Initial) size of ConcurrentHashMap is 16, It means 16 thread can perform put(write) operation simultaneously on map provided each of them working on different bucket location. But for read (get) operation thread doesn't require to take lock, So multiple thread can read from same bucket location simultaneously as they are not modifying map. Multiple threads can perform read operation on one single bucket location while one thread is performing write operation.

3. What is different between HashTable and ConcurrentHashMap?

Answer: The very important difference between them is "In order to perform operations in HashTable thread locks entire HashTable object but in ConcurrentHashMap thread locks only one bucket location object". Hence HashTable offers very low level of concurrency in compare of ConcurrentHashMap. Only one thread can perform operation on HashTable at a time but by default 16 threads can perform operation on ConcurrentHashMap at a time.
ConcurrentHashMap offers much better level of performance in compare of HashTable.

4. Why ConcurrentHashMap doesn't allow null keys or values?

Answer: It is not allowed because if you call map.get(key) and it will return null then you can't say that key is mapped to null value or key is not present in map. In case of HashMap(non concurrent map) you can solve this problem by calling map.contains(key) but in ConcurrentHashMap if you call map.contains(key) then it might possible that map has changed between map.get(key) and map.contains(key) calls.

5. What is ConcurrentModificationException?

Answer: We get the ConcurrentModificationException If one thread is trying to modify the structure of a non-concurrent collection when other thread is iterating over it. Concurrent collections never throw this exceptions as they work on copy of underlying structure for write operations.

For example:

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class ConcureentExceptionTest {

 public static void main(String[] args) {
  List<Integer> list = new ArrayList<>();
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  
  Iterator<Integer> itr = list.iterator();
  while(itr.hasNext()){
   System.out.println(itr.next());
   list.remove(3);
  }
 }
}

above code will throw the ConcurrentModificationException at line number 17 as we are trying modify list while iterating over it.

You can use iterator's remove() method instead of list's to handle exception in single threaded environment. In below code we have used Iterator's remove() method and if you run below code you won't get exception.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

public class ConcureentExceptionTest {

 public static void main(String[] args) {
  List<Integer> list = new ArrayList<>();
  list.add(1);
  list.add(2);
  list.add(3);
  list.add(4);
  
  Iterator<Integer> itr = list.iterator();
  while(itr.hasNext()){
   System.out.println(itr.next());
   itr.remove();
  }
 }
}

6. How ArrayList's(or any concurrent collection) iterator detect Concurrent Modification or change in the structure of list in order to throw exception?

Answer: ArrayList maintains a variable named modCount. Whenever we made modifications(add or remove) in list modCount get updated by one.
So in above code we have added 4 elements to list it means value of modCount Will be 4.
When we initialize iterator for the list, Iterator stores the value of modCount in a temporary variable named expectedModCount. On every iteration(on invocation of next() method) it first compare expectedModCount variable with modCount. If they are not equal then next() method throws ConcurrentModificationException immediately else it simple return the current value.
So in above code we have initialized iterator at line number 14. At this point we have value of modCount as 4 hence Iterator will initialize value of expectedModCount as 4. Now at line 17 we have called remove() method of list which will increment the value of modCount from 4 to 5. Hence on next invocation of next() method modCount won't be equal to expectedModCount which will result in ConcurrentModificationException.

Note: Iterator's remove() method doesn't throw exception because It first removes the element form list and then updates the expectedModCount with latest modCount value. So on next invocation of next() method both the variables will be equal.

7. Why CopyOnWriteArrayList's iterator or any concurrent collections' iterator doesn't throw ConcurrentModificationException?

Answer: ArrayList's Iterator works on the same original list hence any modification on list directly affect the iterator while CopyOnWriteArrayList's Iterator works on the copy of original list hence any modification on underlying original list doesn't affect the Iterator as It is working on copy.
So we should use concurrent collection's iterator like CopyOnWriteArrayList, ConcurrentHashMap etc in multi-threaded environment.

8. What are fail-fast and fail-safe iterators?

Answer: Fail-fast iterators throw exception as soon as we made any structural modification in underlying collection. All non con-concurrent collections's Iterators are fail-fast.
Fail-safe iterators don't throw exception when we made any structural modification in underlying collection. All con-concurrent collections's Iterators are fail-safe.

JavaBrushUp4U

Pages

Saturday 6 May 2017

Concurrent Collection