高性能并发MultiMap Java / Scala

我正在寻找一个高性能,并发的MultiMap。 我到处search,但我根本找不到与ConcurrentHashMap(只locking散列数组的一部分)相同方法的解决scheme。

多图将被读取,添加和经常移除。

multimap键将是一个string,它的值将是任意的。

我需要O(1)find给定键的所有值,O(N)可以删除,但O(logN)将是首选。

关键是删除给定键的最后一个值将从键删除容器的值,以防止泄漏内存。

这是我构build的解决scheme,可用于ApacheV2: Index(multimap)

为什么不把ConcurrentHashMap [T,ConcurrentLinkedQueue [U]]和一些很好的类似Scala的方法(例如隐式转换为Iterable,或者你需要什么以及更新方法)进行包装呢?

您是否尝试过Googlecollections夹? 他们有各种Multimap实现。

虽然我没有用过,但还是有一个 。

我做了一个ConcurrentMultiMap的 mixin,它扩展了mutable.MultiMap的mixin并且有一个concurrent.Map [A​​,Set [B]] selftypes。 它locking每个密钥,它具有O(n)空间复杂性,但是如果你不是特别重写的话,它的时间复杂度是非常好的。

你应该试试看。 这里是pdf 。

我有一个要求,我必须有一个Map<Comparable, Set<Comparable>> ,在Map上的插入是并发的,也是在相应的Set上,但是一旦从Map中消耗了一个Key,它必须被删除,如果作为一个Job每两秒钟运行一个特定的Key来使用整个Set<Comparable> ,但插入是完全并发的,这样当Job开始时大部分的值被caching,这里是我的实现:

注意:我使用Guava的助手类Maps来创build并发映射,同样,这个解决scheme模拟实践列表5.19中的Java并发

 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(); } } 

我在这个话题上有点晚了,但我想现在你可以使用番石榴:

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

你看看Javalution是用于实时等,当然高性能。

讨论已经晚了,但是…

当涉及到高性能并发的东西时,应该准备好编码解决scheme。 与此同时, 魔鬼在细节中的陈述具有完整的意义。 可以实现完全并发和无锁的结构。

起始基地将是NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/ ,然后取决于多less个值每个键和多久需要添加/删除一些副本上写Object []的值或一个基于数组的信号量/自旋locking。

Interesting Posts