Pattern for Java ConcurrentHashMap of Sets

Question

A data structure that I use commonly in multi-threaded applications is a ConcurrentHashMap where I want to save a group of items that all share the same key. The problem occurs when installing the first item for a particular key value.

The pattern that I have been using is:

final ConcurrentMap<KEYTYPE, Set<VALUETYPE>> hashMap = new ConcurrentHashMap<KEYTYPE, Set<VALUETYPE>>();
// ...
Set<VALUETYPE> newSet = new HashSet<VALUETYPE>();
final Set<VALUETYPE> set = hashMap.putIfAbsent(key, newSet)
if (set != null) {
  newSet = set;
}
synchronized (newSet) {
  if (!newSet.contains(value)) {
    newSet.add(value);
  }
}

Is there a better pattern for doing this operation? Is this even thread-safe? Is there a better class to use for the inner Set than java.util.HashSet?

Answer 1

I strongly recommend using the Google Guava libraries for this, specifically an implementation of Multimap. The HashMultimap would be your best bet, though if you need concurrent update opterations you would need to wrap it in a delegate using Multimaps.synchronizedSetMultimap().

Another option is to use a ComputingMap (also from Guava), which is a map that, if the Value returned from a call to get(Key) does not exist, it is instantiated there and then. ComputingMaps are created using MapMaker.

The code from your question would be roughly:

ConcurrentMap<KEYTYPE, Set<VALUETYPE>> hashMap = new MapMaker()
                 .makeComputingMap(
        new Function<KEYTYPE, VALUETYPE>() {
         public Graph apply(KEYTYPE key) {
           return new HashSet<VALUETYPE>();
         }
       });

The Function would only be called when a call to get() for a specific key would otherwise return null. This means that you can then do this:

hashMap.get(key).put(value);

safely knowing that the HashSet<VALUETYPE> is created if it doesn't already exist.

MapMaker is also relevant because of the control it gives you over the tuning of the returned Map, letting you specify, for example, the concurrency level using the method concurrencyLevel(). You may find that useful:

Guides the allowed concurrency among update operations. Used as a hint for internal sizing. The table is internally partitioned to try to permit the indicated number of concurrent updates without contention. Because assignment of entries to these partitions is not necessarily uniform, the actual concurrency observed may vary.

Answer 2

I think using java.util.concurrent.ConcurrentSkipListMap and java.util.concurrent.ConcurrentSkipListSet could help you resolve the concurrency concerns.