java - 在没有竞争的情况下在并发多映射上实现删除

Question

我一直在看写并发的问题Multimap ，我有一个由 Google Guava 支持的实现AbstractSetMultimap 和一个 MapMaker 计算 map ，它按需创建值集合作为 ConcurrentHashMap 上的 Collection View 。通过对 View 集合和各种包装器的一些关注，我认为这已经非常接近了。

大问题，已经是discussed通过 others谁have尝试过这个，似乎是在值集合变空时从底层映射中删除值集合，而不引入竞争条件。

似乎存在几个选项。

• 将空集合留在那里。这会泄露一些 CHM，但我相信它至少是正确的。
• 乐观地尝试在集合为空时移除集合，如果其中出现任何其他内容则进行补偿。这充满了种族，似乎本质上无法解决。
• 同步 values-collection 上的所有内容，这至少会允许此删除，但代价是在按键初始查找后的任何并发性。
• 对于较小的惩罚(可能取决于使用模式？)，可能会同步值集合的创建和删除，需要检查是否涵盖所有内容。

问题:

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

谢谢

---

编辑:另见 the discussion here在 Guava 邮件列表上。

---

编辑 2: 我已将其记录下来。请看this Google code area一个实现。我将非常感谢任何尝试过它的人的反馈，无论是在那里而不是在这里。

Answer 1

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

问题: High-performance Concurrent MultiMap Java/Scala

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