具有良好性能的多地圖

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