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