在没有种族的ConcurrentMultimap上实现删除

Question

我一直在研究编写并发多机的问题，我有一个由谷歌番石榴 AbstractSetMultimap支持的实现和一个按需创建值的MapMaker计算映射--集合作为一个ConcurrentHashMap的集合视图。通过对视图集合和各种包装的一些关注，我认为这是非常接近的。

讨论已经是其他 有尝试过的一个大问题，它似乎是在没有引入竞争条件的情况下，将值从底层映射中移除。

似乎有几个选项存在。

• 把空的收藏品留在那里。这会泄漏一些CHMs，但我相信至少是正确的。
• 乐观地尝试在空时删除集合，并对其中出现的任何其他内容进行补偿。这是充满种族，似乎本质上是不可能解决的。
• 同步值-集合上的所有内容，这至少允许这种删除，但代价是在通过键进行初始查找之后的任何并发性。
• 为了更小的代价(可能，取决于使用模式？)，也许在值上同步--集合创建和删除--需要检查这是否涵盖了所有内容。

问题：

• 有人知道比这更好的实现吗？我们是否可以更好地组合MapMaker的部分，或者这需要一个从头开始编写的专门的ConcurrentHashMultimap？
• 如果在这方面很难改进，那么这个漏洞在实践中很可能是个大问题吗？值得注意的集合，如java.util.HashMap、juc.ConcurrentHashMap和ArrayDeque，不会向下调整后备存储的大小，而ArrayList也不会自动调整大小。只要我们清除这些物体，我就不知道这是否太重要了。

谢谢

编辑：也见番石榴邮件列表上的这里的讨论。

编辑2:，我已经写了这篇文章。有关实现，请参见这个Google代码区。我非常感谢任何尝试过它的人的反馈，而不是这里。

Answer 1

作为后续，下面是我在前面的讨论中省略的一些细节，您已经链接到了这些细节，这些细节都是关于我并发的multimap实现的。

该实现遵循了您的第一个建议:将空集合保留在支持图中。下面的实时视图行为使您的其他建议更加复杂。

Multimap<String, Integer> multimap = HashMultimap.create();
Set<Integer> set = multimap.get("foo");
multimap.put("foo", 1);
int count = set.size();   // equals 1

对于一个实际的应用程序，而不是集合库类，少于一个完全并发的multimap可能就足够了。您可以定义自己的类，以实现Multimap接口的子集或有限选择的并发性保证。或者，您的应用程序逻辑可以最小化同步multimap的争用，以避免性能问题。

Answer 2

我之前问过同样的问题，最后实现了4种不同的实现。

问题：高性能并发MultiMap Java/Scala

impl (我称之为索引) http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314

Answer 3

如果您真的不想泄漏空集合，您可以尝试用一个按键占位符来替换它。这样，并发添加/删除或添加/添加应该能够在再次展开时达到一致状态。