java ArrayListMultimap 与 LinkedListMultimap 有何不同？

How is ArrayListMultimap different from LinkedListMultimap?

提问by TheRookierLearner

So, I was just reading the javadoc for ArrayListMultimapand LinkedListMultimapso as to understand how to use them and I came to know that both support duplicate key-value pair (and by that I mean same keys, different values - if I understand correctly. Please correct me if I am wrong). However, I don't understand the difference between them. Both are used to store duplicate key value pairs. Is the only part they differ is in their implementation i.e ArrayListMultimapis implemented as an Array and LinkedListMultimapis implemented as a LinkedList? Also, how do they differ in performance? I know I am asking a lot but I don't really know where else to find answers for this.

所以，我只是阅读的JavadocArrayListMultimap和LinkedListMultimap以了解如何使用他们，我才知道，都支持重复的键值对（和我的意思是相同的键，不同的价值观-如果我理解正确的话，请正确如果我错了，我）。但是，我不明白它们之间的区别。两者都用于存储重复的键值对。它们唯一不同的部分是它们的实现，即ArrayListMultimap作为数组LinkedListMultimap实现并作为 LinkedList 实现？另外，它们在性能上有何不同？我知道我问了很多，但我真的不知道还有什么地方可以找到答案。

回答by Xaerxess

It's in the docs... and in the code. Basically besides one difference you've already seen (Listimplementation choice), they also use a different Mapimplementation. So:

它在文档中......和代码中。基本上，除了您已经看到的一个差异（List实现选择）之外，它们还使用不同的Map实现。所以：

• ArrayListMultimapuses HashMapfor map and ArrayListcor collection, which means that iteration order of such methods as entries(), asMap().keySet()or asMap.entrySet()is undefined. It's plain and simple implementation of ListMultimapand you should start with this one.

• LinkedListMultimapuses LinkedListfor collection and specialized data structure (custom linked list) to maintain iteration order of methods mentioned above:

  Order is maintained using a linked list containing all key-value pairs. In addition, a series of disjoint linked lists of "siblings", each containing the values for a specific key, is used to implement ValueForKeyIteratorin constant time.

  Additionally it uses few other structures to maintain "linked list"-like behavior:

  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
  

• ArrayListMultimap用途HashMap在地图和ArrayListCOR收集，这意味着，这样的方法作为迭代顺序entries()，asMap().keySet()或者asMap.entrySet()是未定义的。这是一个简单明了的实现，ListMultimap你应该从这个开始。

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

  使用包含所有键值对的链表维护订单。此外，一系列不相交的“兄弟”链表，每个包含特定键的值，用于在恒定时间内实现ValueForKeyIterator。

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

  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
  

Also, memory footprint is a implication of backing collections used in these Multimapimplementations - see this comparision(may not be 100% up to date).

此外，内存占用是这些Multimap实现中使用的后备集合的暗示-请参阅此比较（可能不是 100% 最新）。

---

---

Personally, when I need efficient, mutable ListMultimapwith defined iteration order of keys, I use "custom" ListMultimap(created with MultimapBuilder, which is in Guava since v16.0):

就我个人而言，当我需要有效的、可变的ListMultimap并具有定义的键迭代顺序时，我使用“自定义” ListMultimap（使用创建MultimapBuilder，自 v16.0 起在 Guava 中）：

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

---

---

Before v16.0 creating custom Multimaps was more verbose (using Multimaps.newListMultimap):

在 v16.0 创建自定义Multimaps之前更详细（使用Multimaps.newListMultimap）：

/**
 * 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();
          }
      });
}