Как ArrayListMultimap отличается от LinkedListMultimap?

Question

Итак, я просто читал javadoc для ArrayListMultimap и LinkedListMultimap, чтобы понять, как их использовать, и я узнал, что обе поддерживают двойную пару ключ-значение (и тем самым я имею в виду те же ключи, разные значения - если я понимаю правильно. Пожалуйста, поправьте меня, если я ошибаюсь). Однако я не понимаю разницы между ними. Оба используются для хранения повторяющихся пар значений ключа. Единственная их отличия заключается в их реализации. ArrayListMultimap реализован как массив и LinkedListMultimap реализован как LinkedList? Кроме того, как они отличаются по производительности? Я знаю, что много спрашиваю, но я не знаю, где еще найти ответы на это.

Answer 1

Это в документах ... и в коде. В основном помимо одной разницы, которую вы уже видели (List выбор реализации), они также используют другую реализацию Map. Итак:

• ArrayListMultimap использует HashMap для отображения и ArrayList кор сбора, а это значит, что итерационный порядок таких методов, как 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 реализаций - see this comparision (не может быть на 100% до настоящего времени).

---

Лично я, когда нужно эффективно, изменяемые ListMultimap с определенной итерации порядка ключей, я использую "обычай" ListMultimap (созданный с MultimapBuilder, который находится в гуавы, так как v16.0):

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

---

Перед v16.0 создания пользовательских Multimap сек был более многословен (с использованием 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(); 
      } 
     }); 
}