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