001/* 002 * Copyright (C) 2007 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except 005 * in compliance with the License. You may obtain a copy of the License at 006 * 007 * http://www.apache.org/licenses/LICENSE-2.0 008 * 009 * Unless required by applicable law or agreed to in writing, software distributed under the License 010 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express 011 * or implied. See the License for the specific language governing permissions and limitations under 012 * the License. 013 */ 014 015package com.google.common.collect; 016 017import static com.google.common.base.Preconditions.checkArgument; 018import static com.google.common.base.Preconditions.checkNotNull; 019import static com.google.common.collect.CollectPreconditions.checkNonnegative; 020import static com.google.common.collect.Hashing.smearedHash; 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.base.Objects; 027import com.google.common.collect.Maps.IteratorBasedAbstractMap; 028import com.google.errorprone.annotations.CanIgnoreReturnValue; 029import com.google.errorprone.annotations.concurrent.LazyInit; 030import com.google.j2objc.annotations.RetainedWith; 031import com.google.j2objc.annotations.Weak; 032import java.io.IOException; 033import java.io.InvalidObjectException; 034import java.io.ObjectInputStream; 035import java.io.ObjectOutputStream; 036import java.io.Serializable; 037import java.util.Arrays; 038import java.util.ConcurrentModificationException; 039import java.util.Iterator; 040import java.util.Map; 041import java.util.NoSuchElementException; 042import java.util.Set; 043import java.util.function.BiConsumer; 044import java.util.function.BiFunction; 045import javax.annotation.CheckForNull; 046import org.checkerframework.checker.nullness.qual.Nullable; 047 048/** 049 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A 050 * {@code HashBiMap} and its inverse are both serializable. 051 * 052 * <p>This implementation guarantees insertion-based iteration order of its keys. 053 * 054 * <p>See the Guava User Guide article on <a href= 055 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap">{@code BiMap} </a>. 056 * 057 * @author Louis Wasserman 058 * @author Mike Bostock 059 * @since 2.0 060 */ 061@GwtCompatible(emulated = true) 062public final class HashBiMap<K extends @Nullable Object, V extends @Nullable Object> 063 extends IteratorBasedAbstractMap<K, V> implements BiMap<K, V>, Serializable { 064 065 /** Returns a new, empty {@code HashBiMap} with the default initial capacity (16). */ 066 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create() { 067 return create(16); 068 } 069 070 /** 071 * Constructs a new, empty bimap with the specified expected size. 072 * 073 * @param expectedSize the expected number of entries 074 * @throws IllegalArgumentException if the specified expected size is negative 075 */ 076 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create( 077 int expectedSize) { 078 return new HashBiMap<>(expectedSize); 079 } 080 081 /** 082 * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an 083 * initial capacity sufficient to hold the mappings in the specified map. 084 */ 085 public static <K extends @Nullable Object, V extends @Nullable Object> HashBiMap<K, V> create( 086 Map<? extends K, ? extends V> map) { 087 HashBiMap<K, V> bimap = create(map.size()); 088 bimap.putAll(map); 089 return bimap; 090 } 091 092 static final class BiEntry<K extends @Nullable Object, V extends @Nullable Object> 093 extends ImmutableEntry<K, V> { 094 final int keyHash; 095 final int valueHash; 096 097 // All BiEntry instances are strongly reachable from owning HashBiMap through 098 // "HashBiMap.hashTableKToV" and "BiEntry.nextInKToVBucket" references. 099 // Under that assumption, the remaining references can be safely marked as @Weak. 100 // Using @Weak is necessary to avoid retain-cycles between BiEntry instances on iOS, 101 // which would cause memory leaks when non-empty HashBiMap with cyclic BiEntry 102 // instances is deallocated. 103 @CheckForNull BiEntry<K, V> nextInKToVBucket; 104 @Weak @CheckForNull BiEntry<K, V> nextInVToKBucket; 105 106 @Weak @CheckForNull BiEntry<K, V> nextInKeyInsertionOrder; 107 @Weak @CheckForNull BiEntry<K, V> prevInKeyInsertionOrder; 108 109 BiEntry(@ParametricNullness K key, int keyHash, @ParametricNullness V value, int valueHash) { 110 super(key, value); 111 this.keyHash = keyHash; 112 this.valueHash = valueHash; 113 } 114 } 115 116 private static final double LOAD_FACTOR = 1.0; 117 118 /* 119 * The following two arrays may *contain* nulls, but they are never *themselves* null: Even though 120 * they are not initialized inline in the constructor, they are initialized from init(), which the 121 * constructor calls (as does readObject()). 122 */ 123 @SuppressWarnings("nullness:initialization.field.uninitialized") // For J2KT (see above) 124 private transient @Nullable BiEntry<K, V>[] hashTableKToV; 125 126 @SuppressWarnings("nullness:initialization.field.uninitialized") // For J2KT (see above) 127 private transient @Nullable BiEntry<K, V>[] hashTableVToK; 128 129 @Weak @CheckForNull private transient BiEntry<K, V> firstInKeyInsertionOrder; 130 @Weak @CheckForNull private transient BiEntry<K, V> lastInKeyInsertionOrder; 131 private transient int size; 132 private transient int mask; 133 private transient int modCount; 134 135 private HashBiMap(int expectedSize) { 136 init(expectedSize); 137 } 138 139 private void init(int expectedSize) { 140 checkNonnegative(expectedSize, "expectedSize"); 141 int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR); 142 this.hashTableKToV = createTable(tableSize); 143 this.hashTableVToK = createTable(tableSize); 144 this.firstInKeyInsertionOrder = null; 145 this.lastInKeyInsertionOrder = null; 146 this.size = 0; 147 this.mask = tableSize - 1; 148 this.modCount = 0; 149 } 150 151 /** 152 * Finds and removes {@code entry} from the bucket linked lists in both the key-to-value direction 153 * and the value-to-key direction. 154 */ 155 private void delete(BiEntry<K, V> entry) { 156 int keyBucket = entry.keyHash & mask; 157 BiEntry<K, V> prevBucketEntry = null; 158 for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket]; 159 true; 160 bucketEntry = bucketEntry.nextInKToVBucket) { 161 if (bucketEntry == entry) { 162 if (prevBucketEntry == null) { 163 hashTableKToV[keyBucket] = entry.nextInKToVBucket; 164 } else { 165 prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket; 166 } 167 break; 168 } 169 prevBucketEntry = bucketEntry; 170 } 171 172 int valueBucket = entry.valueHash & mask; 173 prevBucketEntry = null; 174 for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket]; 175 true; 176 bucketEntry = bucketEntry.nextInVToKBucket) { 177 if (bucketEntry == entry) { 178 if (prevBucketEntry == null) { 179 hashTableVToK[valueBucket] = entry.nextInVToKBucket; 180 } else { 181 prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket; 182 } 183 break; 184 } 185 prevBucketEntry = bucketEntry; 186 } 187 188 if (entry.prevInKeyInsertionOrder == null) { 189 firstInKeyInsertionOrder = entry.nextInKeyInsertionOrder; 190 } else { 191 entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry.nextInKeyInsertionOrder; 192 } 193 194 if (entry.nextInKeyInsertionOrder == null) { 195 lastInKeyInsertionOrder = entry.prevInKeyInsertionOrder; 196 } else { 197 entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry.prevInKeyInsertionOrder; 198 } 199 200 size--; 201 modCount++; 202 } 203 204 private void insert(BiEntry<K, V> entry, @CheckForNull BiEntry<K, V> oldEntryForKey) { 205 int keyBucket = entry.keyHash & mask; 206 entry.nextInKToVBucket = hashTableKToV[keyBucket]; 207 hashTableKToV[keyBucket] = entry; 208 209 int valueBucket = entry.valueHash & mask; 210 entry.nextInVToKBucket = hashTableVToK[valueBucket]; 211 hashTableVToK[valueBucket] = entry; 212 213 if (oldEntryForKey == null) { 214 entry.prevInKeyInsertionOrder = lastInKeyInsertionOrder; 215 entry.nextInKeyInsertionOrder = null; 216 if (lastInKeyInsertionOrder == null) { 217 firstInKeyInsertionOrder = entry; 218 } else { 219 lastInKeyInsertionOrder.nextInKeyInsertionOrder = entry; 220 } 221 lastInKeyInsertionOrder = entry; 222 } else { 223 entry.prevInKeyInsertionOrder = oldEntryForKey.prevInKeyInsertionOrder; 224 if (entry.prevInKeyInsertionOrder == null) { 225 firstInKeyInsertionOrder = entry; 226 } else { 227 entry.prevInKeyInsertionOrder.nextInKeyInsertionOrder = entry; 228 } 229 entry.nextInKeyInsertionOrder = oldEntryForKey.nextInKeyInsertionOrder; 230 if (entry.nextInKeyInsertionOrder == null) { 231 lastInKeyInsertionOrder = entry; 232 } else { 233 entry.nextInKeyInsertionOrder.prevInKeyInsertionOrder = entry; 234 } 235 } 236 237 size++; 238 modCount++; 239 } 240 241 @CheckForNull 242 private BiEntry<K, V> seekByKey(@CheckForNull Object key, int keyHash) { 243 for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask]; 244 entry != null; 245 entry = entry.nextInKToVBucket) { 246 if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) { 247 return entry; 248 } 249 } 250 return null; 251 } 252 253 @CheckForNull 254 private BiEntry<K, V> seekByValue(@CheckForNull Object value, int valueHash) { 255 for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask]; 256 entry != null; 257 entry = entry.nextInVToKBucket) { 258 if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) { 259 return entry; 260 } 261 } 262 return null; 263 } 264 265 @Override 266 public boolean containsKey(@CheckForNull Object key) { 267 return seekByKey(key, smearedHash(key)) != null; 268 } 269 270 /** 271 * Returns {@code true} if this BiMap contains an entry whose value is equal to {@code value} (or, 272 * equivalently, if this inverse view contains a key that is equal to {@code value}). 273 * 274 * <p>Due to the property that values in a BiMap are unique, this will tend to execute in 275 * faster-than-linear time. 276 * 277 * @param value the object to search for in the values of this BiMap 278 * @return true if a mapping exists from a key to the specified value 279 */ 280 @Override 281 public boolean containsValue(@CheckForNull Object value) { 282 return seekByValue(value, smearedHash(value)) != null; 283 } 284 285 @Override 286 @CheckForNull 287 public V get(@CheckForNull Object key) { 288 return Maps.valueOrNull(seekByKey(key, smearedHash(key))); 289 } 290 291 @CanIgnoreReturnValue 292 @Override 293 @CheckForNull 294 public V put(@ParametricNullness K key, @ParametricNullness V value) { 295 return put(key, value, false); 296 } 297 298 @CheckForNull 299 private V put(@ParametricNullness K key, @ParametricNullness V value, boolean force) { 300 int keyHash = smearedHash(key); 301 int valueHash = smearedHash(value); 302 303 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 304 if (oldEntryForKey != null 305 && valueHash == oldEntryForKey.valueHash 306 && Objects.equal(value, oldEntryForKey.value)) { 307 return value; 308 } 309 310 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 311 if (oldEntryForValue != null) { 312 if (force) { 313 delete(oldEntryForValue); 314 } else { 315 throw new IllegalArgumentException("value already present: " + value); 316 } 317 } 318 319 BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash); 320 if (oldEntryForKey != null) { 321 delete(oldEntryForKey); 322 insert(newEntry, oldEntryForKey); 323 oldEntryForKey.prevInKeyInsertionOrder = null; 324 oldEntryForKey.nextInKeyInsertionOrder = null; 325 return oldEntryForKey.value; 326 } else { 327 insert(newEntry, null); 328 rehashIfNecessary(); 329 return null; 330 } 331 } 332 333 @CanIgnoreReturnValue 334 @Override 335 @CheckForNull 336 public V forcePut(@ParametricNullness K key, @ParametricNullness V value) { 337 return put(key, value, true); 338 } 339 340 @CanIgnoreReturnValue 341 @CheckForNull 342 private K putInverse(@ParametricNullness V value, @ParametricNullness K key, boolean force) { 343 int valueHash = smearedHash(value); 344 int keyHash = smearedHash(key); 345 346 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 347 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 348 if (oldEntryForValue != null 349 && keyHash == oldEntryForValue.keyHash 350 && Objects.equal(key, oldEntryForValue.key)) { 351 return key; 352 } else if (oldEntryForKey != null && !force) { 353 throw new IllegalArgumentException("key already present: " + key); 354 } 355 356 /* 357 * The ordering here is important: if we deleted the key entry and then the value entry, 358 * the key entry's prev or next pointer might point to the dead value entry, and when we 359 * put the new entry in the key entry's position in iteration order, it might invalidate 360 * the linked list. 361 */ 362 363 if (oldEntryForValue != null) { 364 delete(oldEntryForValue); 365 } 366 367 if (oldEntryForKey != null) { 368 delete(oldEntryForKey); 369 } 370 371 BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash); 372 insert(newEntry, oldEntryForKey); 373 374 if (oldEntryForKey != null) { 375 oldEntryForKey.prevInKeyInsertionOrder = null; 376 oldEntryForKey.nextInKeyInsertionOrder = null; 377 } 378 if (oldEntryForValue != null) { 379 oldEntryForValue.prevInKeyInsertionOrder = null; 380 oldEntryForValue.nextInKeyInsertionOrder = null; 381 } 382 rehashIfNecessary(); 383 return Maps.keyOrNull(oldEntryForValue); 384 } 385 386 private void rehashIfNecessary() { 387 @Nullable BiEntry<K, V>[] oldKToV = hashTableKToV; 388 if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) { 389 int newTableSize = oldKToV.length * 2; 390 391 this.hashTableKToV = createTable(newTableSize); 392 this.hashTableVToK = createTable(newTableSize); 393 this.mask = newTableSize - 1; 394 this.size = 0; 395 396 for (BiEntry<K, V> entry = firstInKeyInsertionOrder; 397 entry != null; 398 entry = entry.nextInKeyInsertionOrder) { 399 insert(entry, entry); 400 } 401 this.modCount++; 402 } 403 } 404 405 @SuppressWarnings({"unchecked", "rawtypes"}) 406 private @Nullable BiEntry<K, V>[] createTable(int length) { 407 return new @Nullable BiEntry[length]; 408 } 409 410 @CanIgnoreReturnValue 411 @Override 412 @CheckForNull 413 public V remove(@CheckForNull Object key) { 414 BiEntry<K, V> entry = seekByKey(key, smearedHash(key)); 415 if (entry == null) { 416 return null; 417 } else { 418 delete(entry); 419 entry.prevInKeyInsertionOrder = null; 420 entry.nextInKeyInsertionOrder = null; 421 return entry.value; 422 } 423 } 424 425 @Override 426 public void clear() { 427 size = 0; 428 Arrays.fill(hashTableKToV, null); 429 Arrays.fill(hashTableVToK, null); 430 firstInKeyInsertionOrder = null; 431 lastInKeyInsertionOrder = null; 432 modCount++; 433 } 434 435 @Override 436 public int size() { 437 return size; 438 } 439 440 private abstract class Itr<T extends @Nullable Object> implements Iterator<T> { 441 @CheckForNull BiEntry<K, V> next = firstInKeyInsertionOrder; 442 @CheckForNull BiEntry<K, V> toRemove = null; 443 int expectedModCount = modCount; 444 int remaining = size(); 445 446 @Override 447 public boolean hasNext() { 448 if (modCount != expectedModCount) { 449 throw new ConcurrentModificationException(); 450 } 451 return next != null && remaining > 0; 452 } 453 454 @Override 455 public T next() { 456 if (!hasNext()) { 457 throw new NoSuchElementException(); 458 } 459 460 // requireNonNull is safe because of the hasNext check. 461 BiEntry<K, V> entry = requireNonNull(next); 462 next = entry.nextInKeyInsertionOrder; 463 toRemove = entry; 464 remaining--; 465 return output(entry); 466 } 467 468 @Override 469 public void remove() { 470 if (modCount != expectedModCount) { 471 throw new ConcurrentModificationException(); 472 } 473 if (toRemove == null) { 474 throw new IllegalStateException("no calls to next() since the last call to remove()"); 475 } 476 delete(toRemove); 477 expectedModCount = modCount; 478 toRemove = null; 479 } 480 481 abstract T output(BiEntry<K, V> entry); 482 } 483 484 @Override 485 public Set<K> keySet() { 486 return new KeySet(); 487 } 488 489 private final class KeySet extends Maps.KeySet<K, V> { 490 KeySet() { 491 super(HashBiMap.this); 492 } 493 494 @Override 495 public Iterator<K> iterator() { 496 return new Itr<K>() { 497 @Override 498 @ParametricNullness 499 K output(BiEntry<K, V> entry) { 500 return entry.key; 501 } 502 }; 503 } 504 505 @Override 506 public boolean remove(@CheckForNull Object o) { 507 BiEntry<K, V> entry = seekByKey(o, smearedHash(o)); 508 if (entry == null) { 509 return false; 510 } else { 511 delete(entry); 512 entry.prevInKeyInsertionOrder = null; 513 entry.nextInKeyInsertionOrder = null; 514 return true; 515 } 516 } 517 } 518 519 @Override 520 public Set<V> values() { 521 return inverse().keySet(); 522 } 523 524 @Override 525 Iterator<Entry<K, V>> entryIterator() { 526 return new Itr<Entry<K, V>>() { 527 @Override 528 Entry<K, V> output(BiEntry<K, V> entry) { 529 return new MapEntry(entry); 530 } 531 532 class MapEntry extends AbstractMapEntry<K, V> { 533 private BiEntry<K, V> delegate; 534 535 MapEntry(BiEntry<K, V> entry) { 536 this.delegate = entry; 537 } 538 539 @Override 540 @ParametricNullness 541 public K getKey() { 542 return delegate.key; 543 } 544 545 @Override 546 @ParametricNullness 547 public V getValue() { 548 return delegate.value; 549 } 550 551 @Override 552 @ParametricNullness 553 public V setValue(@ParametricNullness V value) { 554 V oldValue = delegate.value; 555 int valueHash = smearedHash(value); 556 if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) { 557 return value; 558 } 559 checkArgument(seekByValue(value, valueHash) == null, "value already present: %s", value); 560 delete(delegate); 561 BiEntry<K, V> newEntry = new BiEntry<>(delegate.key, delegate.keyHash, value, valueHash); 562 insert(newEntry, delegate); 563 delegate.prevInKeyInsertionOrder = null; 564 delegate.nextInKeyInsertionOrder = null; 565 expectedModCount = modCount; 566 if (toRemove == delegate) { 567 toRemove = newEntry; 568 } 569 delegate = newEntry; 570 return oldValue; 571 } 572 } 573 }; 574 } 575 576 @Override 577 public void forEach(BiConsumer<? super K, ? super V> action) { 578 checkNotNull(action); 579 for (BiEntry<K, V> entry = firstInKeyInsertionOrder; 580 entry != null; 581 entry = entry.nextInKeyInsertionOrder) { 582 action.accept(entry.key, entry.value); 583 } 584 } 585 586 @Override 587 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 588 checkNotNull(function); 589 BiEntry<K, V> oldFirst = firstInKeyInsertionOrder; 590 clear(); 591 for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) { 592 put(entry.key, function.apply(entry.key, entry.value)); 593 } 594 } 595 596 @LazyInit @RetainedWith @CheckForNull private transient BiMap<V, K> inverse; 597 598 @Override 599 public BiMap<V, K> inverse() { 600 BiMap<V, K> result = inverse; 601 return (result == null) ? inverse = new Inverse() : result; 602 } 603 604 private final class Inverse extends IteratorBasedAbstractMap<V, K> 605 implements BiMap<V, K>, Serializable { 606 BiMap<K, V> forward() { 607 return HashBiMap.this; 608 } 609 610 @Override 611 public int size() { 612 return size; 613 } 614 615 @Override 616 public void clear() { 617 forward().clear(); 618 } 619 620 @Override 621 public boolean containsKey(@CheckForNull Object value) { 622 return forward().containsValue(value); 623 } 624 625 @Override 626 @CheckForNull 627 public K get(@CheckForNull Object value) { 628 return Maps.keyOrNull(seekByValue(value, smearedHash(value))); 629 } 630 631 @CanIgnoreReturnValue 632 @Override 633 @CheckForNull 634 public K put(@ParametricNullness V value, @ParametricNullness K key) { 635 return putInverse(value, key, false); 636 } 637 638 @Override 639 @CheckForNull 640 public K forcePut(@ParametricNullness V value, @ParametricNullness K key) { 641 return putInverse(value, key, true); 642 } 643 644 @Override 645 @CheckForNull 646 public K remove(@CheckForNull Object value) { 647 BiEntry<K, V> entry = seekByValue(value, smearedHash(value)); 648 if (entry == null) { 649 return null; 650 } else { 651 delete(entry); 652 entry.prevInKeyInsertionOrder = null; 653 entry.nextInKeyInsertionOrder = null; 654 return entry.key; 655 } 656 } 657 658 @Override 659 public BiMap<K, V> inverse() { 660 return forward(); 661 } 662 663 @Override 664 public Set<V> keySet() { 665 return new InverseKeySet(); 666 } 667 668 private final class InverseKeySet extends Maps.KeySet<V, K> { 669 InverseKeySet() { 670 super(Inverse.this); 671 } 672 673 @Override 674 public boolean remove(@CheckForNull Object o) { 675 BiEntry<K, V> entry = seekByValue(o, smearedHash(o)); 676 if (entry == null) { 677 return false; 678 } else { 679 delete(entry); 680 return true; 681 } 682 } 683 684 @Override 685 public Iterator<V> iterator() { 686 return new Itr<V>() { 687 @Override 688 @ParametricNullness 689 V output(BiEntry<K, V> entry) { 690 return entry.value; 691 } 692 }; 693 } 694 } 695 696 @Override 697 public Set<K> values() { 698 return forward().keySet(); 699 } 700 701 @Override 702 Iterator<Entry<V, K>> entryIterator() { 703 return new Itr<Entry<V, K>>() { 704 @Override 705 Entry<V, K> output(BiEntry<K, V> entry) { 706 return new InverseEntry(entry); 707 } 708 709 class InverseEntry extends AbstractMapEntry<V, K> { 710 private BiEntry<K, V> delegate; 711 712 InverseEntry(BiEntry<K, V> entry) { 713 this.delegate = entry; 714 } 715 716 @Override 717 @ParametricNullness 718 public V getKey() { 719 return delegate.value; 720 } 721 722 @Override 723 @ParametricNullness 724 public K getValue() { 725 return delegate.key; 726 } 727 728 @Override 729 @ParametricNullness 730 public K setValue(@ParametricNullness K key) { 731 K oldKey = delegate.key; 732 int keyHash = smearedHash(key); 733 if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) { 734 return key; 735 } 736 checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key); 737 delete(delegate); 738 BiEntry<K, V> newEntry = 739 new BiEntry<>(key, keyHash, delegate.value, delegate.valueHash); 740 delegate = newEntry; 741 insert(newEntry, null); 742 expectedModCount = modCount; 743 return oldKey; 744 } 745 } 746 }; 747 } 748 749 @Override 750 public void forEach(BiConsumer<? super V, ? super K> action) { 751 checkNotNull(action); 752 HashBiMap.this.forEach((k, v) -> action.accept(v, k)); 753 } 754 755 @Override 756 public void replaceAll(BiFunction<? super V, ? super K, ? extends K> function) { 757 checkNotNull(function); 758 BiEntry<K, V> oldFirst = firstInKeyInsertionOrder; 759 clear(); 760 for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) { 761 put(entry.value, function.apply(entry.value, entry.key)); 762 } 763 } 764 765 Object writeReplace() { 766 return new InverseSerializedForm<>(HashBiMap.this); 767 } 768 769 @GwtIncompatible // serialization 770 @J2ktIncompatible 771 private void readObject(ObjectInputStream in) throws InvalidObjectException { 772 throw new InvalidObjectException("Use InverseSerializedForm"); 773 } 774 } 775 776 private static final class InverseSerializedForm< 777 K extends @Nullable Object, V extends @Nullable Object> 778 implements Serializable { 779 private final HashBiMap<K, V> bimap; 780 781 InverseSerializedForm(HashBiMap<K, V> bimap) { 782 this.bimap = bimap; 783 } 784 785 Object readResolve() { 786 return bimap.inverse(); 787 } 788 } 789 790 /** 791 * @serialData the number of entries, first key, first value, second key, second value, and so on. 792 */ 793 @GwtIncompatible // java.io.ObjectOutputStream 794 @J2ktIncompatible 795 private void writeObject(ObjectOutputStream stream) throws IOException { 796 stream.defaultWriteObject(); 797 Serialization.writeMap(this, stream); 798 } 799 800 @GwtIncompatible // java.io.ObjectInputStream 801 @J2ktIncompatible 802 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 803 stream.defaultReadObject(); 804 int size = Serialization.readCount(stream); 805 init(16); // resist hostile attempts to allocate gratuitous heap 806 Serialization.populateMap(this, stream, size); 807 } 808 809 @GwtIncompatible // Not needed in emulated source 810 @J2ktIncompatible 811 private static final long serialVersionUID = 0; 812}