高性能并发 MultiMap Java/Scala
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3635292/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
High-performance Concurrent MultiMap Java/Scala
提问by Viktor Klang
I am looking for a high-performance, concurrent, MultiMap. I have searched everywhere but I simply cannot find a solution that uses the same approach as ConcurrentHashMap (Only locking a segment of the hash array).
我正在寻找高性能、并发的 MultiMap。我到处搜索，但我根本找不到使用与 ConcurrentHashMap 相同方法的解决方案（仅锁定哈希数组的一部分）。
The multimap will be both read, added to and removed from often.
多图将经常被读取、添加和删除。
The multimap key will be a String and it's value will be arbitrary.
multimap 键将是一个字符串，它的值将是任意的。
I need O(1) to find all values for a given key, O(N) is OK for removal, but O(logN) would be preferred.
我需要 O(1) 来查找给定键的所有值，O(N) 可以删除，但 O(logN) 将是首选。
It is crucial that removal of the last value for a given key will remove the container of values from the key, as to not leak memory.
删除给定键的最后一个值将从键中删除值的容器，以免泄漏内存，这一点至关重要。
EDIT: HERE'S THE SOLUTION I BUILT, available under ApacheV2: Index (multimap)
编辑：这是我构建的解决方案，在 ApacheV2 下可用： 索引（多图）
回答by Rex Kerr
Why not wrap ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] with some nice Scala-like methods (e.g. implicit conversion to Iterable or whatever it is that you need, and an update method)?
为什么不用一些类似 Scala 的好方法（例如隐式转换为 Iterable 或任何您需要的方法，以及更新方法）来包装 ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] ？
回答by Jon Freedman
回答by lisak
There is one in akkaalthough I haven't used it.
回答by nnythm
I made a ConcurrentMultiMapmixin which extends the mutable.MultiMap mixin and has a concurrent.Map[A, Set[B]] self type. It locks per key, which has O(n) space complexity, but its time complexity is pretty good, if you aren't particularly write-heavy.
我做了一个ConcurrentMultiMapmixin，它扩展了 mutable.MultiMap mixin 并有一个 concurrent.Map[A, Set[B]] 自我类型。它锁定每个键，它具有 O(n) 空间复杂度，但它的时间复杂度非常好，如果你不是特别喜欢写。
回答by Guido Medina
I had a requirement where I had to have a Map<Comparable, Set<Comparable>>where insertion on the Map be concurrent and also on the corresponding Set, but once a Key was consumed from the Map, it had to be deleted, think if as a Job running every two seconds which is consuming the whole Set<Comparable>from an specific Key but insertion be totally concurrent so that most values be buffered when the Job kicks in, here is my implementation:
我有一个要求，我必须Map<Comparable, Set<Comparable>>在 Map 上的 where 插入是并发的，并且在相应的 Set 上插入，但是一旦从 Map 中消耗了一个 Key，它就必须被删除，想想如果作为每两秒运行一次的作业正在Set<Comparable>从特定的 Key 中消耗整个但插入是完全并发的，以便在 Job 开始时缓冲大多数值，这是我的实现：
Note:I use Guava's helper class Maps to create the concurrent Maps, also, this solution emulates Java concurrency in Practice Listing 5.19:
注意：我使用 Guava 的辅助类 Maps 来创建并发映射，而且，这个解决方案模拟了实践清单 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();
}
}
回答by deep
Use MultiMaps from Gauava.
Multimaps.synchronizedMultimap(HashMultimap.create())
使用 Gauava 的 MultiMaps。
Multimaps.synchronizedMultimap(HashMultimap.create())
回答by bestsss
It's late for the discussion, yet...
讨论已经晚了，但......
When it comes to high performance concurrent stuff, one should be prepared to code the solution. With Concurrent the statement the Devil is in the detailshas a complete meaning. It's possible to implement the structure fully concurrent and lock-free.
当谈到高性能并发的东西时，应该准备好编写解决方案。与 Concurrent 相比，Devil is in the details的陈述具有完整的含义。可以实现完全并发和无锁的结构。
Starting base would be the NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/and then depending how many values per key and how often need to add/remove some copy on write Object[] for values or an array based Set with semaphore/spin lock.
起始基础将是 NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/，然后取决于每个键有多少个值以及需要在写入 Object[] 时为值添加/删除一些副本的频率或带有信号量/自旋锁的基于数组的集合。
回答by khmarbaise
Have you taken a look to Javalutionwhich is intended for Real time etc. and of course high performance.
您是否看过Javalution，它旨在用于实时等，当然还有高性能。
回答by teo
I am a bit late on this topic but I think, nowadays, you can use Guava like this:
我在这个话题上有点晚了，但我认为，现在，你可以像这样使用番石榴：
Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)
