Czym różni się ArrayListMultimap od LinkedListMultimap?

Question

Tak, właśnie czytałem javadoc dla ArrayListMultimap i LinkedListMultimap, aby zrozumieć, jak z nich korzystać i dowiedziałem się, że oba obsługują duplikaty pary klucz-wartość (i przez to mam na myśli te same klucze, różne wartości - jeśli rozumiem poprawnie, popraw mnie, jeśli się mylę). Jednak nie rozumiem różnicy między nimi. Obie są używane do przechowywania duplikatów par klucz-wartość. Czy jedyną częścią, którą różnią się jest ich implementacja, to znaczy, że ArrayListMultimap jest zaimplementowany jako Array i LinkedListMultimap jest zaimplementowany jako LinkedList? Ponadto, w jaki sposób różnią się one wydajnością? Wiem, że dużo zadaję, ale tak naprawdę nie wiem, gdzie jeszcze znaleźć odpowiedzi na to.

Answer 1

Jest w dokumentach ... i w kodzie. Zasadniczo poza jedną różnicą, którą już zauważyłeś (List wybór implementacji), używają one także innej implementacji Map. Więc:

• ArrayListMultimap wykorzystuje HashMap na mapie i ArrayList zbiórki cor, co oznacza, że ​​kolejność iteracji takich metod jak entries(), asMap().keySet() lub asMap.entrySet() jest niezdefiniowany. Jest to prosta i prosta implementacja ListMultimap i powinieneś zacząć od tego.

• LinkedListMultimap wykorzystuje LinkedList zbierania i specjalistycznej struktury danych (na zamówienie listę) do utrzymywania iteracji kolejności metodami opisanymi powyżej

  Zamówienie jest utrzymywana za pomocą umieszczonego listę wszystkich KLUCZ WARTOŚĆ par. Ponadto szereg rozłącznych połączonych list rodzeństwa " ", z których każda zawiera wartości dla określonego klucza, jest używane do realizacji ValueForKeyIterator w stałym czasie.

  Dodatkowo wykorzystuje kilka innych struktur w celu utrzymania „połączonej listy” -jak zachowanie:

  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 
  

Ponadto, zużycie pamięci jest implikacją kolekcji podkładów stosowanych w tych Multimap wdrożeń - see this comparision (może nie być w 100% aktualne).

---

Osobiście, kiedy muszę wydajny, zmienny ListMultimap z określonej kolejności iteracji kluczy używam "zwyczaj" ListMultimap (utworzony z MultimapBuilder, który jest w Guava od v16.0):

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

---

Przed v16.0 tworzenia własnych Multimap s bardziej opisowy (stosując 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(); 
      } 
     }); 
}