001/*
002 * Copyright (C) 2007 The Guava Authors
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 * http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 */
016
017package com.google.common.collect;
018
019import static com.google.common.base.Preconditions.checkNotNull;
020import static com.google.common.base.Preconditions.checkState;
021import static com.google.common.collect.CollectPreconditions.checkNonnegative;
022import static java.util.Objects.requireNonNull;
023
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.annotations.VisibleForTesting;
027import com.google.common.base.Objects;
028import com.google.errorprone.annotations.CanIgnoreReturnValue;
029import com.google.j2objc.annotations.WeakOuter;
030import java.io.IOException;
031import java.io.ObjectInputStream;
032import java.io.ObjectOutputStream;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.ConcurrentModificationException;
036import java.util.Iterator;
037import java.util.Map;
038import java.util.Map.Entry;
039import java.util.NoSuchElementException;
040import java.util.Set;
041import java.util.Spliterator;
042import java.util.Spliterators;
043import java.util.function.Consumer;
044import javax.annotation.CheckForNull;
045import org.checkerframework.checker.nullness.qual.Nullable;
046
047/**
048 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that
049 * returns collections whose iterators follow the ordering in which the data was added to the
050 * multimap.
051 *
052 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through
053 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code
054 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the
055 * order they were added. The collections generated by {@code entries} and {@code values} iterate
056 * across the key-value mappings in the order they were added to the multimap.
057 *
058 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and
059 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or
060 * removing mappings does not affect the key iteration order. However, if you remove all values
061 * associated with a key and then add the key back to the multimap, that key will come last in the
062 * key iteration order.
063 *
064 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an
065 * existing key-value pair has no effect.
066 *
067 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned
068 * views are modifiable.
069 *
070 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent
071 * read operations will work correctly. To allow concurrent update operations, wrap your multimap
072 * with a call to {@link Multimaps#synchronizedSetMultimap}.
073 *
074 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap}
075 * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will
076 * result.
077 *
078 * <p>See the Guava User Guide article on <a href=
079 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code Multimap}</a>.
080 *
081 * @author Jared Levy
082 * @author Louis Wasserman
083 * @since 2.0
084 */
085@GwtCompatible(serializable = true, emulated = true)
086@ElementTypesAreNonnullByDefault
087public final class LinkedHashMultimap<K extends @Nullable Object, V extends @Nullable Object>
088    extends LinkedHashMultimapGwtSerializationDependencies<K, V> {
089
090  /** Creates a new, empty {@code LinkedHashMultimap} with the default initial capacities. */
091  public static <K extends @Nullable Object, V extends @Nullable Object>
092      LinkedHashMultimap<K, V> create() {
093    return new LinkedHashMultimap<>(DEFAULT_KEY_CAPACITY, DEFAULT_VALUE_SET_CAPACITY);
094  }
095
096  /**
097   * Constructs an empty {@code LinkedHashMultimap} with enough capacity to hold the specified
098   * numbers of keys and values without rehashing.
099   *
100   * @param expectedKeys the expected number of distinct keys
101   * @param expectedValuesPerKey the expected average number of values per key
102   * @throws IllegalArgumentException if {@code expectedKeys} or {@code expectedValuesPerKey} is
103   *     negative
104   */
105  public static <K extends @Nullable Object, V extends @Nullable Object>
106      LinkedHashMultimap<K, V> create(int expectedKeys, int expectedValuesPerKey) {
107    return new LinkedHashMultimap<>(
108        Maps.capacity(expectedKeys), Maps.capacity(expectedValuesPerKey));
109  }
110
111  /**
112   * Constructs a {@code LinkedHashMultimap} with the same mappings as the specified multimap. If a
113   * key-value mapping appears multiple times in the input multimap, it only appears once in the
114   * constructed multimap. The new multimap has the same {@link Multimap#entries()} iteration order
115   * as the input multimap, except for excluding duplicate mappings.
116   *
117   * @param multimap the multimap whose contents are copied to this multimap
118   */
119  public static <K extends @Nullable Object, V extends @Nullable Object>
120      LinkedHashMultimap<K, V> create(Multimap<? extends K, ? extends V> multimap) {
121    LinkedHashMultimap<K, V> result = create(multimap.keySet().size(), DEFAULT_VALUE_SET_CAPACITY);
122    result.putAll(multimap);
123    return result;
124  }
125
126  private interface ValueSetLink<K extends @Nullable Object, V extends @Nullable Object> {
127    ValueSetLink<K, V> getPredecessorInValueSet();
128
129    ValueSetLink<K, V> getSuccessorInValueSet();
130
131    void setPredecessorInValueSet(ValueSetLink<K, V> entry);
132
133    void setSuccessorInValueSet(ValueSetLink<K, V> entry);
134  }
135
136  private static <K extends @Nullable Object, V extends @Nullable Object> void succeedsInValueSet(
137      ValueSetLink<K, V> pred, ValueSetLink<K, V> succ) {
138    pred.setSuccessorInValueSet(succ);
139    succ.setPredecessorInValueSet(pred);
140  }
141
142  private static <K extends @Nullable Object, V extends @Nullable Object> void succeedsInMultimap(
143      ValueEntry<K, V> pred, ValueEntry<K, V> succ) {
144    pred.setSuccessorInMultimap(succ);
145    succ.setPredecessorInMultimap(pred);
146  }
147
148  private static <K extends @Nullable Object, V extends @Nullable Object> void deleteFromValueSet(
149      ValueSetLink<K, V> entry) {
150    succeedsInValueSet(entry.getPredecessorInValueSet(), entry.getSuccessorInValueSet());
151  }
152
153  private static <K extends @Nullable Object, V extends @Nullable Object> void deleteFromMultimap(
154      ValueEntry<K, V> entry) {
155    succeedsInMultimap(entry.getPredecessorInMultimap(), entry.getSuccessorInMultimap());
156  }
157
158  /**
159   * LinkedHashMultimap entries are in no less than three coexisting linked lists: a bucket in the
160   * hash table for a {@code Set<V>} associated with a key, the linked list of insertion-ordered
161   * entries in that {@code Set<V>}, and the linked list of entries in the LinkedHashMultimap as a
162   * whole.
163   */
164  @VisibleForTesting
165  static final class ValueEntry<K extends @Nullable Object, V extends @Nullable Object>
166      extends ImmutableEntry<K, V> implements ValueSetLink<K, V> {
167    final int smearedValueHash;
168
169    @CheckForNull ValueEntry<K, V> nextInValueBucket;
170    /*
171     * The *InValueSet and *InMultimap fields below are null after construction, but we almost
172     * always call succeedsIn*() to initialize them immediately thereafter.
173     *
174     * The exception is the *InValueSet fields of multimapHeaderEntry, which are never set. (That
175     * works out fine as long as we continue to be careful not to try delete them or iterate past
176     * them.)
177     *
178     * We could consider "lying" and omitting @CheckNotNull from all these fields. Normally, I'm not
179     * a fan of that: What if we someday implement (presumably to be enabled during tests only)
180     * bytecode rewriting that checks for any null value that passes through an API with a
181     * known-non-null type? But that particular problem might not arise here, since we're not
182     * actually reading from the fields in any case in which they might be null (as proven by the
183     * requireNonNull checks below). Plus, we're *already* lying here, since newHeader passes a null
184     * key and value, which we pass to the superconstructor, even though the key and value type for
185     * a given entry might not include null. The right fix for the header problems is probably to
186     * define a separate MultimapLink interface with a separate "header" implementation, which
187     * hopefully could avoid implementing Entry or ValueSetLink at all. (But note that that approach
188     * requires us to define extra classes -- unfortunate under Android.) *Then* we could consider
189     * lying about the fields below on the grounds that we always initialize them just after the
190     * constructor -- an example of the kind of lying that our hypotheticaly bytecode rewriter would
191     * already have to deal with, thanks to DI frameworks that perform field and method injection,
192     * frameworks like Android that define post-construct hooks like Activity.onCreate, etc.
193     */
194
195    @CheckForNull ValueSetLink<K, V> predecessorInValueSet;
196    @CheckForNull ValueSetLink<K, V> successorInValueSet;
197
198    @CheckForNull ValueEntry<K, V> predecessorInMultimap;
199    @CheckForNull ValueEntry<K, V> successorInMultimap;
200
201    ValueEntry(
202        @ParametricNullness K key,
203        @ParametricNullness V value,
204        int smearedValueHash,
205        @CheckForNull ValueEntry<K, V> nextInValueBucket) {
206      super(key, value);
207      this.smearedValueHash = smearedValueHash;
208      this.nextInValueBucket = nextInValueBucket;
209    }
210
211    @SuppressWarnings("nullness") // see the comment on the class fields, especially about newHeader
212    static <K extends @Nullable Object, V extends @Nullable Object> ValueEntry<K, V> newHeader() {
213      return new ValueEntry<>(null, null, 0, null);
214    }
215
216    boolean matchesValue(@CheckForNull Object v, int smearedVHash) {
217      return smearedValueHash == smearedVHash && Objects.equal(getValue(), v);
218    }
219
220    @Override
221    public ValueSetLink<K, V> getPredecessorInValueSet() {
222      return requireNonNull(predecessorInValueSet); // see the comment on the class fields
223    }
224
225    @Override
226    public ValueSetLink<K, V> getSuccessorInValueSet() {
227      return requireNonNull(successorInValueSet); // see the comment on the class fields
228    }
229
230    @Override
231    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
232      predecessorInValueSet = entry;
233    }
234
235    @Override
236    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
237      successorInValueSet = entry;
238    }
239
240    public ValueEntry<K, V> getPredecessorInMultimap() {
241      return requireNonNull(predecessorInMultimap); // see the comment on the class fields
242    }
243
244    public ValueEntry<K, V> getSuccessorInMultimap() {
245      return requireNonNull(successorInMultimap); // see the comment on the class fields
246    }
247
248    public void setSuccessorInMultimap(ValueEntry<K, V> multimapSuccessor) {
249      this.successorInMultimap = multimapSuccessor;
250    }
251
252    public void setPredecessorInMultimap(ValueEntry<K, V> multimapPredecessor) {
253      this.predecessorInMultimap = multimapPredecessor;
254    }
255  }
256
257  private static final int DEFAULT_KEY_CAPACITY = 16;
258  private static final int DEFAULT_VALUE_SET_CAPACITY = 2;
259  @VisibleForTesting static final double VALUE_SET_LOAD_FACTOR = 1.0;
260
261  @VisibleForTesting transient int valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
262  private transient ValueEntry<K, V> multimapHeaderEntry;
263
264  private LinkedHashMultimap(int keyCapacity, int valueSetCapacity) {
265    super(Platform.<K, Collection<V>>newLinkedHashMapWithExpectedSize(keyCapacity));
266    checkNonnegative(valueSetCapacity, "expectedValuesPerKey");
267
268    this.valueSetCapacity = valueSetCapacity;
269    this.multimapHeaderEntry = ValueEntry.newHeader();
270    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
271  }
272
273  /**
274   * {@inheritDoc}
275   *
276   * <p>Creates an empty {@code LinkedHashSet} for a collection of values for one key.
277   *
278   * @return a new {@code LinkedHashSet} containing a collection of values for one key
279   */
280  @Override
281  Set<V> createCollection() {
282    return Platform.newLinkedHashSetWithExpectedSize(valueSetCapacity);
283  }
284
285  /**
286   * {@inheritDoc}
287   *
288   * <p>Creates a decorated insertion-ordered set that also keeps track of the order in which
289   * key-value pairs are added to the multimap.
290   *
291   * @param key key to associate with values in the collection
292   * @return a new decorated set containing a collection of values for one key
293   */
294  @Override
295  Collection<V> createCollection(@ParametricNullness K key) {
296    return new ValueSet(key, valueSetCapacity);
297  }
298
299  /**
300   * {@inheritDoc}
301   *
302   * <p>If {@code values} is not empty and the multimap already contains a mapping for {@code key},
303   * the {@code keySet()} ordering is unchanged. However, the provided values always come last in
304   * the {@link #entries()} and {@link #values()} iteration orderings.
305   */
306  @CanIgnoreReturnValue
307  @Override
308  public Set<V> replaceValues(@ParametricNullness K key, Iterable<? extends V> values) {
309    return super.replaceValues(key, values);
310  }
311
312  /**
313   * Returns a set of all key-value pairs. Changes to the returned set will update the underlying
314   * multimap, and vice versa. The entries set does not support the {@code add} or {@code addAll}
315   * operations.
316   *
317   * <p>The iterator generated by the returned set traverses the entries in the order they were
318   * added to the multimap.
319   *
320   * <p>Each entry is an immutable snapshot of a key-value mapping in the multimap, taken at the
321   * time the entry is returned by a method call to the collection or its iterator.
322   */
323  @Override
324  public Set<Entry<K, V>> entries() {
325    return super.entries();
326  }
327
328  /**
329   * Returns a view collection of all <i>distinct</i> keys contained in this multimap. Note that the
330   * key set contains a key if and only if this multimap maps that key to at least one value.
331   *
332   * <p>The iterator generated by the returned set traverses the keys in the order they were first
333   * added to the multimap.
334   *
335   * <p>Changes to the returned set will update the underlying multimap, and vice versa. However,
336   * <i>adding</i> to the returned set is not possible.
337   */
338  @Override
339  public Set<K> keySet() {
340    return super.keySet();
341  }
342
343  /**
344   * Returns a collection of all values in the multimap. Changes to the returned collection will
345   * update the underlying multimap, and vice versa.
346   *
347   * <p>The iterator generated by the returned collection traverses the values in the order they
348   * were added to the multimap.
349   */
350  @Override
351  public Collection<V> values() {
352    return super.values();
353  }
354
355  @VisibleForTesting
356  @WeakOuter
357  final class ValueSet extends Sets.ImprovedAbstractSet<V> implements ValueSetLink<K, V> {
358    /*
359     * We currently use a fixed load factor of 1.0, a bit higher than normal to reduce memory
360     * consumption.
361     */
362
363    @ParametricNullness private final K key;
364    @VisibleForTesting @Nullable ValueEntry<K, V>[] hashTable;
365    private int size = 0;
366    private int modCount = 0;
367
368    // We use the set object itself as the end of the linked list, avoiding an unnecessary
369    // entry object per key.
370    private ValueSetLink<K, V> firstEntry;
371    private ValueSetLink<K, V> lastEntry;
372
373    ValueSet(@ParametricNullness K key, int expectedValues) {
374      this.key = key;
375      this.firstEntry = this;
376      this.lastEntry = this;
377      // Round expected values up to a power of 2 to get the table size.
378      int tableSize = Hashing.closedTableSize(expectedValues, VALUE_SET_LOAD_FACTOR);
379
380      @SuppressWarnings({"rawtypes", "unchecked"})
381      @Nullable
382      ValueEntry<K, V>[] hashTable = new @Nullable ValueEntry[tableSize];
383      this.hashTable = hashTable;
384    }
385
386    private int mask() {
387      return hashTable.length - 1;
388    }
389
390    @Override
391    public ValueSetLink<K, V> getPredecessorInValueSet() {
392      return lastEntry;
393    }
394
395    @Override
396    public ValueSetLink<K, V> getSuccessorInValueSet() {
397      return firstEntry;
398    }
399
400    @Override
401    public void setPredecessorInValueSet(ValueSetLink<K, V> entry) {
402      lastEntry = entry;
403    }
404
405    @Override
406    public void setSuccessorInValueSet(ValueSetLink<K, V> entry) {
407      firstEntry = entry;
408    }
409
410    @Override
411    public Iterator<V> iterator() {
412      return new Iterator<V>() {
413        ValueSetLink<K, V> nextEntry = firstEntry;
414        @CheckForNull ValueEntry<K, V> toRemove;
415        int expectedModCount = modCount;
416
417        private void checkForComodification() {
418          if (modCount != expectedModCount) {
419            throw new ConcurrentModificationException();
420          }
421        }
422
423        @Override
424        public boolean hasNext() {
425          checkForComodification();
426          return nextEntry != ValueSet.this;
427        }
428
429        @Override
430        @ParametricNullness
431        public V next() {
432          if (!hasNext()) {
433            throw new NoSuchElementException();
434          }
435          ValueEntry<K, V> entry = (ValueEntry<K, V>) nextEntry;
436          V result = entry.getValue();
437          toRemove = entry;
438          nextEntry = entry.getSuccessorInValueSet();
439          return result;
440        }
441
442        @Override
443        public void remove() {
444          checkForComodification();
445          checkState(toRemove != null, "no calls to next() since the last call to remove()");
446          ValueSet.this.remove(toRemove.getValue());
447          expectedModCount = modCount;
448          toRemove = null;
449        }
450      };
451    }
452
453    @Override
454    public void forEach(Consumer<? super V> action) {
455      checkNotNull(action);
456      for (ValueSetLink<K, V> entry = firstEntry;
457          entry != ValueSet.this;
458          entry = entry.getSuccessorInValueSet()) {
459        action.accept(((ValueEntry<K, V>) entry).getValue());
460      }
461    }
462
463    @Override
464    public int size() {
465      return size;
466    }
467
468    @Override
469    public boolean contains(@CheckForNull Object o) {
470      int smearedHash = Hashing.smearedHash(o);
471      for (ValueEntry<K, V> entry = hashTable[smearedHash & mask()];
472          entry != null;
473          entry = entry.nextInValueBucket) {
474        if (entry.matchesValue(o, smearedHash)) {
475          return true;
476        }
477      }
478      return false;
479    }
480
481    @Override
482    public boolean add(@ParametricNullness V value) {
483      int smearedHash = Hashing.smearedHash(value);
484      int bucket = smearedHash & mask();
485      ValueEntry<K, V> rowHead = hashTable[bucket];
486      for (ValueEntry<K, V> entry = rowHead; entry != null; entry = entry.nextInValueBucket) {
487        if (entry.matchesValue(value, smearedHash)) {
488          return false;
489        }
490      }
491
492      ValueEntry<K, V> newEntry = new ValueEntry<>(key, value, smearedHash, rowHead);
493      succeedsInValueSet(lastEntry, newEntry);
494      succeedsInValueSet(newEntry, this);
495      succeedsInMultimap(multimapHeaderEntry.getPredecessorInMultimap(), newEntry);
496      succeedsInMultimap(newEntry, multimapHeaderEntry);
497      hashTable[bucket] = newEntry;
498      size++;
499      modCount++;
500      rehashIfNecessary();
501      return true;
502    }
503
504    private void rehashIfNecessary() {
505      if (Hashing.needsResizing(size, hashTable.length, VALUE_SET_LOAD_FACTOR)) {
506        @SuppressWarnings("unchecked")
507        ValueEntry<K, V>[] hashTable = new ValueEntry[this.hashTable.length * 2];
508        this.hashTable = hashTable;
509        int mask = hashTable.length - 1;
510        for (ValueSetLink<K, V> entry = firstEntry;
511            entry != this;
512            entry = entry.getSuccessorInValueSet()) {
513          ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
514          int bucket = valueEntry.smearedValueHash & mask;
515          valueEntry.nextInValueBucket = hashTable[bucket];
516          hashTable[bucket] = valueEntry;
517        }
518      }
519    }
520
521    @CanIgnoreReturnValue
522    @Override
523    public boolean remove(@CheckForNull Object o) {
524      int smearedHash = Hashing.smearedHash(o);
525      int bucket = smearedHash & mask();
526      ValueEntry<K, V> prev = null;
527      for (ValueEntry<K, V> entry = hashTable[bucket];
528          entry != null;
529          prev = entry, entry = entry.nextInValueBucket) {
530        if (entry.matchesValue(o, smearedHash)) {
531          if (prev == null) {
532            // first entry in the bucket
533            hashTable[bucket] = entry.nextInValueBucket;
534          } else {
535            prev.nextInValueBucket = entry.nextInValueBucket;
536          }
537          deleteFromValueSet(entry);
538          deleteFromMultimap(entry);
539          size--;
540          modCount++;
541          return true;
542        }
543      }
544      return false;
545    }
546
547    @Override
548    public void clear() {
549      Arrays.fill(hashTable, null);
550      size = 0;
551      for (ValueSetLink<K, V> entry = firstEntry;
552          entry != this;
553          entry = entry.getSuccessorInValueSet()) {
554        ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry;
555        deleteFromMultimap(valueEntry);
556      }
557      succeedsInValueSet(this, this);
558      modCount++;
559    }
560  }
561
562  @Override
563  Iterator<Entry<K, V>> entryIterator() {
564    return new Iterator<Entry<K, V>>() {
565      ValueEntry<K, V> nextEntry = multimapHeaderEntry.getSuccessorInMultimap();
566      @CheckForNull ValueEntry<K, V> toRemove;
567
568      @Override
569      public boolean hasNext() {
570        return nextEntry != multimapHeaderEntry;
571      }
572
573      @Override
574      public Entry<K, V> next() {
575        if (!hasNext()) {
576          throw new NoSuchElementException();
577        }
578        ValueEntry<K, V> result = nextEntry;
579        toRemove = result;
580        nextEntry = nextEntry.getSuccessorInMultimap();
581        return result;
582      }
583
584      @Override
585      public void remove() {
586        checkState(toRemove != null, "no calls to next() since the last call to remove()");
587        LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue());
588        toRemove = null;
589      }
590    };
591  }
592
593  @Override
594  Spliterator<Entry<K, V>> entrySpliterator() {
595    return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED);
596  }
597
598  @Override
599  Iterator<V> valueIterator() {
600    return Maps.valueIterator(entryIterator());
601  }
602
603  @Override
604  Spliterator<V> valueSpliterator() {
605    return CollectSpliterators.map(entrySpliterator(), Entry::getValue);
606  }
607
608  @Override
609  public void clear() {
610    super.clear();
611    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
612  }
613
614  /**
615   * @serialData the expected values per key, the number of distinct keys, the number of entries,
616   *     and the entries in order
617   */
618  @GwtIncompatible // java.io.ObjectOutputStream
619  private void writeObject(ObjectOutputStream stream) throws IOException {
620    stream.defaultWriteObject();
621    stream.writeInt(keySet().size());
622    for (K key : keySet()) {
623      stream.writeObject(key);
624    }
625    stream.writeInt(size());
626    for (Entry<K, V> entry : entries()) {
627      stream.writeObject(entry.getKey());
628      stream.writeObject(entry.getValue());
629    }
630  }
631
632  @GwtIncompatible // java.io.ObjectInputStream
633  private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
634    stream.defaultReadObject();
635    multimapHeaderEntry = ValueEntry.newHeader();
636    succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry);
637    valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY;
638    int distinctKeys = stream.readInt();
639    Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12);
640    for (int i = 0; i < distinctKeys; i++) {
641      @SuppressWarnings("unchecked")
642      K key = (K) stream.readObject();
643      map.put(key, createCollection(key));
644    }
645    int entries = stream.readInt();
646    for (int i = 0; i < entries; i++) {
647      @SuppressWarnings("unchecked")
648      K key = (K) stream.readObject();
649      @SuppressWarnings("unchecked")
650      V value = (V) stream.readObject();
651      /*
652       * requireNonNull is safe for a properly serialized multimap: We've already inserted a
653       * collection for each key that we expect.
654       */
655      requireNonNull(map.get(key)).add(value);
656    }
657    setMap(map);
658  }
659
660  @GwtIncompatible // java serialization not supported
661  private static final long serialVersionUID = 1;
662}