Concurrent HashMap is a Hash based map like HashMap but it uses entirely a different locking strategy that offer better concurrency and scalability.

What does this Do Differentely?

Instead of synchronizing every method on a common lock ,restricting access to a single thread at a time , its uses fine grained locking mechanism that is called lock stripping to allow a greater degree of shared access.

Arbitrarily many reading threads can access the map concurrently , readers can access the map concurrently with writers and a limited number of writers can modify the map concurrently.

No ConcurrentModificationException

ConcurrentHashMap provides iterator that does not throw ConcurrentModificationException that means we don't need to lock the collection while iterating over it.

The iterator returned by ConcurrentHashMap are weakly consistent instead of being fail-fast that means the weakly consistent iterator does not reflect modifications to the collection after the construction of the iterator.

Java 8 Specific Improvements :

• Java 8 brought about important changes in the way ConcurrentHashMap.
• The map was restructured to use red black trees after the certain size increase( which is 8) HashMap, but with additional concurrency controls. This change improved the map's scalability and performance, particularly in high-contention scenarios.

This improved the worst case get operation in HashMap to the complexity of O(logn) )as opposed to O(n).

A little note about complexities regarding finding an element.

LinkedList

• Average and Worst Case: O(n)

In a linked list, to find an element, you may have to traverse through each node in the worst case. This is because linked lists do not have indexed access to their elements, meaning you can't jump directly to an element. The search operation involves linearly going through nodes until the desired element is found or the list ends.

Red-Black Tree:

• Average and Worst Case: O(logn)
• A red-black tree is a balanced binary search tree. This balance ensures that the tree's height is logarithmic relative to the number of nodes. Therefore, operations like search, insertion, and deletion can be done in logarithmic time. When searching for an element, you start at the root and traverse down the tree, making a decision at each step to go left or right based on the value you're searching for. This divide-and-conquer approach significantly reduces the time complexity compared to a linear search in a linked list.

Note: The reason is in case of collision the Hash Map starts adding the keys with the different values as a node in the linked list which has the worst case get operation complexity as O(n) meaning someone needs to traverse the whole list when we replace that with the red black trees that brings this search complexity to Olog(n).

• In Java 8 certian new methods were added like compute, computeIfAbsent, computeIfPresent, and merge, which allowed atomic updates to the map values using lambda expressions.
• Parallel operations were introduced in Java 8 for ConcurrentHashMap, enabling large-scale parallel operations on the map, such as forEach, search, and reduce.

Common Concurrent Hash Map Operations:

• Operations like get and put are usually non-blocking and do not involve locking.
• Operations like putIfAbsent, remove, and replace are atomic and are used for conditional updates.

Concurrent Hash Map Improvements Over Time

• Lock Stripping: ConcurrentHashMap uses a technique called lock stripping as described earlier where the map is divided into segments, each controlled by its own lock. This design construct allows multiple threads to acquire finer grain locks to improve concurrency.
• As Read operations on ConcurrentHashMap are generally non-blocking, that enhances concurrent hash map performance in scenarios that require heavy reads.
• The iterators provided byConcurrentHashMap are fail-safe, meaning they do not throw ConcurrentModificationException if the map is modified during iteration.
• If the HashMap size reaches over 8 the hash map starts using the red black tress as opposed to the linked list in order to store values which have collisions in the map , improving performance further.