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