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.J2ktIncompatible; 027import com.google.common.annotations.VisibleForTesting; 028import com.google.common.base.Objects; 029import com.google.errorprone.annotations.CanIgnoreReturnValue; 030import com.google.j2objc.annotations.WeakOuter; 031import java.io.IOException; 032import java.io.ObjectInputStream; 033import java.io.ObjectOutputStream; 034import java.util.Arrays; 035import java.util.Collection; 036import java.util.ConcurrentModificationException; 037import java.util.Iterator; 038import java.util.Map; 039import java.util.Map.Entry; 040import java.util.NoSuchElementException; 041import java.util.Set; 042import java.util.Spliterator; 043import java.util.Spliterators; 044import java.util.function.Consumer; 045import javax.annotation.CheckForNull; 046import org.checkerframework.checker.nullness.qual.Nullable; 047 048/** 049 * Implementation of {@code Multimap} that does not allow duplicate key-value entries and that 050 * returns collections whose iterators follow the ordering in which the data was added to the 051 * multimap. 052 * 053 * <p>The collections returned by {@code keySet}, {@code keys}, and {@code asMap} iterate through 054 * the keys in the order they were first added to the multimap. Similarly, {@code get}, {@code 055 * removeAll}, and {@code replaceValues} return collections that iterate through the values in the 056 * order they were added. The collections generated by {@code entries} and {@code values} iterate 057 * across the key-value mappings in the order they were added to the multimap. 058 * 059 * <p>The iteration ordering of the collections generated by {@code keySet}, {@code keys}, and 060 * {@code asMap} has a few subtleties. As long as the set of keys remains unchanged, adding or 061 * removing mappings does not affect the key iteration order. However, if you remove all values 062 * associated with a key and then add the key back to the multimap, that key will come last in the 063 * key iteration order. 064 * 065 * <p>The multimap does not store duplicate key-value pairs. Adding a new key-value pair equal to an 066 * existing key-value pair has no effect. 067 * 068 * <p>Keys and values may be null. All optional multimap methods are supported, and all returned 069 * views are modifiable. 070 * 071 * <p>This class is not threadsafe when any concurrent operations update the multimap. Concurrent 072 * read operations will work correctly. To allow concurrent update operations, wrap your multimap 073 * with a call to {@link Multimaps#synchronizedSetMultimap}. 074 * 075 * <p><b>Warning:</b> Do not modify either a key <i>or a value</i> of a {@code LinkedHashMultimap} 076 * in a way that affects its {@link Object#equals} behavior. Undefined behavior and bugs will 077 * result. 078 * 079 * <p>See the Guava User Guide article on <a href= 080 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#multimap">{@code 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 to delete them or iterate 177 * past 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 hypothetical 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 private ValueSetLink<K, V> predecessorInValueSet; 197 @CheckForNull private ValueSetLink<K, V> successorInValueSet; 198 199 @CheckForNull private ValueEntry<K, V> predecessorInMultimap; 200 @CheckForNull private 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 = 509 (ValueEntry<K, V>[]) new ValueEntry<?, ?>[this.hashTable.length * 2]; 510 this.hashTable = hashTable; 511 int mask = hashTable.length - 1; 512 for (ValueSetLink<K, V> entry = firstEntry; 513 entry != this; 514 entry = entry.getSuccessorInValueSet()) { 515 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 516 int bucket = valueEntry.smearedValueHash & mask; 517 valueEntry.nextInValueBucket = hashTable[bucket]; 518 hashTable[bucket] = valueEntry; 519 } 520 } 521 } 522 523 @CanIgnoreReturnValue 524 @Override 525 public boolean remove(@CheckForNull Object o) { 526 int smearedHash = Hashing.smearedHash(o); 527 int bucket = smearedHash & mask(); 528 ValueEntry<K, V> prev = null; 529 for (ValueEntry<K, V> entry = hashTable[bucket]; 530 entry != null; 531 prev = entry, entry = entry.nextInValueBucket) { 532 if (entry.matchesValue(o, smearedHash)) { 533 if (prev == null) { 534 // first entry in the bucket 535 hashTable[bucket] = entry.nextInValueBucket; 536 } else { 537 prev.nextInValueBucket = entry.nextInValueBucket; 538 } 539 deleteFromValueSet(entry); 540 deleteFromMultimap(entry); 541 size--; 542 modCount++; 543 return true; 544 } 545 } 546 return false; 547 } 548 549 @Override 550 public void clear() { 551 Arrays.fill(hashTable, null); 552 size = 0; 553 for (ValueSetLink<K, V> entry = firstEntry; 554 entry != this; 555 entry = entry.getSuccessorInValueSet()) { 556 ValueEntry<K, V> valueEntry = (ValueEntry<K, V>) entry; 557 deleteFromMultimap(valueEntry); 558 } 559 succeedsInValueSet(this, this); 560 modCount++; 561 } 562 } 563 564 @Override 565 Iterator<Entry<K, V>> entryIterator() { 566 return new Iterator<Entry<K, V>>() { 567 ValueEntry<K, V> nextEntry = multimapHeaderEntry.getSuccessorInMultimap(); 568 @CheckForNull ValueEntry<K, V> toRemove; 569 570 @Override 571 public boolean hasNext() { 572 return nextEntry != multimapHeaderEntry; 573 } 574 575 @Override 576 public Entry<K, V> next() { 577 if (!hasNext()) { 578 throw new NoSuchElementException(); 579 } 580 ValueEntry<K, V> result = nextEntry; 581 toRemove = result; 582 nextEntry = nextEntry.getSuccessorInMultimap(); 583 return result; 584 } 585 586 @Override 587 public void remove() { 588 checkState(toRemove != null, "no calls to next() since the last call to remove()"); 589 LinkedHashMultimap.this.remove(toRemove.getKey(), toRemove.getValue()); 590 toRemove = null; 591 } 592 }; 593 } 594 595 @Override 596 Spliterator<Entry<K, V>> entrySpliterator() { 597 return Spliterators.spliterator(entries(), Spliterator.DISTINCT | Spliterator.ORDERED); 598 } 599 600 @Override 601 Iterator<V> valueIterator() { 602 return Maps.valueIterator(entryIterator()); 603 } 604 605 @Override 606 Spliterator<V> valueSpliterator() { 607 return CollectSpliterators.map(entrySpliterator(), Entry::getValue); 608 } 609 610 @Override 611 public void clear() { 612 super.clear(); 613 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 614 } 615 616 /** 617 * @serialData the expected values per key, the number of distinct keys, the number of entries, 618 * and the entries in order 619 */ 620 @GwtIncompatible // java.io.ObjectOutputStream 621 @J2ktIncompatible 622 private void writeObject(ObjectOutputStream stream) throws IOException { 623 stream.defaultWriteObject(); 624 stream.writeInt(keySet().size()); 625 for (K key : keySet()) { 626 stream.writeObject(key); 627 } 628 stream.writeInt(size()); 629 for (Entry<K, V> entry : entries()) { 630 stream.writeObject(entry.getKey()); 631 stream.writeObject(entry.getValue()); 632 } 633 } 634 635 @GwtIncompatible // java.io.ObjectInputStream 636 @J2ktIncompatible 637 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 638 stream.defaultReadObject(); 639 multimapHeaderEntry = ValueEntry.newHeader(); 640 succeedsInMultimap(multimapHeaderEntry, multimapHeaderEntry); 641 valueSetCapacity = DEFAULT_VALUE_SET_CAPACITY; 642 int distinctKeys = stream.readInt(); 643 Map<K, Collection<V>> map = Platform.newLinkedHashMapWithExpectedSize(12); 644 for (int i = 0; i < distinctKeys; i++) { 645 @SuppressWarnings("unchecked") 646 K key = (K) stream.readObject(); 647 map.put(key, createCollection(key)); 648 } 649 int entries = stream.readInt(); 650 for (int i = 0; i < entries; i++) { 651 @SuppressWarnings("unchecked") 652 K key = (K) stream.readObject(); 653 @SuppressWarnings("unchecked") 654 V value = (V) stream.readObject(); 655 /* 656 * requireNonNull is safe for a properly serialized multimap: We've already inserted a 657 * collection for each key that we expect. 658 */ 659 requireNonNull(map.get(key)).add(value); 660 } 661 setMap(map); 662 } 663 664 @GwtIncompatible // java serialization not supported 665 @J2ktIncompatible 666 private static final long serialVersionUID = 1; 667}