2

在我的代码中，我有一张在几秒钟内被大量使用的地图，几千次。最初我有一个 TreeMap，但在测试 9,000 个条目时，我看到我的旧处理器融化了。这需要扩展。所以我搬到了一个 HashMap 并且性能非常好。

现在我正在改变我的设计并正在寻找一个 MultiMap。但是我担心对性能的影响get()，因为它必须遍历所述大地图来挑选匹配的键，并且当多次调用甚至同步时，它似乎会很慢。

是否有一个好的 MultiMap 可以处理如此大的值并具有出色的性能？性能在此应用程序中至关重要，因为可能有许多大型独立地图处理非常大的工作负载，这使得“小”性能损失成为非常大的问题。

如果可以提取它以单独工作而没有任何依赖关系，则可以加分。

4

5 回答 5

4

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

它是免费软件，因此您至少可以获取源代码来查看它，并且根据您的许可情况，您可以修改它或单独使用它。

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

更新：实际上，番石榴的 HashMultiMap 似乎已经是我所说的： https ://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Multimap.java

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

于 2010-08-10T04:44:46.620 回答
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 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();
  }

}
于 2012-09-12T21:00:49.430 回答
1

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

我可以向您推荐潜在的候选人。如果完全阅读，ImmutableMultiMap 可能是一个不错的选择。

如果您需要并发读/写，那么我会实现我自己的多图，也许使用 ConcurrentHashMap 和 ConcurrentSkipListSet （您需要小心，因为同步多图和使用非阻塞数据结构以这种方式创建的多图之间的语义不同）。如果你使用 ConcurrentSkipListSet，你可以使用二分搜索，它比迭代更快。

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

于 2010-08-10T11:01:32.913 回答
1

我一直在尽可能地使用 Google Guava 作为 Apache Commons 的替代品……这里有一个 Multimap 实现 HashMultiMap 的示例，请注意地图的值是值的集合，而不是单个引用。方法“contains()”用于 get(key) 的结果。

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);
}
于 2013-11-16T16:50:19.023 回答
0

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

请注意，Guava 包含多个具有不同性能特征的多图实现。正如 Zwei 提到的，ImmutableMultimap 比可变多图具有更好的性能。如果您的代码检查多图是否包含特定值，则 SetMultimap 会更快；否则 ArrayListMultimap 表现更好。

于 2010-09-07T02:29:48.267 回答