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:
- Caches: for example, after reading the contents of
a given file or database table, we could associate the file name with
its contents (or database key with a representation of the row data) in
- Dictionaires: for example, we could associate
locale abbrevations with a language name;
- Sparse arrays: by mapping integers to values, we
in effect create an array which does not waste space on blank elements.
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
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.