ConcurrentHashMap

If you are interviewing, consider buying our number#1 course for Java Multithreading Interviews.

HashMaps and Concurrency

HashMap is a commonly used data structure offering constant time access, however, it is not thread-safe. Consider the two methods get() and put() that get invoked by two different threads on an instance of HashMap in the following sequence:

1. Thread 1 invokes put() and inserts the key value pair ("myKey","item-1")

2. Thread 2 invokes get() but before get operation completes, the thread is context-switched

3. Thread 1 updates myKey with a new value say "item-2"

4. Thread 2 becomes active again but retrieves the stale key value pair ("myKey","item-1")

The above scenario is naive and one may argue that if stale values are acceptable for an application then we may get away without using synchronization. However, that is not true. Consider the scenario when a HashMap reaches capacity and resizes. When a resize occurs the elements from the old structure are copied over to the new structure and a rehashing of the elements that hash to the same bucket and form a collision list may take place to reduce the size of the collision list. As one can imagine, there are several things that can go wrong when multiples threads operate on a map whilst the resize takes place. For instance, a reader thread might be iterating over the ...