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