性能良好的多重映射

在我的一个问题中向我推荐的是Apache Commons MultiMap: http://commons.apache.org/collections/api-3.2.1/org/apache/commons/collections/MultiHashMap.html

它在内部使用ArrayList,但我想您可以将其更改为使用HashSet之类的东西。我会看看 createCollection(Collection coll) 方法。

更新:事实上,Guava的HashMultiMap似乎已经是我所说的: https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Multimap.java

我查看了源代码,似乎每个值集合实际上都有一个HashSet支持。

Map<Comparable, Set<Comparable>> 如果在映射上的插入是并发的,并且也是在相应的集合上,但是一旦从映射中消耗了一个键,就必须将其删除,那么如果将其视为每两秒钟运行一次的作业,它将消耗整个映射 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();
  }

}

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

如果你需要的话

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

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

当你提到你“在一个大地图上迭代,找出匹配的键”时,我不禁怀疑你是否使用了最好的数据结构。有没有办法避免这种迭代?

请注意,Guava包含多个具有不同性能特征的multimap实现。正如Zwei所提到的,不可变多重映射比可变多重映射具有更好的性能。如果代码检查multimap是否包含特定值,setmultimap会更快;否则,ArrayListMultimap的性能会更好。