61

高性能で同時実行可能な MultiMap を探しています。どこでも検索しましたが、ConcurrentHashMap (ハッシュ配列のセグメントのみをロックする) と同じアプローチを使用するソリューションを見つけることができません。

マルチマップは、頻繁に読み取られ、追加され、削除されます。

multimap キーは文字列で、その値は任意です。

特定のキーのすべての値を見つけるには O(1) が必要です。O(N) は削除しても問題ありませんが、O(logN) が優先されます。

特定のキーの最後の値を削除すると、メモリ リークが発生しないように、キーから値のコンテナーが削除されることが重要です。

編集：これが私が構築したソリューションです。ApacheV2で利用できます： インデックス（マルチマップ）

4

10 に答える 10

12

ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] を素敵な Scala ライクなメソッド (例: Iterable への暗黙の変換または必要なものへの変換、および更新メソッド) でラップしてみませんか?

于 2010-09-03T13:22:54.607 に答える
8

Google コレクションを試しましたか? さまざまなMultimap実装があります。

于 2010-09-03T11:35:32.527 に答える
4

私は使っていませんが、akkaにもあります。

于 2013-06-17T13:51:12.993 に答える
2

マップへの場所の挿入と対応するセットへの同時挿入が必要であるという要件がありましたMap<Comparable, Set<Comparable>>が、キーがマップから消費されたら、キーを削除する必要がありました。2 秒ごとに実行されるジョブとして特定のキーから全体を消費していますSet<Comparable>が、挿入は完全に同時であるため、ジョブが開始されたときにほとんどの値がバッファリングされます。これが私の実装です:

注: Guava のヘルパー クラス Maps を使用して同時実行マップを作成します。また、このソリューションは、プラクティス リスト 5.19 で Java 同時実行をエミュレートします。

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

}
于 2012-09-12T10:11:02.470 に答える
1

ctriesを試してみてください。ここにpdfがあります。

于 2011-11-21T21:16:53.107 に答える
0

Gauava の MultiMaps を使用します。 Multimaps.synchronizedMultimap(HashMultimap.create())

于 2019-11-02T22:35:09.460 に答える
-1

リアルタイムなどを想定し、もちろん高性能なJavalutionをご覧になったことはありますか？

于 2010-09-03T12:14:24.717 に答える