Home  Synchronization and concurrency  wait/notify  final  volatile  synchronized keyword  Java threading  Deadlock (and avoiding it)  Java 5: ConcurrentHashMap  Atomic variables  Explicit locks  Queues  Semaphores  CountDownLatch  CyclicBarrier

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:

  • 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 a HashMap;
  • 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 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.

Article written by Neil Coffey (@BitterCoffey).

Software

 LetterMeister (word puzzle game for iPhone)
 Currency Quoter (currency converter/predictor)
 French Vocab Games for iPhone/iPad
 Vocabularium: create Spanish vocab podcasts


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 © Neil Coffey 2014. All rights reserved.