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}