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