Wie unterscheidet sich ArrayListMultimap von LinkedListMultimap?

Question

Also, ich habe gerade die Javadoc für ArrayListMultimap und LinkedListMultimap gelesen, um zu verstehen, wie man sie verwendet und ich wusste, dass beide doppelte Schlüssel-Wert-Paar unterstützen (und damit meine ich gleiche Schlüssel, andere Werte - wenn ich verstehe richtig. Bitte korrigieren Sie mich, wenn ich falsch liege). Ich verstehe jedoch nicht den Unterschied zwischen ihnen. Beide werden zum Speichern von doppelten Schlüsselwertpaaren verwendet. Ist der einzige Teil, den sie unterscheiden, ihre Implementierung, d. H. ArrayListMultimap ist als Array implementiert und LinkedListMultimap ist als LinkedList implementiert? Wie unterscheiden sie sich in der Leistung? Ich weiß, ich frage viel, aber ich weiß nicht wirklich, wo ich sonst Antworten finden könnte.

Answer 1

Es ist in der Dokumentation ... und im Code. Abgesehen von einem Unterschied, den Sie bereits gesehen haben (List Implementierungswahl), verwenden sie auch eine andere Map Implementierung. So:

• ArrayListMultimap verwendet HashMap für Karte und ArrayList cor Sammlung, die diese Iterationsreihenfolge solchen Verfahrens bedeutet wie entries(), asMap().keySet()asMap.entrySet() oder undefiniert ist. Es ist schlicht und einfach Umsetzung von ListMultimap und Sie sollten mit diesem beginnen.

• LinkedListMultimap verwendet LinkedList für die Sammlung und spezialisierte Datenstruktur (custom verketteten Liste) Iteration der Reihenfolge der oben genannten Verfahren zu erhalten:

  Sortieren einer verketteten Liste gehalten wird, unter Verwendung aller Schlüssel-Wert-Paaren enthält. Zusätzlich wird eine Reihe von getrennten Listen von "Geschwister", die jeweils die Werte für einen bestimmten Schlüssel enthalten, verwendet, um ValueForKeyIterator in konstanter Zeit zu implementieren.

  Zusätzlich verwendet es nur wenige andere Strukturen „verketteten Liste“ -ähnlichen Regeln verhalten:

  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 
  

Auch Speicherbedarf ist eine Implikation der Träger in diesen Multimap Implementierungen verwendet Sammlungen - see this comparision (möglicherweise nicht 100% aktuell).

---

Persönlich, wenn ich brauche effizient, wandelbar ListMultimap mit definierten Iterationsreihenfolge von Schlüsseln, verwende ich "custom" ListMultimap (erstellt mit MultimapBuilder, die seit V16.0 in Guava ist):

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

---

Bevor V16.0 das Erstellen von benutzerdefinierten Multimap s war ausführlicher (mit 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(); 
      } 
     }); 
}