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