ArrayListMultimap与LinkedListMultimap有何不同？

Question

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

Answer 1

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

• 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
  

此外,内存占用是这些Multimap实现中使用的后备集合的含义- 请参阅此比较(可能不是100%最新).

就个人而言,当我需要有效的,可变ListMultimap的定义迭代顺序的键,我使用"自定义" ListMultimap(创建时MultimapBuilder,自从v16.0以来在Guava中):

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

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