ArrayListMultimap与LinkedListMultimap有何不同? [英] How is ArrayListMultimap different from LinkedListMultimap?

问题描述

因此，我只是在阅读ArrayListMultimap和LinkedListMultimap的javadoc，以了解如何使用它们，然后我才知道它们都支持重复的键值对(并且我的意思是相同的键，不同的键值-如果我理解正确，请输入正确的答案.但是，我不了解它们之间的区别.两者都用于存储重复的键值对.它们唯一的不同之处在于它们的实现方式，即ArrayListMultimap被实现为数组，而LinkedListMultimap被实现为LinkedList吗?另外，它们在性能上有何不同?我知道我要问很多，但我真的不知道该从哪里找到答案.

So, I was just reading the javadoc for ArrayListMultimap and LinkedListMultimap so 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 ArrayListMultimap is implemented as an Array and LinkedListMultimap is 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.

推荐答案

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

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

• ArrayListMultimap使用HashMap进行地图和ArrayList cor收集，这意味着entries()，asMap().keySet()或asMap.entrySet()之类的方法的迭代顺序未定义.这是ListMultimap的简单明了的实现，您应该从此开始.

• LinkedListMultimap使用LinkedList进行收集和专用数据结构(自定义链接列表)来维护上述方法的迭代顺序:

• ArrayListMultimap uses HashMap for map and ArrayList cor 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 ListMultimap and you should start with this one.

• LinkedListMultimap uses LinkedList for collection and specialized data structure (custom linked list) to maintain iteration order of methods mentioned above:

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

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 ValueForKeyIterator in 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

此外，内存占用量是这些Multimap实现中使用的备份集合的含义-

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

个人而言，当我需要具有定义的键迭代顺序的高效，可变的ListMultimap时，我会使用自定义" ListMultimap(由

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

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

---

在v16.0之前，创建自定义Multimap更为冗长(使用

---

Before v16.0 creating custom Multimaps was more verbose (using 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();
          }
      });
}

这篇关于ArrayListMultimap与LinkedListMultimap有何不同?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！