Concurrent Collections in Java

This post is intended to tell you what concurrent collections are, and why they are an improvement over the synchronized collections which have been available since the first versions of the JDK. You will also be introduced to some basic multi-threaded terminology regarding check-then-act sequences and composite operations.

If you are aware of what concurrent collections are and just want information on which ones are available and what their benefits are, you should view [this post] instead.

Synchronized Collections

Before version 1.5, the “thread-safe” collections provided with Java were not very sophisticated. They were called synchronized collections, and they worked by simply wrapping an instance of a collection (e.g. a hash map), and putting the “synchronized” keyword on all of the wrapper methods.

This might sound okay at first, but if we think about it, there are a number of issues:

  • Contention; every method with the “synchronized” keyword requires the monitor lock of the class. This means that while multiple threads may be attempting to use the collection at once, only one at a time can actually do so. The rest perform a blocking wait.
  • Composite operations; many useful operations require a check-then-act sequence, or another operation which is really composed of multiple operations. Synchronized methods guarantee that they will be executed without interference from other threads. They do not help you compose operations though. So, if you wanted two threads to (1) check if a value exists, and (2) add it if it didn’t already exist, then you would have to use additional client-side locking to make sure that those operations were executed together. If you didn’t use the additional locking, then the operations between the two threads could interleave resulting in:
    • Thread 1 and thread 2 both check and find {x} does not exist.
    • Thread 1 adds {x}.
    • Thread 2 tries to add {x} and fails because it already exists.

An interesting thing to note here is that synchronised collections always synchronize on the reference to the underlying collection. This is actually a benefit in some ways, because it means that the client can lock that collection themselves to form their own composite operations. Since concurrent collections use various internal locking mechanisms, it is not possible to use client side locking to form your own composite operations with them. So, you get built-in, better-performing common composite operations with concurrent collections, but you lose the ability to make your own composite operations.

Concurrent Collections

In Java 1.5, concurrent collection classes were added to address the shortcomings of the synchronized collections. Unlike synchronized collections, concurrent collections are not implemented by serializing access to the underlying class via synchronized methods. Instead, they were designed to minimize the scope of internal locking wherever possible. They allow multiple parallel readers and a limited number of parallel writers. They also may implement different interfaces to allow them to provide additional operations useful in a concurrent setting. For example, common composite operations like put-if-absent and replace are built right into ConcurrentHashMap, which implements the ConcurrentMap interface.

Let’s take a look at the JavaDoc for the ConcurrentMap class to see an example:

We can see the following:

Methods inherited from java.util.Map:

clear, containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keySet, put, putAll, remove, size, values

New Methods Specified:

putIfAbsent : If the specified key is not already associated with a value, associate it with the given value.
remove : Removes the entry for a key only if currently mapped to a given value.
replace : Replaces the entry for a key only if currently mapped to some value

You can refer to the documentation link above to get more information; about these composite methods; this list was copied from there. The purpose of this post is just to inform you that they exist and are better supported by concurrent collections than synchronized collections.

Sample Composite Operation

Now… let’s look at an example of a composite operation. A typical composite operation is a check-then-act sequence where you (1) check a condition and then (2) act on that condition. Whenever you do this, you open the door for threading issues due to interleaving of operations as mentioned earlier. The “putIfAbsent()” operation in the ConcurrentHashMap interface is an example of a concurrent collection providing composite action support. It atomically performs the following operation to ensure no interleaving occurs:

V putIfAbsent(K key, V value):

              if (!map.containsKey(key))
                  return map.put(key, value);
                  return map.get(key);

Wrapping Up

Now that you’ve been exposed to the concepts of synchronized collections and concurrent collections, you should take a look at [next post] to see the various kinds of concurrent collections, and the new operations they support. Knowing what’s available in the Java libraries in advance can save you from implementing many of these features yourself (and having to test them) in the future.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s