Concurrent Collections

• package: java.util.concurrent
• All of these collections help avoid Memory Consistency Errors by defining a happens-before relationship between an operation that adds an object to the collection with subsequent operations that access or remove that object

Synchronized Collections

• These classes synchronize every public method, and hence slow
  • getter + setter
• Vector
• HashTable
• Collections.synchronizedXXX()
  • Performs locking for all operations including both reads and writes
  • Still you must iterate in synchronized block to avoid unexpected results??
• Make ArrayList thread-safe
  • https://stackoverflow.com/questions/2444005/how-do-i-make-my-arraylist-thread-safe-another-approach-to-problem-in-java
  • Collections.synchronizedList(new ArrayList<YourClassNameHere>())

BlockingQueue

• Extension of Queue
• Defines a FIFO data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue
• Useful for implement_producer_consumer_pattern, better than wait() and notify()
• BlockingQueue
• Existing Operations:
  • add(), remove() — throws exception (immediate)
  • bool offer(), poll() — return boolean (immediate)
• New Operations:
  • put(), take() — blocks
  • bool offer(value, timeout, unit) — return boolean (timeout)
  • bool poll(timeout, unit) — return boolean (timeout)
• Implementations:
  • ArrayBlockingQueue
  • LinkedBlockingQueue

ConcurrentMap

• Extension of Map
• Existing compound operations are made atomic like:
  • remove or replace a key-value pair only if the key is present
  • add a key-value pair only if the key is absent
• Implementation:
  • ConcurrentHashMap — analog of HashMap
  • ConcurrentSkipListMap — analog of TreeMap

ConcurrentHashMap

• Reads do not entail locking, multiple threads can read without any issue
• Writes perform locking at segment/bucket level (Java 8 might have bucket level, not confirmed)
• Neither null key nor null value allowed
• Iterator never throws ConcurrentModificationException
• Compared to Collections.synchronizedMap(), ConcurrentHashMap has:
  • better concurrency
  • fine grained locking
  • Never throw ConcurrentModificationException, while synchronizedMap may throw

// Throws exception:
//        - new HashMap<>()
//        - Collections.synchronizedMap(new HashMap<>())
// Do not throw exception:
//        - new ConcurrentHashMap()
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("a", 1);
hashMap.put("b", 2);
 
for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
    hashMap.put("c", 3); // throws ConcurrentModificationException
}

Copy On Write Collections

• Read:
  • No locks involved while reading
  • Iterator is Fail-safe
  • When read is invoked the iterator returned is an immutable snapshot of the original array
  • The iterator cannot do write operations like: add(), set(), remove()
• Write:
  • Uses ReentrantLock internally and allows only one thread to write
  • Create a new array and modifies it by performing write operation
  • Update the reference to the new array and release the lock
• Use case:
  • It solves the issue when traversal and modification is happening concurrently which can throw ConcurrentModificationException
    • In general single Random read and modification concurrently is not that problematic but traversal is problematic
  • Traversal does not involve locks and hence faster
  • Good for systems with heavy traversal operations without worrying about concurrent modifications and writes are infrequent
  • Example includes many Event-Notification systems
    • Delivering a notification requires iterating the list of registered listeners and calling each one of them
    • In most cases registering/unregistering is far less common than receiving event notification
• Compared to ArrayList
  • More memory needed
  • Slow on writes
  • Follows eventual consistency and delay between writes and visibility
• Implementation:
  • CopyOnWriteArrayList
  • CopyOnWriteArraySet

Iterator

• Fail-fast
  • Collections maintain an internal counter called modCount
  • Each time an item is added or removed from the Collection, counter gets incremented.
  • On each next() call, the current value of modCount gets compared with the initial value. If there’s a mismatch, it throws ConcurrentModificationException which aborts the entire operation
  • Remark: In Single Thread ConcurrentModificationException happen if the objects are removed from collection directly rather than through iterator
  • Remark: If during iteration over a Collection, an item is removed using Iterator‘s remove() method, that’s entirely safe and doesn’t throw an exception
  • Example: ArrayList, HashMap
• Fail-safe
  • create clone of actual collection and iterate
  • slow because of copying operation
  • Don’t throw ConcurrentModificationException
  • Example: CopyOnWriteArrayList, CopyOnWriteArraySet
• Weakly Consistent Iterators
  • Iterator can tolerate concurrent modification, traverses elements as they existed when Iterator was constructed
  • May (but isn’t guaranteed to) reflect modifications to the Collection after the construction of the Iterator
  • Don’t throw ConcurrentModificationException
  • Example: ConcurrentHashMap, ConcurrentSkipListSet
• Beware!! Some methods may iterate collection internally
  • hashCode(), equals(), toString(), containsAll(), removeAll()