Key structures implemented as part of the Java Collections API are various types of maps, and in particular the hash map (via the HashMap class and other related classes).

Maps allow you to associate keys with values and crop up in all sorts of uses such as:

Frequently-accessed hash maps can be important on server applications for caching purposes. And as such, they can receive a good deal of concurrent access. Before Java 5, the standard HashMap implementation had the weakness that accessing the map concurrently meant synchronizing on the entire map on each access. This means that, for example, a frequently-used cache implemented as a hash map can encounter high contention: multiple threads attempting to access the map at the same time frequently have to block waiting for one another.

Lock striping and ConcurrentHashMap

Synchronizing on the whole map fails to take advantage of a possible optimisation: because hash maps store their data in a series of separate buckets, it is in principle possible to lock only the portion of the map that is being accessed. This optimisation is generally called lock striping.

Java 5 brings a hash map optimised in this way in the form of ConcurrentHashMap. A combination of lock striping plus judicious use of volatile variables gives the class two highly concurrent properties:

Next: throughput and scalability of ConcurrentHashMap vs synchronized HashMap

The benefits of ConcurrentHashMap over a regular synchronized HashMap become blatantly apparent when we run a small experiment to simulate what might happen in the case of a map used as a frequently-accessed cache on a moderately busy server. On the next page, we discuss the scalability of ConcurrentHashMap in the light of such a simulation.