High Performance Parallel MultiMap Java / Scala

Question

I am looking for a high performance parallel MultiMap. I searched everywhere, but I just can't find a solution that uses the same approach as ConcurrentHashMap (only hash array segment lock).

A multimap will often be read, added and removed from it.

The multimap key will be a string, and this value will be arbitrary.

I need O (1) to find all the values ​​for a given key, O (N) is in order to delete, but O (logN) would be preferable.

It is imperative that deleting the last value for a given key removes the container of values ​​from the key so that there is no memory leak.

HERE A SOLUTION, BUILT, available under ApacheV2: Index (multimap)

Answer 1

Why not move ConcurrentHashMap [T, ConcurrentLinkedQueue [U]] with some good Scala methods (like implicit conversion to Iterable or something you need and an update method)?

Answer 2

Have you tried Google Collections? They have various multimap .

Answer 3

There is one in akka , although I have not used it.

Answer 4

I made a ConcurrentMultiMap mixin that extends mutable.MultiMap mixin and has concurrent.Map [A, Set [B]] self type. It blocks every key that has O (n) complexity, but its temporal complexity is pretty good if you're not particularly hard to write.

Answer 5

you should give ctries . here pdf .

Answer 6

I had a requirement, when I had to have Map<Comparable, Set<Comparable>> , where the insert on the map would be parallel, as well as in the corresponding set, but after the key was used up from the map, it had to be removed, think, Work done every two seconds that consumes the whole Set<Comparable> from a specific key, but the insert must be completely parallel so that most of the values ​​are buffered when the task starts, here is my implementation:

Note. . I use Guava Maps helper classes to create parallel Maps. In addition, this solution emulates the Java concurrency in Practical Listing 5.19 :

 import com.google.common.collect.MapMaker; import com.google.common.collect.Sets; import java.util.Collection; import java.util.Set; import java.util.concurrent.ConcurrentMap; /** * A general purpose Multimap implementation for delayed processing and concurrent insertion/deletes. * * @param <K> A comparable Key * @param <V> A comparable Value */ public class ConcurrentMultiMap<K extends Comparable, V extends Comparable> { private final int size; private final ConcurrentMap<K, Set<V>> cache; private final ConcurrentMap<K, Object> locks; public ConcurrentMultiMap() { this(32, 2); } public ConcurrentMultiMap(final int concurrencyLevel) { this(concurrencyLevel, 2); } public ConcurrentMultiMap(final int concurrencyLevel, final int factor) { size=concurrencyLevel * factor; cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).makeMap(); locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(concurrencyLevel).weakKeys().weakValues().makeMap(); } private Object getLock(final K key){ final Object object=new Object(); Object lock=locks.putIfAbsent(key, object); if(lock == null){ lock=object; } return lock; } public void put(final K key, final V value) { synchronized(getLock(key)){ Set<V> set=cache.get(key); if(set == null){ set=Sets.newHashSetWithExpectedSize(size); cache.put(key, set); } set.add(value); } } public void putAll(final K key, final Collection<V> values) { synchronized(getLock(key)){ Set<V> set=cache.get(key); if(set == null){ set=Sets.newHashSetWithExpectedSize(size); cache.put(key, set); } set.addAll(values); } } public Set<V> remove(final K key) { synchronized(getLock(key)){ return cache.remove(key); } } public Set<K> getKeySet() { return cache.keySet(); } public int size() { return cache.size(); } } 

Answer 7

I'm a little late on this topic, but I think now you can use Guava like this:

 Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet) 

Answer 8

You took a look at Javalution , which is designed for real time, etc. and, of course, high performance.

Answer 9

It's late for discussion, but ...

When it comes to high-performance parallel things, you need to prepare code for the solution. With the simultaneous assertion that the Devil has full meaning in detail. This allows you to implement a structure that is completely parallel and loose.

The initial base will be NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/ , and then depending on how many values ​​per key and how often you need to add / remove any copy to the Object [] record for values ​​or array based on Set with semaphore / spin lock.