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