我正在寻找一个高性能、并发的MultiMap。我已经到处搜索了，但是我无法找到一种使用与ConcurrentHashMap相同方法的解决方案（仅锁定哈希数组的一部分）。
这个Multimap将经常被读取、添加和删除。
多重映射的键将是字符串，其值将是任意的。
我需要O(1)来查找给定键的所有值，删除操作的时间复杂度为O(N)可以接受，但是如果是O(logN)则更好。
对于某个键的最后一个值的删除非常关键，它将从该键中删除容器的所有值，以避免内存泄漏。
编辑：这是我构建的解决方案，可在ApacheV2下获得：索引（多重映射）
map.get(key).remove(value)应该可以做到这一点，只要在删除键时留下空队列作为占位符，并捕获异常（包括get的NPE）。如果你不能将队列留作占位符，那么除非你锁定整个映射表来清除垃圾，否则很难确保安全。 - Rex Kerrakka.util.ConcurrentMultiMap 中找到它。非常感谢，Viktor！ - Jean-Philippe Pellet您尝试过谷歌收藏吗？它们具有各种Multimap实现。
我有一个需求，需要使用Map<Comparable, Set<Comparable>>，在Map和相应的Set上进行插入操作时必须是并发的，但是一旦从Map中消耗了一个Key，它就必须被删除。可以将其想象为每两秒运行一次的作业，该作业正在消耗来自特定Key的整个Set<Comparable>，但插入操作是完全并发的，因此大多数值在作业启动时会被缓冲，以下是我的实现方式：
注意：我使用Guava的帮助类Maps创建并发Maps，此解决方案还模拟了Java Concurrency in Practice 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();
}
}
我创建了一个 ConcurrentMultiMap mixin，它扩展了 mutable.MultiMap mixin 并具有 concurrent.Map[A, Set[B]] 自身类型。 它按键锁定，具有 O(n) 空间复杂度，但如果您写入不是特别频繁，其时间复杂度相当不错。
Multimaps.synchronizedMultimap(HashMultimap.create())
讨论可能已经有些晚了，但是...
在高性能并发编程方面，一个人应该准备好编写解决方案。在使用Concurrent时，“细节决定成败”的声明具有完整的意义。可以实现完全并发和无锁结构。
起点将是非阻塞HashTable http://sourceforge.net/projects/high-scale-lib/，然后根据每个键的值数量以及需要多频繁添加/删除一些写入对象[]来确定是否需要基于数组的带信号量/自旋锁集合。
我对这个话题有点晚了，但我认为现在你可以像这样使用Guava：
Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)
Multimaps.newSetMultimap(...)支持并发更新吗？根据Javadoc，"如果有任何并发操作更新多重映射，则该映射在这种情况下是不线程安全的，即使映射和工厂生成的实例也是如此。"请参考：http://google.github.io/guava/releases/23.0/api/docs/com/google/common/collect/Multimaps.html#newSetMultimap-java.util.Map-com.google.common.base.Supplier- - breandan