Is there any Concurrent multi valued HashMap data structure in java?

Question

I have a requirement to have key value pairs, where the value can be a set. This data structure should be thread safe to add remove elements to the set in a multi threaded environment.

My requirement is to create a subscription list, here people can subscribe for different topics. This subscription list should be concurrent, thread safe and fast. I was thinking about Using ConcurentHashMap and ConcurrentHashSet, this will not help me since, I have to put the syncronization block at the top level and it will block the entire map until the put/remove operation completes.

• user207421: Not in the JRE. Maybe in Apache Commons etc.
• Rasekaran: I have checked in Apache Comments I could not find one. There are multi valued hash maps but they are not thread safe.
• Vipin CP: ConcurrentHashMap can be used, with value as SET . Any observation?
• shmosel: Can't you use simple synchronization? Does it have to be a concurrent structure?
• Rasekaran: @shmosel If I use synchronization in top level It will block entire map, then there is no concurrency.

Answer 1

There is no pre-rolled solution, but it is possible to achieve thread-safe concurrency for simple values using a ConcurrentMap<K, Set<V>> which has Set<V> values made from ConcurrentMap<V, Boolean> using Collections.newSetFromMap(Map<V,Boolean>).

Then, to get each value set in an atomic way, use ConcurrentMap.computeIfAbsent(K, Function<? super K, ? extends Set<V>>):

ConcurrentMap<String, Set<Integer>> multimap = new ConcurrentHashMap<>();
Set<Integer> fooValues = multimap.computeIfAbsent("foo", key -> Collections.newSetFromMap(new ConcurrentHashMap<Integer, Boolean>()));

If you want your values to have a stable iteration order, you can use a ConcurrentSkipListSet to hold values instead:

ConcurrentMap<String, NavigableSet<Integer>> multimap = new ConcurrentHashMap<>();
NavigableSet<Integer> fooValues = multimap.computeIfAbsent("foo", key -> new ConcurrentSkipListSet<>());

Likewise, in order to remove Set<V> value holder instances in a thread-safe fashion, you can use ConcurrentMap.computeIfPresent(K, BiFunction<? super K,? super Set<V>,? extends Set<V>>):

public static <K, V> void remove(final ConcurrentMap<K, Collection<? extends V>> multimap, final K key,
 final V value) {
 multimap.computeIfPresent(key, (k, oldValues) -> {
 final Collection<? extends V> newValues;
 if (oldValues.remove(value) && oldValues.isEmpty()) {
 // Remove the empty set from the multimap
 newValues = null;
 } else {
 newValues = oldValues;
 }
 return newValues;
 });
}

Note that there is no "ConcurrentHashSet" class provided by the Java core libraries.

• Rasekaran: Sorry for the delayed responce. I think this is the best way to do it. Let me try it.

Answer 2

you write "the value can be a set", but don't mention what the key is. In any case, Hashtable, the first map that was present in Java, is thread safe wrt adding/removing/replacing key,value pairs.

You can create a thread-safe Set with one of the methods described here. Whether that set is stored as value in an hashmap makes no difference.

• Rasekaran: I have 2 issues with this solution. First one Thread safety in Hashtable in achieved by synchronizing the add remove operation. It makes entire Hashtable inaccessible until the operation completes. Instead I can use a concurrentHashMap.
• Rasekaran: Second issue is, I cannot use a ConcurrentHashMap and ConcurrentHashSet together. Lets say I'm going to add a value to a key First I have to check If there is a set already added to the key. Otherwise I have to add the Set first and then I have to add the value. In this case there is a possibility that another thread can override the set. This also happends when removing values from set. When removing If removing element is the last element in the set Then we have to remove the set from HashMap. What will happen If one thread is adding a value to the set while another removing the set?
• Roberto Attias: I would suggest adding your own synchronized wrapper which hides the set object and just gets the set value. Something like: class MyMap<K, V> { private ConcurrentHashMap<K, ConcurrentHashSet<V>> hm = ... void put(K k, V v) { synchronized(hm) { ConcurrentHashSet<V> hs = hm.get(k) if (hs == null) { hs = new ... } hs.add(v) } } ... }
• Rasekaran: @ Roberto Attias While the put completes no one can access the map and no point of using ConcurrentHashMap.
• errantlinguist: I'm sorry: Hashtable is old and uses a terrible concurrency strategy (i.e. forbidding concurrency); It should never be used in non-legacy code.