我正在寻找一个高性能、并发的 MultiMap。我到处搜索，但我根本找不到使用与 ConcurrentHashMap 相同的方法的解决方案（仅锁定哈希数组的一部分）。
多图将经常被读取、添加和删除。
多映射键将是一个字符串，它的值将是任意的。
我需要 O(1) 来查找给定键的所有值，O(N) 可以删除，但 O(logN) 将是首选。
至关重要的是，删除给定键的最后一个值将从键中删除值的容器，以免泄漏内存。
编辑：这是我构建的解决方案，在 ApacheV2 下可用： 索引（多图）
问问题
18756 次
10 回答
12
为什么不用一些很好的类似 Scala 的方法（例如隐式转换为 Iterable 或您需要的任何东西，以及更新方法）包装 ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] ？
于 2010-09-03T13:22:54.607 回答
8
你试过谷歌收藏吗？他们有各种Multimap实现。
于 2010-09-03T11:35:32.527 回答
4
akka中有一个，虽然我没用过。
于 2013-06-17T13:51:12.993 回答
3
我制作了一个ConcurrentMultiMap mixin，它扩展了 mutable.MultiMap mixin 并具有 concurrent.Map[A, Set[B]] 自类型。它锁定每个键，具有 O(n) 空间复杂度，但它的时间复杂度非常好，如果你不是特别多写的话。
于 2013-07-11T05:26:32.747 回答
2
我有一个要求，我必须Map<Comparable, Set<Comparable>>在 Map 和相应的 Set 上同时插入 where正在消耗Set<Comparable>来自特定 Key 的全部内容，但插入是完全并发的，以便在 Job 启动时缓冲大多数值，这是我的实现：
注意：我使用 Guava 的辅助类 Maps 来创建并发 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();
}
}
于 2012-09-12T10:11:02.470 回答
0
讨论已经晚了，但...
当涉及到高性能并发的东西时，应该准备好编写解决方案的代码。在 Concurrent 中，Devil is in the details的陈述具有完整的含义。可以实现完全并发和无锁的结构。
起始基础将是 NonBlocking Hashtable http://sourceforge.net/projects/high-scale-lib/，然后取决于每个键有多少值以及在写入 Object[] 时需要添加/删除一些副本的频率或带有信号量/自旋锁的基于数组的集合。
于 2011-11-22T00:47:21.553 回答
0
我在这个话题上有点晚了，但我认为，现在，你可以像这样使用 Guava：
Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)
于 2017-05-31T09:19:46.453 回答
0
使用 Gauava 的 MultiMaps。
Multimaps.synchronizedMultimap(HashMultimap.create())
于 2019-11-02T22:35:09.460 回答
-1
您是否看过Javalution，它适用于实时等，当然还有高性能。
于 2010-09-03T12:14:24.717 回答