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.

I have checked in Apache Comments I could not find one. There are multi valued hash maps but they are not thread safe. — Rasekaran, Oct 27 '17 at 05:30
ConcurrentHashMap can be used, with value as SET . Any observation? — Vipin CP, Oct 27 '17 at 05:46
Can't you use simple synchronization? Does it have to be a concurrent structure? — shmosel, Oct 27 '17 at 06:09
@shmosel If I use synchronization in top level It will block entire map, then there is no concurrency. — Rasekaran, Oct 27 '17 at 09:35
Right, I was asking whether that's acceptable. An alternative is to use `ConcurrentHashMap.compute()` and its friends to atomically update (or replace) values. — shmosel, Oct 27 '17 at 09:41
When it comes to concurrency, the devil is in the details. The more detail you can provide, the better chance you have at getting a solution. It would be ideal if you could provide a [mcve] demonstrating your use case. — shmosel, Oct 27 '17 at 09:42
@vipincp When I add value to map I have to check if set is already added for the key and then add the value to the set. if set is not there I have to add the set and the value. Consider the following scenarios, 1) 2 threads adding value at the same time to a key which does not have set in the map. 2) one thread is adding and other thread is removing the last value of the set for the same key.( when removing last value in the set it has to remove the set as well so that there will not be memory issue ) in both cases there is a high possibility of loosing the data. — Rasekaran, Oct 27 '17 at 09:46
https://stackoverflow.com/questions/3635292/high-performance-concurrent-multimap-java-scala — , Oct 27 '17 at 10:29
@Rasekaran: You can consider using Guava's [Striped class](https://static.javadoc.io/com.google.guava/guava/23.0/com/google/common/util/concurrent/Striped.html) for more fine-grained concurrency that doesn't lock the entire map. — Henrik Aasted Sørensen, Oct 27 '17 at 10:30

errantlinguist · Answer 1 · 2017-10-27T11:35:00.873

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.

Sorry for the delayed responce. I think this is the best way to do it. Let me try it. — Rasekaran, Nov 02 '17 at 13:00

score -1 · Answer 2 · answered Oct 27 '17 at 05:42

-1

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.

answered Oct 27 '17 at 05:42

Roberto Attias

1,883
1
11
21

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 Oct 27 '17 at 06:15
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? – Rasekaran Oct 27 '17 at 06:15
1

I would suggest adding your own synchronized wrapper which hides the set object and just gets the set value. Something like: class MyMap { private ConcurrentHashMap> hm = ... void put(K k, V v) { synchronized(hm) { ConcurrentHashSet hs = hm.get(k) if (hs == null) { hs = new ... } hs.add(v) } } ... } – Roberto Attias Oct 27 '17 at 06:59
@ Roberto Attias While the put completes no one can access the map and no point of using ConcurrentHashMap. – Rasekaran Oct 27 '17 at 10:06
1

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. – errantlinguist Oct 27 '17 at 10:31

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

2 Answers2