具有良好性能的多地图

Question

在我的代码中，我有一张使用得很厉害的地图，几秒钟后就有几千次。最初我有一个TreeMap，但在测试9000个条目时，我看到我的旧处理器融化了。这需要扩展。所以我转向了HashMap，性能非常好。

现在我正在改变我的设计，并正在寻找一个MultiMap。但是我害怕对性能的影响，因为它必须遍历所有大地图挑选出匹配的键，并且即使同步调用很多次，似乎也会很慢。

有没有一个很好的MultiMap可以处理这么大的性能值？性能在此应用程序中非常重要，因为可能有许多大型单独的映射处理非常大的工作负载，使“小”性能损失成为非常大的问题。

奖励分数，如果它可以提取独立工作，没有任何依赖关系。

Answer 1

都推荐给我的我的问题之一是Apache的百科全书multimap中的一个： http://commons.apache.org/collections/api-3.2.1/org/apache/commons/collections/MultiHashMap.html

它是免费软件，所以你至少可以得到源来看待它，并根据您的许可证情况，你可以修改它或单独使用它。

它在内部使用ArrayList，但我想你可以改变它来使用HashSet或其他东西。我会看看createCollection(Collection coll)方法。

UPDATE：其实，番石榴的HashMultiMap似乎已经成为了我说的是： http://guava-libraries.googlecode.com/svn/trunk/javadoc/index.html

我看了看源，似乎值的每个集合是实际上是由一个HashSet支持。

Answer 2

这个选择很大程度上取决于你想要做什么。有许多数据结构，有些比特定领域的其他数据结构更好，反之亦然。

我可以推荐你潜在的候选人。如果它完全读取，ImmutableMultiMap可能是一个很好的选择。

如果您需要并发读/写，然后我会实现我自己的多重映射，可能使用的ConcurrentHashMap和ConcurrentSkipListSet（你必须要小心，因为同步多重映射和创建使用非这样一个multipmap之间的语义阻止数据结构不同）。如果使用ConcurrentSkipListSet，则可以使用二进制搜索，并且比迭代更快。

如果你有很多行，你也可以从使用ConcurrentHashMap和同步列表开始。这可以显着减少争用，这可能足以解决您的性能问题，而且很简单。

Answer 3

当你提到你“遍历所有大地图挑选匹配键”时，这让我想知道你是否使用了最好的数据结构。有没有办法可以避免这种迭代？

请注意，Guava包含具有不同性能特征的多个multimap实现。正如Zwei提到的，​​ImmutableMultimap比可变的multimaps有更好的性能。如果代码检查multimap是否包含特定值，SetMultimaps速度会更快;否则ArrayListMultimap的性能会更好。

Answer 4

我有一个要求，我必须有一个Map<Comparable, Set<Comparable>>，其中地图上的插入是并发的，并且也在相应的Set上，但是一旦Key从Map消耗完，它必须被删除，认为是Job每两秒钟是从一个特定的重点，但插入消耗整个Set<Comparable>运行完全同步，这样，当作业踢，这里最值缓冲是我实现：

注：我用番石榴的辅助类地图创建并发映射，此解决方案也可模拟实践中的Java并发性列表5.19：

import com.google.common.collect.MapMaker; 

import java.util.concurrent.ConcurrentMap; 

/** 
* Created by IntelliJ IDEA. 
* User: gmedina 
* Date: 18-Sep-2012 
* Time: 09:17:50 
*/ 
public class LockMap<K extends Comparable> 
{ 
    private final ConcurrentMap<K, Object> locks; 

    public LockMap() 
    { 
    this(16, 64); 
    } 

    public LockMap(final int concurrencyLevel) 
    { 
    this(concurrencyLevel, 64); 
    } 

    public LockMap(final int concurrencyLevel, final int initialCapacity) 
    { 
    locks=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).weakValues().makeMap(); 
    } 

    public Object getLock(final K key) 
    { 
    final Object object=new Object(); 
    Object lock=locks.putIfAbsent(key, object); 
    return lock == null ? object : lock; 
    } 

} 


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 initialCapacity; 
    private final LockMap<K> locks; 
    private final ConcurrentMap<K, Set<V>> cache; 

    public ConcurrentMultiMap() 
    { 
    this(16, 64); 
    } 

    public ConcurrentMultiMap(final int concurrencyLevel) 
    { 
    this(concurrencyLevel, 64); 
    } 

    public ConcurrentMultiMap(final int concurrencyLevel, final int initialCapacity) 
    { 
    this.initialCapacity=initialCapacity; 
    cache=new MapMaker().concurrencyLevel(concurrencyLevel).initialCapacity(initialCapacity).makeMap(); 
    locks=new LockMap<K>(concurrencyLevel, initialCapacity); 
    } 

    public void put(final K key, final V value) 
    { 
    synchronized(locks.getLock(key)){ 
     Set<V> set=cache.get(key); 
     if(set == null){ 
     set=Sets.newHashSetWithExpectedSize(initialCapacity); 
     cache.put(key, set); 
     } 
     set.add(value); 
    } 
    } 

    public void putAll(final K key, final Collection<V> values) 
    { 
    synchronized(locks.getLock(key)){ 
     Set<V> set=cache.get(key); 
     if(set == null){ 
     set=Sets.newHashSetWithExpectedSize(initialCapacity); 
     cache.put(key, set); 
     } 
     set.addAll(values); 
    } 
    } 

    public Set<V> remove(final K key) 
    { 
    synchronized(locks.getLock(key)){ 
     return cache.remove(key); 
    } 
    } 

    public Set<K> getKeySet() 
    { 
    return cache.keySet(); 
    } 

    public int size() 
    { 
    return cache.size(); 
    } 

} 

Answer 5

我一直在使用谷歌番石榴作为替代到Apache共享尽可能...以下是其Multimap之的实现HashMultiMap一个例子，并注意地图的值是值的集合而不是一个单一的参考。 get（key）的结果使用“contains（）”方法。

private Multimap<Phase, ResultingState> phaseResults = HashMultimap.create(); 

/** 
* @param withState is the state to be verified. 
* @param onPhase is the phase to be verified. 
* @return Whether the given result was reported in the given phase. 
*/ 
public boolean wasReported(ResultingState withState, Phase onPhase) { 
    return phaseResults.containsKey(onPhase) && phaseResults.get(onPhase).contains(withState); 
} 

/** 
* @param resultingState is the resulting state. 
* @return Whether the given resulting state has ever been reported. 
*/ 
public boolean anyReported(ResultingState resultingState) { 
    return phaseResults.values().contains(resultingState); 
}