How is ArrayListMultimap different from LinkedListMultimap?

Question

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.

Answer 1

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 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:

  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
  

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

---

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

---

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