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}