ArrayListMultimap 与 LinkedListMultimap 有何不同？

所以，我只是在阅读 javadocArrayListMultimap and LinkedListMultimap为了了解如何使用它们，我开始知道两者都支持重复的键值对（我的意思是相同的键，不同的值 - 如果我理解正确的话。如果我错了，请纠正我）。但是，我不明白它们之间的区别。两者都用于存储重复的键值对。他们唯一不同的是他们的实施，即ArrayListMultimap被实现为一个数组并且LinkedListMultimap是作为 LinkedList 实现的吗？另外，它们的性能有何不同？我知道我问了很多，但我真的不知道还能在哪里找到答案。

它在文档中......和代码中。基本上除了你已经看到的一个区别（List实现选择），他们也使用不同的Map执行。所以：

• ArrayListMultimap uses HashMap对于地图和ArrayListcor 集合，这意味着此类方法的迭代顺序为entries(), asMap().keySet() or asMap.entrySet()未定义。这是简单明了的实现ListMultimap你应该从这个开始。

• LinkedListMultimap uses LinkedList用于集合和专门的数据结构（自定义链表）来维护上述方法的迭代顺序：

  使用包含所有键值的链表来维护顺序 对。此外，一系列不相交的链表 使用“siblings”，每个都包含特定键的值 实施ValueForKey迭代器在恒定的时间内。

  此外，它使用很少的其他结构来维护类似“链表”的行为：

  private transient Node<K, V> head; // the head for all keys
  private transient Node<K, V> tail; // the tail for all keys
  private transient Multiset<K> keyCount; // the number of values for each key
  private transient Map<K, Node<K, V>> keyToKeyHead; // the head for a given key
  private transient Map<K, Node<K, V>> keyToKeyTail; // the tail for a given key
  

此外，内存占用也暗示了这些中使用的支持集合。Multimap实施-看这个比较 https://github.com/DimitrisAndreou/memory-measurer/blob/master/ElementCostInDataStructures.txt（可能不是 100% 最新）。

就我个人而言，当我需要高效、可变的时候ListMultimap对于定义的键迭代顺序，我使用“自定义”ListMultimap（创建于MultimapBuilder http://docs.guava-libraries.googlecode.com/git-history/v18.0/javadoc/com/google/common/collect/MultimapBuilder.html，自 v16.0 起就在 Guava 中）：

ListMultimap<String, Integer> treeListMultimap = 
    MultimapBuilder.linkedHashKeys().arrayListValues().build();

v16.0之前创建自定义Multimaps 更详细（使用Multimaps.newListMultimap http://docs.guava-libraries.googlecode.com/git/javadoc/com/google/common/collect/Multimaps.html#newListMultimap%28java.util.Map,%20com.google.common.base.Supplier%29):

/**
 * Creates {@link ListMultimap} preserving insertion order of keys and values 
 * (it's backed by {@link LinkedHashMap} and {@link ArrayList}).
 */
public static <K, V> ListMultimap<K, V> newLinkedArrayListMultimap() {
  return Multimaps.newListMultimap(
      Maps.<K, Collection<V>>newLinkedHashMap(),
      new Supplier<List<V>>() {
          @Override
          public List<V> get() {
            return Lists.newArrayList();
          }
      });
}