Java concurrency with a Map of Lists

Question

I have a java class that is accessed by a lot of threads at once and want to make sure it is thread safe. The class has one private field, which is a Map of Strings to Lists of Strings. I've implemented the Map as a ConcurrentHashMap to ensure gets and puts are thread safe:

public class ListStore {

  private Map<String, List<String>> innerListStore;

  public ListStore() {
    innerListStore = new ConcurrentHashMap<String, List<String>>();
  }
  ...
}

So given that gets and puts to the Map are thread safe, my concern is with the lists that are stored in the Map. For instance, consider the following method that checks if a given entry exists in a given list in the store (I've omitted error checking for brevity):

public boolean listEntryExists(String listName, String listEntry) {

  List<String> listToSearch = innerListStore.get(listName);

  for (String entryName : listToSearch) {
    if(entryName.equals(listEntry)) {
      return true;
    }
  }

  return false;
}

It would seem that I need to synchronize the entire contents of this method because if another method changed the contents of the list at innerListStore.get(listName) while this method is iterating over it, a ConcurrentModificationException would be thrown.

Is that correct and if so, do I synchronize on innerListStore or would synchronizing on the local listToSearch variable work?

UPDATE: Thanks for the responses. It sounds like I can synchronize on the list itself. For more information, here is the add() method, which can be running at the same time the listEntryExists() method is running in another thread:

public void add(String listName, String entryName) {

  List<String> addTo = innerListStore.get(listName);
  if (addTo == null) {
    addTo = Collections.synchronizedList(new ArrayList<String>());
    List<String> added = innerListStore.putIfAbsent(listName, addTo);
    if (added != null) {
      addTo = added;
    }
  }

  addTo.add(entryName);
}

If this is the only method that modifies the underlying lists stored in the map and no public methods return references to the map or entries in the map, can I synchronize iteration on the lists themselves and is this implementation of add() sufficient?

Answer 1

You can synchronize on listToSearch ("synchronized(listToSearch) {...}"). Make sure that there is no race condition creating the lists (use innerListStore.putIfAbsent to create them).

Answer 2

You could synchronize on just listToSearch, there's no reason to lock the entire map any time anyone is using just one entry.

Just remember though, that you need to synchronize on the list everywhere it is modified! Synchronizing the iterator doesn't automagically block other people from doing an add() or whatnot if you passed out to them references to the unsynchronized list.

It would be safest to just store synchronized lists in the Map and then lock on them when you iterate, and also document when you return a reference to the list that the user must sycnhronize on it if they iterate. Synchronization is pretty cheap in modern JVMs when no actual contention is happening. Of course if you never let a reference to one of the lists escape your class, you can handle it internally with a finer comb.

Alternately you can use a threadsafe list such as CopyOnWriteArrayList that uses snapshot iterators. What kind of point in time consistency you need is a design decision we can't make for you. The javadoc also includes a helpful discussion of performance characteristics.