高性能并发MultiMap Java/Scala

Question

我正在寻找一个高性能,并发的MultiMap.我到处搜索但是我找不到使用与ConcurrentHashMap相同的方法的解决方案(仅锁定哈希数组的一部分).

多图表将经常被读取,添加和删除.

multimap键将是一个String,它的值将是任意的.

我需要O(1)来查找给定键的所有值,O(N)可以删除,但O(logN)将是首选.

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

这是我建立的解决方案,在ApacheV2下可用: 索引(多图)

Answer 1

为什么不用一些类似Scala的方法来包装ConcurrentHashMap [T,ConcurrentLinkedQueue [U]](例如隐式转换为Iterable或者你需要什么,以及更新方法)？

你能否容忍在获得队列时锁定队列,然后在向地图发送更新以清空那个(k,v)对时保持队列？也就是说,使用队列上的锁而不是整个地图来避免碰撞？(并添加逻辑来处理你获得队列的情况,然后,在你可以锁定它之前,它被清空并从地图中删除 - 你所要做的就是检查你何时获得它是非空的锁如果它是空的,则认为它已被删除.) (3认同)
@Viktor - 如果你有（键，值）对，只要在删除键并捕获时将空队列留在那里作为占位符，“map.get(key).remove(value)”就应该可以解决问题如果不存在则例外（包括 get 的 NPE）。如果你不能将队列作为占位符，那么就很难确保安全，除非你在清理残骸时锁定整个地图。 (2认同)
感谢Rex,这种方法似乎很有用:http://gist.github.com/566793 (2认同)
对于那些寻找 Viktor 实现的人，你可以在 `akka.util.ConcurrentMultiMap` 中找到它。非常感谢，维克多！ (2认同)

Answer 2

你试过Google Collections吗？他们有各种Multimap实现.

是的,但我不是在寻找一个多图,我正在寻找一个高性能的_concurrent_ multimap.当我今天早些时候检查它们的源代码时,它们的并发多重映射锁定了整个映射,从而创建了一个串行结构. (6认同)
是的，这是最重要的。 (2认同)