Java / Concurrent collections

The java.util.concurrent package includes a number of additions to the Java Collections Framework.

These collections helps preventing 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.

The API is initially introduced in JDK 1.5.

BlockingQueue defines a FIFO (first-in-first-out) data structure that blocks or times out when you attempt to add to a full queue, or retrieve from an empty queue.

ConcurrentMap is a subinterface of java.util.Map that defines useful atomic operations. These operations remove or replace a key-value pair only if the key is present, or add a key-value pair only if the key is absent. Making these operations atomic helps avoid synchronization. The general purpose implementation of ConcurrentMap is ConcurrentHashMap, which is a concurrent analog of HashMap.

ConcurrentNavigableMap is a subinterface of ConcurrentMap that supports approximate matches. The general-purpose implementation of ConcurrentNavigableMap is ConcurrentSkipListMap, which is a concurrent analog of TreeMap.

BlockingDeque interface extends BlockingQueue and adds the operations of Deque.

TransferQueue interface extends BlockingQueue and adds method where the producer will wait for the consumer to receive elements.

BlockingQueue extends Queue interface, is a queue that additionally supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the fixed length queue when storing an element while it is full.

A BlockingQueue does not allow null elements and throws NullPointerException.

BlockingQueue methods are categorized into 4 forms due to its way of handling operations that cannot be satisfied immediately, but may be satisfied at some point in the future.

• Methods that throws an exception, for example, add(element) throws exception while trying to add the element failed when queue is full.
• Methods that return a special value (either null or false, depending on the operation).
• one that blocks the current thread indefinitely until the operation can succeed.
• the fourth blocks for only a given maximum time limit before giving up.

Yes. BlockingQueue supports Collection interface, it is possible to remove an arbitrary element from a queue using remove(x) method. However, such operations are not performed very efficiently, and are intended for only occasional use, such as when a queued message is cancelled.

It is also possible to access all the elements inside a BlockingQueue.

Yes, BlockingQueue implementations are thread-safe. Even all the queue method action and its effects are atomic.

However, the bulk Collection operations addAll, containsAll, retainAll and removeAll are not necessarily performed atomically unless specified otherwise in an implementation.

Poison Pill or poison object is a data item placed on the queue and when the consumer reads this item it closes down. Obviously, the poison pill will be last item placed on the queue otherwise the consumer will shut down prematurely.

drainTo method removes all available elements from this queue and adds them to the given collection.

int drainTo(Collection<? super E> c)

• ArrayBlockingQueue,
• DelayQueue,
• LinkedBlockingQueue,
• PriorityBlockingQueue,
• and SynchronousQueue.

No. It doesn't allow and it throws NullPointerException.

The ArrayBlockingQueue class implements the BlockingQueue interface. It is introduced in Java 1.5.

ArrayBlockingQueue is a bounded blocking queue backed by an array.

This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.

BlockingQueue<String> queue = new ArrayBlockingQueue<String>(100);

queue.put("Element");

String string = queue.take();

This class supports an optional fairness policy for ordering waiting producer and consumer threads. By default, this ordering is not guaranteed. However, a queue constructed with fairness set to true grants threads access in FIFO order. Fairness generally decreases throughput but reduces variability and avoids starvation.

Bounded buffer or datastructure means that it cannot store unlimited amounts of elements and there is an upper bound on the number of elements it can store at the same time. You set the upper bound at instantiation time, and after that it cannot be changed.

DelayQueue class implements the BlockingQueue interface. It is introduced in Java 1.5.

DelayQueue is an unbounded blocking queue of Delayed elements, in which an element can only be taken when its delay has expired. The head of the queue is that Delayed element whose delay expired furthest in the past. If no delay has expired there is no head and poll will return null. Expiration occurs when an element's getDelay(TimeUnit.NANOSECONDS) method returns a value less than or equal to zero.

Even though unexpired elements cannot be removed using take or poll, they are otherwise treated as normal elements. For example, the size method returns the count of both expired and unexpired elements.

The elements of DelayQueue must implement the interface java.util.concurrent.Delayed.

This queue does not permit null elements.

The LinkedBlockingQueue class implements the BlockingQueue interface. It is introduced in Java 1.5.

The LinkedBlockingQueue keeps the elements internally in a linked structure (linked nodes). This linked structure can optionally have an upper bound if desired. If no upper bound is specified, Integer.MAX_VALUE is used as the upper bound.

This queue orders elements FIFO (first-in-first-out). The head of the queue is that element that has been on the queue the longest time. The tail of the queue is that element that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements at the head of the queue.

Linked queues typically have higher throughput than array-based queues but less predictable performance in most concurrent applications.

The PriorityBlockingQueue class implements the BlockingQueue interface. It is introduced in Java 1.5.

An unbounded blocking queue that uses the same ordering rules as class PriorityQueue and supplies blocking retrieval operations. While this queue is logically unbounded, attempted additions may fail due to resource exhaustion (causing OutOfMemoryError). This class does not permit null elements. A priority queue relying on natural ordering also does not permit insertion of non-comparable objects.

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the PriorityBlockingQueue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()). Also, method drainTo can be used to remove some or all elements in priority order and place them in another collection.

ArrayBlockingQueue and LinkedBlockingQueue are common implementations of the BlockingQueue interface.

ArrayBlockingQueue is a fixed size bounded buffer on the other hand LinkedBlockingQueue is an optionally bounded queue built on top of Linked nodes.

LinkedBlockingQueue provides higher throughput than ArrayBlockingQueue.

The synchronizedMap(HashMap) locks the entire map while ConcurrentHashMap synchronizes or locks on the certain portion of the Map . To optimize the performance of ConcurrentHashMap , Map is divided into different Segments.

ConcurrentHashMap shows good performance than synchronized version of HashMap.

When you read from a ConcurrentHashMap using get(), there are no locks, contrary to the Synchronized HashMap for which all operations are simply synchronized.

ConcurrentHashMap can guarantee that there is no ConcurrentModificationException thrown while one thread is updating the map and another thread is traversing the iterator obtained from the map. However, Collections.synchronizedMap() is not guaranteed on this.

ConcurrentHashMap will not preserve the order of elements in the Map passed in. It is similar to HashMap when storing data. There is no guarantee that the element order is preserved. While Collections.synchronizedMap() will preserve the elements order of the Map passed in.

The main reason that null is not allowed in ConcurrentMaps such as ConcurrentHashMaps, ConcurrentSkipListMaps is to avoid ambiguities. If map.get(key) returns null, you cannot detect whether the key explicitly maps to null or the key itself is not mapped. In a non-concurrent map, you may check this using map.contains(key), but in a concurrent environment, the map might have changed between calls.

Yes. However the ConcurrentHashMap is designed to work in a multi threaded environment and it will exhibit poor performance.

ConcurrentHashMap uses multiple buckets to store data. This avoids read locks and greatly improves performance over a HashTable.

Hashtable uses single lock for whole data. ConcurrentHashMap uses multiple locks on Segment level (16 by default) instead of whole Map.

ConcurrentHashMap Locking is applied only for updates. In case of of retrievals, it allows full concurrency, Retrievals reflect the results of the most recently completed update operations. So Reads can happen very fast while write is done with a lock.

High-throughput computing (HTC) describes the use of many computing resources over long periods of time to accomplish a computational task.

ConcurrentHashMap is thread safe while HashMap is not.

ConcurrentHashMap does not allow NULL key or value while HashMap allows one null key.

The SynchronousQueue class implements the BlockingQueue interface introduced in Java 1.5.

SynchronousQueue is a blocking queue in which each insert operation must wait for a corresponding remove operation by another thread, and vice versa. A synchronous queue does not have any internal capacity.

The peek operation cannot be performed at a synchronous queue because an element is only present when you try to remove it; you cannot insert an element (using any method) unless another thread is trying to remove it; you cannot iterate as there is nothing to iterate. The head of the queue is the element that the first queued inserting thread is trying to add to the queue; if there is no such queued thread then no element is available for removal and poll() will return null. This queue does not permit null elements.

This class supports an optional fairness policy for ordering waiting producer and consumer threads. A queue constructed with fairness set to true grants threads access in FIFO order.

They are well suited for handoff designs, in which an object running in one thread must sync up with an object running in another thread in order to hand it some information, event, or task.

A shutdown hook is simply a thread that JVM invokes implicitly before it shuts down.

When the JVM begins its shutdown sequence it starts all registered shutdown hooks in a random order and let runs it concurrently. When all the hooks have completed its execution JVM will then run all uninvoked finalizers if finalization-on-exit has been enabled. Finally, the virtual machine will halt.

The Callable interface is similar to Runnable, both designed for classes whose instances are executed by another thread.

A Callable needs to implement call() method while a Runnable needs to implement run() method.

Callable can return a value however a Runnable cannot.

Callable can throw checked exception but a Runnable cannot.

Callable can be used with ExecutorService invoke... methods but a Runnable cannot be.

To stop threads in Java, we rely on a cooperative mechanism called Interruption. To stop a thread, all we can do is deliver it a interrupt signal, requesting that the thread stops itself at the next available opportunity. This means that threads could only signal other threads to stop, not force them to stop.

It is inherently unsafe. Stopping a thread causes it to unlock all the monitors that it has locked. If any of the objects previously protected by these monitors were in an inconsistent state, other threads may now view these objects in an inconsistent state. Such objects are said to be damaged. When threads operate on damaged objects, arbitrary behavior can result.

Thread.suspend is inherently deadlock-prone. If the target thread holds a lock on the monitor protecting a critical system resource when it is suspended, no thread can access this resource until the target thread is resumed. If the thread that would resume the target thread attempts to lock this monitor prior to calling resume, deadlock results. Such deadlocks typically manifest themselves as "frozen" processes.

findMonitorDeadlockThreads method finds cycles of threads that are in deadlock waiting to acquire object monitors while findDeadlockedThreads finds cycles of threads that are in deadlock waiting to acquire object monitors or ownable synchronizers.

An ownable synchronizer is a synchronizer that may be exclusively owned by a thread and uses AbstractOwnableSynchronizer (or its subclass) to implement its synchronization property.

ReentrantLock and ReentrantReadWriteLock are 2 examples of ownable synchronizers provided by the platform.

To detect deadlock in ownable synchronizers, ReentrankLock or ReentrantReadWriteLock, make sure to use findMonitorThreads method.

ThreadMXBean gives the information about threads in JVM. ThreadMXBean gives the complete information of threads running, daemon thread, peak thread count, current thread user time.

• Immutable Object pattern,
• Observer Pattern.

Yes. Presence of final guarantees that other threads would see values in the map after constructor finished without any external synchronization. Without final it cannot be guaranteed in all the case.

final and volatile fields will be guaranteed to be fully initialized by the time the constructor finishes but not other "normal" fields.

The difference is that execute does not return a Future.

A task queued with execute() that generates a Throwable will cause the UncaughtExceptionHandler for the Thread running the task to be invoked. The default UncaughtExceptionHandler, which typically prints the Throwable stack trace to System.err, will be invoked if no custom handler has been installed.

On the other hand, a Throwable generated by a task queued with submit method will bind the Throwable to the Future that was produced from the call to submit(). Calling get() on that Future will throw an ExecutionException with the original Throwable as its cause (accessible by calling getCause() on the ExecutionException).

If you are in a synchronized method, then calls to other methods that are also synchronized by other threads are locked. However calls to non-synchronized methods by other threads are not locked.

Defensive copying is a technique where an identical, but the copy of an object is returned instead of the original object by performing deep copy. Thus any modification to the returned object will not affect the original object.

Program counter (PC) register keeps track of the current instruction executing at any moment.

A program counter (PC) Register is created every time a new thread is created. PC keeps a pointer to the current statement that is being executed in its thread.

The shutdown hook can be used to perform cleanup resource or save the state when JVM shuts down normally or abruptly. So if you want to execute some code before JVM shuts down, use shutdown hook.

public class MyShutdownHook {
	public static void main(String[] args) {
		System.out.println("Executing main Thread.");

		Runtime.getRuntime().addShutdownHook(new Thread(new Runnable() {
			public void run() {
				System.out.println("Executing Shutdown hook Thread.");
			}
		}));

		System.out.println("Exiting main thread.");
	}
}

JVM shutdown sequence has 2 phases.

• All registered shutdown hooks are started in some unspecified order and allowed to run concurrently until they finish.
• All un-invoked finalizers are run if finalization-on-exit has been enabled.

N threads will be processing tasks and when all the threads are busy, tasks are added to the queue with no limit. Fixed Thread pool are ideal for CPU intensive tasks.

Immutable objects facilitate safe publication and prevent publishing partially constructed objects.

ConcurrentLinkedQueue is not a blocking queue while LinkedBlockingQueue implements BlockingQueue interface.

LinkedBlockingQueue provides blocking methods such as put and take while ConcurrentLinkedQueue does not provide those methods.

It cannot be guaranteed. However an workaround would be to create a synchronized method and invoke an abstract method from it. We also need to ensure the abstract method is directly invoked.

public synchronized final void method() {
    absMethod();
}
protected abstract void absMethod();

Java.util.concurrent.ConcurrentHashMap is a concurrent collection class added in JDK 1.5 as a replacement of synchronized hash-based map implementations such as Hashtable and synchronized HashMap. They offer better performance and scalability over their synchronized counterpart.

Yes, ConcurrentHashMap is thread-safe in Java, two thread can modify the map without damaging its internal data structures: array and linked list. HashMap is not thread-safe and in multi threaded environment, multiple threads may damage internal data structure and may render the map completely unusable, where some links may go missing or referring to incorrect elements.

Yes, ConcurrentHashMap allows concurrent read without locking as reading operation doesn't require locking or thread-safety.

ConcurrentHashMap works similar to HashMap by storing key/value pairs and retrieving values. The difference in its implementation in terms of concurrency and how it achieves thread-safety. ConcurrentHashMap divides the map into several segments, by default 16, also known as synchronization level.

Due to the segment level synchronization, get(), put(), contains() operation can be performed concurrently as it never locks the whole map but only the relevant segment gets locked. Multiple readers can access the map concurrency with writers and a limited number of writers can modify the map concurrently. The result is better throughput and Scalability.

ConcurrentHashMap is a mini hash table with a bucket and linked list of hash entries in case of collision.

ConcurrentHashMap achieves thread-safety by dividing the map into segments and locking only the segment which requires instead of locking the whole map. It achieves thread-safety using locking but it performs better because it never locks the whole map.

This technique is also known as lock stripping.

Use replace() method to update the existing value at ConcurrentHashMap. It takes both old value and new value and only updates the map if the existing value in the map matches with the old value provided otherwise replace method fails by retaining false.

Iterator of ConcurrentHashMap is a fail-safe iterator so it will not throw a ConcurrentModificationException, eliminating the need to lock the map during iteration. The iterator returned by ConcurrentHashMap are also weakly consistent so if the Map is modified during iteration, it may or may not reflect the recent modification. Usually, it creates a copy of collection before iterating.

Spliterator stands for Splitable Iterator. Similar to Iterator and ListIterator, It is also an Iterator interface.

Spliterator is used to split given element set into multiple sets so that we can perform operations/calculations on each set in different threads independently, possibly taking advantage of parallelism. It is designed as parallel analogue of Iterator.

Java9 has introduced reactive streams that is used for Asynchronous communication. This is based on Publish/Subscribe framework. The class java.util.concurrent.Flow provides interfaces that support the Reactive Streams.

Simpler code, thus improved readablity.

Abstracts away from boiler plate code to focus on business logic.

Abstracts away from low-level threading, synchronization, and concurrency issues.

Stream processing implies memory efficient.

The model can be applied almost everywhere to solve almost any kind of problem.

Stream pipelining is the concept of chaining operations together. This is done by splitting the operations that can happen on a stream into two categories, intermediate operations and terminal operations. Each intermediate operation returns an instance of Stream itself when it runs, an arbitrary number of intermediate operations can, therefore, be set up to process data forming a processing pipeline. Then there is a terminal operation which returns a final value and terminates the pipeline.

CopyOnWriteArrayList is a thread safe variant of ArrayList introduced in Java 5. As the name indicates, whenever there is a write, it creates a fresh copy of list and perform modifications.

ConcurrentSkipListMap has sorted keys while ConcurrentHashMap does not sort.

ConcurrentSkipListMap is not fast as compared to ConcurrentHashMap.