Atomic structures and collections in Java 5: ConcurrentHashMap

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:

Writing to a ConcurrentHashMap locks only a portion of the map;
Reads can generally occur without locking.

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.

Java programming articles and tutorials on this site are written by Neil Coffey (@BitterCoffey). Suggestions are always welcome if you wish to suggest topics for Java tutorials or programming articles, or if you simply have a programming question that you would like to see answered on this site. Most topics will be considered. But in particular, the site aims to provide tutorials and information on topics that aren't well covered elsewhere, or on Java performance information that is poorly described or understood. Suggestions may be made via the Javamex blog (see the site's front page for details).
Copyright © Javamex UK 2012. All rights reserved.

ConcurrentHashMap

Lock striping and ConcurrentHashMap

Next: throughput and scalability of ConcurrentHashMap vs synchronized HashMap

Lock striping and `ConcurrentHashMap`