CopyOnWriteArrayList and ConcurrentHashMap

CopyOnWriteArrayList ( introduced in Java 1.5 )

  

CopyOnWriteArrayList vs Array List in Java

CopyOnWriteArrayList and ConcurrentHashMap are concurrent Collection classes introduced in Java 5 Concurrency. 

A CopyOnWriteArrayList implement List interface like ArrayList, Vector and LinkedList but it’s a thread-safe collection and it achieves its thread-safety in a slightly different way than Vector or other thread-safe collection class.

ArrayList is not thread safe so any simultaneous thread can access and modify the content of list simultaneously.Here lies the dangerous, ConcurrentModificationException (Runtime exception). When one thread is Iterating over an ArrayList and any other thread(which may be the same thread)  modify the content of list and when we again call next() on the iterator ,we get this exception. Which means that no thread can modify the ArrayList while an Iterator is iterating over this. We can solve this by surrounding the code that try to modify this list in a synchronized block with some lock so that the thread trying to modify the ArrayList wait for the iterator to complete.

This seems simple solution but not an efficient one where there are many threads iteration over an ArrayList because each thread has to wait for a considerable time.

Another possible solution could be to use CopyOnWriteArrayList instead of ArrayList. This is same as ArrayList with one difference. All operations that change the contents of a CopyOnWriteArrayList collection cause the underlying array to be replaced with a copy of itself before the contents of the array are changed. Any active iterators will continue to see the unmodified array, so there is no need for locks. Iterators created by a CopyOnWriteArrayList object cannot change the underlying array. Though these iterators do have methods for changing the underlying collection, their implementations throw an UnsupportedOperationException instead of modifying the underlying collection.

 As name suggests CopyOnWriteArrayList creates copy of underlying ArrayList with every mutation operation e.g. add or set. Normally CopyOnWriteArrayList is very expensive because it involves costly Array copy with every write operation but it’s very efficient if you have a List where Iteration outnumber mutation e.g. you mostly need to iterate the ArrayList and don't modify it too often. Iterator of CopyOnWriteArrayList is fail-safe and doesn't throw ConcurrentModificationException even if underlying CopyOnWriteArrayList is modified once Iteration begins because Iterator is operating on separate copy of ArrayList. Consequently all the updates made on CopyOnWriteArrayList is not available to Iterator. In this Java Collection tutorial we will see What is CopyOnWriteArrayList in Java, Difference between ArrayList and CopyOnWriteArrayList in Java and One simple Java program example on How to use CopyOnWriteArrayList in Java.

Difference between CopyOnWriteArrayList and ArrayList in Java.

1) First and foremost difference between CopyOnWriteArrayList and ArrayList in Java is that CopyOnWriteArrayList is a thread-safe collection.

 while ArrayList is NOT thread-safe and cannot be used in multi-threaded environment.

2) Second difference between ArrayList and CopyOnWriteArrayList is that

 Iterator of ArrayList is fail-fast and throw ConcurrentModificationException once detect any modification in List once iteration begins

 Iterator of CopyOnWriteArrayList is fail-safe and DOESN’T throw ConcurrentModificationException.

3) Third difference between CopyOnWriteArrayList vs ArrayList is that Iterator of former doesn't support remove operation while Iterator of later supports remove() operation.

ConcurrentHashMap ( introduced in Java 1.5 )

1) First significant difference between HashMap and ConcurrentHashMap is that later is thread-safe and can be used in concurrent environment WITHOUT external synchronization. Though it doesn't provide same level of synchronization as achieved by using Hashtable but it’s enough for most practical purpose.

2) You can make HashMap synchronized by wrapping it on Collections.synchornizedMap(HashMap) which will return a collection which is almost equivalent to Hashtable, where every modification operation on Map is locked on Map object while in case of ConcurrentHashMap, thread-safety is achieved by dividing whole Map into different partition based upon Concurrency level and only locking particular portion instead of locking whole Map.

ConcurrentHashMap’s accomplish this by a very simple mechanism. Instead of a map wide lock, the collection maintains a list of 16 locks by default, each of which is used to guard (or lock on) a single bucket of the map. This effectively means that 16 threads can modify the collection at a single time (as long as they’re all working on different buckets). Infact there is no operation performed by this collection that locks the entire map. The concurrency level of the collection, the number of threads that can modify it at the same time without blocking, can be increased. However a higher number means more overhead of maintaining this list of locks.

3) ConcurrentHashMap is more scalable and performs better than Synchronized HashMap in multi-threaded environment while in Single threaded environment both HashMap and ConcurrentHashMap gives comparable performance, where HashMap only slightly better.

In Summary Main difference between ConcurrentHashMap and HashMap in Java Collection turns out to be thread-safety, Scalability and Synchronization.
ConcurrentHashMap is better choice than synchronized HashMap if you are using them as cache, which is most popular use case of a Map in Java application. ConcurrentHashMap is more scalable and outperform when number of reader threads outnumber number of writer threads.

LinkedHashSet ( introduced in Java 1.4 )

A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.