Java synchronized block vs. Collections.synchronizedMap

Question

Is the following code set up to correctly synchronize the calls on synchronizedMap?

public class MyClass {
  private static Map<String, List<String>> synchronizedMap = Collections.synchronizedMap(new HashMap<String, List<String>>());

  public void doWork(String key) {
    List<String> values = null;
    while ((values = synchronizedMap.remove(key)) != null) {
      //do something with values
    }
  }

  public static void addToMap(String key, String value) {
    synchronized (synchronizedMap) {
      if (synchronizedMap.containsKey(key)) {
        synchronizedMap.get(key).add(value);
      }
      else {
        List<String> valuesList = new ArrayList<String>();
        valuesList.add(value);
        synchronizedMap.put(key, valuesList);
      }
    }
  }
}

From my understanding, I need the synchronized block in addToMap() to prevent another thread from calling remove() or containsKey() before I get through the call to put() but I do not need a synchronized block in doWork() because another thread cannot enter the synchronized block in addToMap() before remove() returns because I created the Map originally with Collections.synchronizedMap(). Is that correct? Is there a better way to do this?

Teryn

Answer 1

Collections.synchronizedMap() guarantees that each atomic operation you want to run on the map will be synchronized.

Running two (or more) operations on the map however, must be synchronized in a block. So yes - you are synchronizing correctly.

Posterior

I think it would be good to mention that this works because the javadocs explicitly state that synchronizedMap synchronizes on the map itself, and not some internal lock. If that were the case synchronized(synchronizedMap) would not be correct. – Partridgeberry

@Yuval could you explain your answer in a little more depth? You say sychronizedMap does operations atomically, but then why would you ever need your own synchronized block if the syncMap made all your operations atomic? Your first paragraph seems to preclude worrying about the second. – Highsounding

@Highsounding see my answer – Hassler

why is it necessary to have synchronized block as the map already uses Collections.synchronizedMap() ? I am not getting the second point. – Messner

@BimalSharma Because there are two atomic operations on the map in the synchronized block. The synchronized collection guarantees, that no other thread changes its state while contains is called and same for get. But between contains and get another thread might replace or remove the element which was checked via contains, so your get result may not be what you expect. This is why the synchronized block is used, to guarantee no change between these two atomic operations. – Abatement

Answer 2

If you are using JDK 6 then you might want to check out ConcurrentHashMap

Note the putIfAbsent method in that class.

Erkan

Answer 3

There is the potential for a subtle bug in your code.

[UPDATE: Since he's using map.remove() this description isn't totally valid. I missed that fact the first time thru. :( Thanks to the question's author for pointing that out. I'm leaving the rest as is, but changed the lead statement to say there is potentially a bug.]

In doWork() you get the List value from the Map in a thread-safe way. Afterward, however, you are accessing that list in an unsafe matter. For instance, one thread may be using the list in doWork() while another thread invokes synchronizedMap.get(key).add(value) in addToMap(). Those two access are not synchronized. The rule of thumb is that a collection's thread-safe guarantees don't extend to the keys or values they store.

You could fix this by inserting a synchronized list into the map like

List<String> valuesList = new ArrayList<String>();
valuesList.add(value);
synchronizedMap.put(key, Collections.synchronizedList(valuesList)); // sync'd list

Alternatively you could synchronize on the map while you access the list in doWork():

  public void doWork(String key) {
    List<String> values = null;
    while ((values = synchronizedMap.remove(key)) != null) {
      synchronized (synchronizedMap) {
          //do something with values
      }
    }
  }

The last option will limit concurrency a bit, but is somewhat clearer IMO.

Also, a quick note about ConcurrentHashMap. This is a really useful class, but is not always an appropriate replacement for synchronized HashMaps. Quoting from its Javadocs,

This class is fully interoperable with Hashtable in programs that rely on its thread safety but not on its synchronization details.

In other words, putIfAbsent() is great for atomic inserts but does not guarantee other parts of the map won't change during that call; it guarantees only atomicity. In your sample program, you are relying on the synchronization details of (a synchronized) HashMap for things other than put()s.

Last thing. :) This great quote from Java Concurrency in Practice always helps me in designing an debugging multi-threaded programs.

For each mutable state variable that may be accessed by more than one thread, all accesses to that variable must be performed with the same lock held.

Sun

I see your point about the bug if I were accessing the list with synchronizedMap.get(). Since I'm using remove(), shouldn't the next add with that key create a new ArrayList and not interfere with the one that I am using in doWork? – Teryn

Correct! I totally breezed past your remove. – Sun

For each mutable state variable that may be accessed by more than one thread, all accesses to that variable must be performed with the same lock held. ---- I generally add a private property thats just a new Object() and use that for my synconization blocks. That way I know its all through the raw for that context. synchronized (objectInVar){} – Mcmasters

Answer 4

Yes, you are synchronizing correctly. I will explain this in more detail. You must synchronize two or more method calls on the synchronizedMap object only in a case you have to rely on results of previous method call(s) in the subsequent method call in the sequence of method calls on the synchronizedMap object. Let’s take a look at this code:

synchronized (synchronizedMap) {
    if (synchronizedMap.containsKey(key)) {
        synchronizedMap.get(key).add(value);
    }
    else {
        List<String> valuesList = new ArrayList<String>();
        valuesList.add(value);
        synchronizedMap.put(key, valuesList);
    }
}

In this code

synchronizedMap.get(key).add(value);

and

synchronizedMap.put(key, valuesList);

method calls are relied on the result of the previous

synchronizedMap.containsKey(key)

method call.

If the sequence of method calls were not synchronized the result might be wrong. For example thread 1 is executing the method addToMap() and thread 2 is executing the method doWork() The sequence of method calls on the synchronizedMap object might be as follows: Thread 1 has executed the method

synchronizedMap.containsKey(key)

and the result is "true". After that operating system has switched execution control to thread 2 and it has executed

synchronizedMap.remove(key)

After that execution control has been switched back to the thread 1 and it has executed for example

synchronizedMap.get(key).add(value);

believing the synchronizedMap object contains the key and NullPointerException will be thrown because synchronizedMap.get(key) will return null. If the sequence of method calls on the synchronizedMap object is not dependent on the results of each other then you don't need to synchronize the sequence. For example you don't need to synchronize this sequence:

synchronizedMap.put(key1, valuesList1);
synchronizedMap.put(key2, valuesList2);

Here

synchronizedMap.put(key2, valuesList2);

method call does not rely on the results of the previous

synchronizedMap.put(key1, valuesList1);

method call (it does not care if some thread has interfered in between the two method calls and for example has removed the key1).

Hassler

Answer 5

That looks correct to me. If I were to change anything, I would stop using the Collections.synchronizedMap() and synchronize everything the same way, just to make it clearer.

Also, I'd replace

  if (synchronizedMap.containsKey(key)) {
    synchronizedMap.get(key).add(value);
  }
  else {
    List<String> valuesList = new ArrayList<String>();
    valuesList.add(value);
    synchronizedMap.put(key, valuesList);
  }

with

List<String> valuesList = synchronziedMap.get(key);
if (valuesList == null)
{
  valuesList = new ArrayList<String>();
  synchronziedMap.put(key, valuesList);
}
valuesList.add(value);

Tortosa

The thing to do. I don't get it why we should use the Collections.synchronizedXXX() APIs when we still have to synchronize on some object (which will be just the collection itself in most cases) in our every day app's logic – Glebe

Answer 6

The way you have synchronized is correct. But there is a catch

1. Synchronized wrapper provided by Collection framework ensures that the method calls I.e add/get/contains will run mutually exclusive.

However in real world you would generally query the map before putting in the value. Hence you would need to do two operations and hence a synchronized block is needed. So the way you have used it is correct. However.

2. You could have used a concurrent implementation of Map available in Collection framework. 'ConcurrentHashMap' benefit is

a. It has a API 'putIfAbsent' which would do the same stuff but in a more efficient manner.

b. Its Efficient: dThe CocurrentMap just locks keys hence its not blocking the whole map's world. Where as you have blocked keys as well as values.

c. You could have passed the reference of your map object somewhere else in your codebase where you/other dev in your tean may end up using it incorrectly. I.e he may just all add() or get() without locking on the map's object. Hence his call won't run mutually exclusive to your sync block. But using a concurrent implementation gives you a peace of mind that it can never be used/implemented incorrectly.

Scoundrelly

Answer 7

Check out Google Collections' Multimap, e.g. page 28 of this presentation.

If you can't use that library for some reason, consider using ConcurrentHashMap instead of SynchronizedHashMap; it has a nifty putIfAbsent(K,V) method with which you can atomically add the element list if it's not already there. Also, consider using CopyOnWriteArrayList for the map values if your usage patterns warrant doing so.

Transudation