高性能并发 MultiMap Java/Scala

Question

我正在寻找高性能、并发的 MultiMap。我已经到处搜索，但我根本找不到使用与 ConcurrentHashMap 相同方法的解决方案（仅锁定哈希数组的一部分）。

多重映射将被经常读取、添加和删除。

多重映射键将是一个字符串，其值是任意的。

我需要 O(1) 来查找给定键的所有值，O(N) 可以删除，但 O(logN) 会更好。

至关重要的是，删除给定键的最后一个值将从该键中删除值的容器，以免泄漏内存。

编辑：这是我构建的解决方案，可在 ApacheV2 下使用： 索引（多图）

Answer 1

为什么不使用一些类似 Scala 的好方法包装 ConcurrentHashMap[T,ConcurrentLinkedQueue[U]] （例如，隐式转换为 Iterable 或您需要的任何内容，以及更新方法）？

Answer 2

您尝试过 Google 收藏集吗？他们有各种Multimap 实施。

Answer 3

akka中有一个一个虽然我没有使用过它。

Answer 4

我有一个要求，我必须有一个 Map> ，其中 Map 上的插入是并发的，并且在相应的 Set 上也是并发的，但是一旦从 Map 中消耗了一个 Key ，它必须被删除，想想如果作为一个每两秒运行一次的作业，它会消耗来自特定键的整个Set，但插入是完全并发的，以便在作业时大多数值被缓冲开始，这是我的实现：

注意：我使用 Guava 的辅助类 Maps 来创建并发 Map，此外，该解决方案模拟 实践清单 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();
  }

}

Answer 5

我做了一个 ConcurrentMultiMap mixin 扩展了 mutable.MultiMap mixin 并具有 concurrent.Map[A, Set[B]] 自类型。它对每个键进行锁定，空间复杂度为 O(n)，但如果您的写入量不是特别大，那么它的时间复杂度相当不错。

Answer 6

你应该尝试 ctries 。这是pdf 。

Answer 7

现在讨论已经晚了，但是......

当涉及高性能并发的东西时，应该准备好编写解决方案。
对于 Concurrent，细节决定成败这句话有了完整的含义。
可以实现完全并发且无锁的结构。

起始基础是非阻塞哈希表 http://sourceforge.net/projects/high-scale-lib / 然后取决于每个键有多少个值以及需要在写入 Object[] 上添加/删除一些副本的频率，以获取值或带有信号量/自旋锁的基于数组的 Set。

Answer 8

我在这个话题上有点晚了，但我想，现在，你可以像这样使用 Guava：

Multimaps.newSetMultimap(new ConcurrentHashMap<>(), ConcurrentHashMap::newKeySet)

Answer 9

使用 Gauava 的 MultiMaps。
Multimaps.synchronizedMultimap(HashMultimap.create())

Answer 10

您是否看过 Javalution ，它旨在实现实时等，当然还有高性能。