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}