Source code

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.closedTableSize;
021import static com.google.common.collect.Hashing.smearedHash;
022import static java.util.Objects.requireNonNull;
023
024import com.google.common.annotations.GwtCompatible;
025import com.google.common.annotations.GwtIncompatible;
026import com.google.common.annotations.J2ktIncompatible;
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.Objects;
043import java.util.Set;
044import java.util.function.BiConsumer;
045import java.util.function.BiFunction;
046import org.jspecify.annotations.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
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  /**
093   * An immutable key-value pair with mutable links to other pairs in its hash buckets and in
094   * iteration order.
095   */
096  static final class Node<K extends @Nullable Object, V extends @Nullable Object> {
097    @ParametricNullness final K key;
098    @ParametricNullness final V value;
099
100    final int keyHash;
101    final int valueHash;
102
103    // All Node instances are strongly reachable from owning HashBiMap through
104    // "HashBiMap.hashTableKToV" and "Node.nextInKToVBucket" references.
105    // Under that assumption, the remaining references can be safely marked as @Weak.
106    // Using @Weak is necessary to avoid retain-cycles between Node instances on iOS,
107    // which would cause memory leaks when non-empty HashBiMap with cyclic Node
108    // instances is deallocated.
109    @Nullable Node<K, V> nextInKToVBucket;
110    @Weak @Nullable Node<K, V> nextInVToKBucket;
111
112    @Weak @Nullable Node<K, V> nextInKeyInsertionOrder;
113    @Weak @Nullable Node<K, V> prevInKeyInsertionOrder;
114
115    Node(@ParametricNullness K key, int keyHash, @ParametricNullness V value, int valueHash) {
116      this.key = key;
117      this.value = value;
118      this.keyHash = keyHash;
119      this.valueHash = valueHash;
120    }
121  }
122
123  private static final double LOAD_FACTOR = 1.0;
124
125  /*
126   * The following two arrays may *contain* nulls, but they are never *themselves* null: Even though
127   * they are not initialized inline in the constructor, they are initialized from init(), which the
128   * constructor calls (as does readObject()).
129   */
130  @SuppressWarnings("nullness:initialization.field.uninitialized") // For J2KT (see above)
131  private transient @Nullable Node<K, V>[] hashTableKToV;
132
133  @SuppressWarnings("nullness:initialization.field.uninitialized") // For J2KT (see above)
134  private transient @Nullable Node<K, V>[] hashTableVToK;
135
136  @Weak private transient @Nullable Node<K, V> firstInKeyInsertionOrder;
137  @Weak private transient @Nullable Node<K, V> lastInKeyInsertionOrder;
138  private transient int size;
139  private transient int mask;
140  private transient int modCount;
141
142  private HashBiMap(int expectedSize) {
143    init(expectedSize);
144  }
145
146  private void init(int expectedSize) {
147    checkNonnegative(expectedSize, "expectedSize");
148    int tableSize = closedTableSize(expectedSize, LOAD_FACTOR);
149    this.hashTableKToV = createTable(tableSize);
150    this.hashTableVToK = createTable(tableSize);
151    this.firstInKeyInsertionOrder = null;
152    this.lastInKeyInsertionOrder = null;
153    this.size = 0;
154    this.mask = tableSize - 1;
155    this.modCount = 0;
156  }
157
158  /**
159   * Finds and removes {@code node} from the key-to-value hash table, the value-to-key hash table,
160   * and the iteration-order chain. This includes clearing its own references to other entries.
161   */
162  private void delete(Node<K, V> node) {
163    int keyBucket = node.keyHash & mask;
164    Node<K, V> prevBucketNode = null;
165    for (Node<K, V> bucketNode = hashTableKToV[keyBucket];
166        true;
167        bucketNode = bucketNode.nextInKToVBucket) {
168      if (bucketNode == node) {
169        if (prevBucketNode == null) {
170          hashTableKToV[keyBucket] = node.nextInKToVBucket;
171        } else {
172          prevBucketNode.nextInKToVBucket = node.nextInKToVBucket;
173        }
174        break;
175      }
176      prevBucketNode = bucketNode;
177    }
178
179    int valueBucket = node.valueHash & mask;
180    prevBucketNode = null;
181    for (Node<K, V> bucketNode = hashTableVToK[valueBucket];
182        true;
183        bucketNode = bucketNode.nextInVToKBucket) {
184      if (bucketNode == node) {
185        if (prevBucketNode == null) {
186          hashTableVToK[valueBucket] = node.nextInVToKBucket;
187        } else {
188          prevBucketNode.nextInVToKBucket = node.nextInVToKBucket;
189        }
190        break;
191      }
192      prevBucketNode = bucketNode;
193    }
194
195    if (node.prevInKeyInsertionOrder == null) {
196      firstInKeyInsertionOrder = node.nextInKeyInsertionOrder;
197    } else {
198      node.prevInKeyInsertionOrder.nextInKeyInsertionOrder = node.nextInKeyInsertionOrder;
199    }
200
201    if (node.nextInKeyInsertionOrder == null) {
202      lastInKeyInsertionOrder = node.prevInKeyInsertionOrder;
203    } else {
204      node.nextInKeyInsertionOrder.prevInKeyInsertionOrder = node.prevInKeyInsertionOrder;
205    }
206
207    node.prevInKeyInsertionOrder = null;
208    node.nextInKeyInsertionOrder = null;
209    node.nextInKToVBucket = null;
210    node.nextInVToKBucket = null;
211
212    size--;
213    modCount++;
214  }
215
216  private void insertPlacingAtEndOfIterationOrder(Node<K, V> node) {
217    insertIntoHashBucketsOnly(node);
218
219    node.prevInKeyInsertionOrder = lastInKeyInsertionOrder;
220    if (lastInKeyInsertionOrder == null) {
221      firstInKeyInsertionOrder = node;
222    } else {
223      lastInKeyInsertionOrder.nextInKeyInsertionOrder = node;
224    }
225    lastInKeyInsertionOrder = node;
226  }
227
228  private void insertSplicingIntoIterationOrder(
229      Node<K, V> node,
230      @Nullable Node<K, V> prevInKeyInsertionOrder,
231      @Nullable Node<K, V> nextInKeyInsertionOrder) {
232    insertIntoHashBucketsOnly(node);
233
234    node.prevInKeyInsertionOrder = prevInKeyInsertionOrder;
235    if (prevInKeyInsertionOrder == null) {
236      firstInKeyInsertionOrder = node;
237    } else {
238      prevInKeyInsertionOrder.nextInKeyInsertionOrder = node;
239    }
240
241    node.nextInKeyInsertionOrder = nextInKeyInsertionOrder;
242    if (nextInKeyInsertionOrder == null) {
243      lastInKeyInsertionOrder = node;
244    } else {
245      nextInKeyInsertionOrder.prevInKeyInsertionOrder = node;
246    }
247  }
248
249  private void insertIntoHashBucketsOnly(Node<K, V> node) {
250    int keyBucket = node.keyHash & mask;
251    node.nextInKToVBucket = hashTableKToV[keyBucket];
252    hashTableKToV[keyBucket] = node;
253
254    int valueBucket = node.valueHash & mask;
255    node.nextInVToKBucket = hashTableVToK[valueBucket];
256    hashTableVToK[valueBucket] = node;
257
258    size++;
259    modCount++;
260  }
261
262  private void replaceNodeForKey(Node<K, V> oldNode, Node<K, V> newNode) {
263    Node<K, V> prevInKeyInsertionOrder = oldNode.prevInKeyInsertionOrder;
264    Node<K, V> nextInKeyInsertionOrder = oldNode.nextInKeyInsertionOrder;
265    delete(oldNode); // clears the two fields we just read
266    insertSplicingIntoIterationOrder(newNode, prevInKeyInsertionOrder, nextInKeyInsertionOrder);
267  }
268
269  private @Nullable Node<K, V> seekByKey(@Nullable Object key, int keyHash) {
270    for (Node<K, V> node = hashTableKToV[keyHash & mask];
271        node != null;
272        node = node.nextInKToVBucket) {
273      if (keyHash == node.keyHash && Objects.equals(key, node.key)) {
274        return node;
275      }
276    }
277    return null;
278  }
279
280  private @Nullable Node<K, V> seekByValue(@Nullable Object value, int valueHash) {
281    for (Node<K, V> node = hashTableVToK[valueHash & mask];
282        node != null;
283        node = node.nextInVToKBucket) {
284      if (valueHash == node.valueHash && Objects.equals(value, node.value)) {
285        return node;
286      }
287    }
288    return null;
289  }
290
291  @Override
292  public boolean containsKey(@Nullable Object key) {
293    return seekByKey(key, smearedHash(key)) != null;
294  }
295
296  /**
297   * Returns {@code true} if this BiMap contains an entry whose value is equal to {@code value} (or,
298   * equivalently, if this inverse view contains a key that is equal to {@code value}).
299   *
300   * <p>Due to the property that values in a BiMap are unique, this will tend to execute in
301   * faster-than-linear time.
302   *
303   * @param value the object to search for in the values of this BiMap
304   * @return true if a mapping exists from a key to the specified value
305   */
306  @Override
307  public boolean containsValue(@Nullable Object value) {
308    return seekByValue(value, smearedHash(value)) != null;
309  }
310
311  @Override
312  public @Nullable V get(@Nullable Object key) {
313    return valueOrNull(seekByKey(key, smearedHash(key)));
314  }
315
316  @CanIgnoreReturnValue
317  @Override
318  public @Nullable V put(@ParametricNullness K key, @ParametricNullness V value) {
319    return put(key, value, false);
320  }
321
322  private @Nullable V put(@ParametricNullness K key, @ParametricNullness V value, boolean force) {
323    int keyHash = smearedHash(key);
324    int valueHash = smearedHash(value);
325
326    Node<K, V> oldNodeForKey = seekByKey(key, keyHash);
327    if (oldNodeForKey != null
328        && valueHash == oldNodeForKey.valueHash
329        && Objects.equals(value, oldNodeForKey.value)) {
330      return value;
331    }
332
333    Node<K, V> oldNodeForValue = seekByValue(value, valueHash);
334    if (oldNodeForValue != null) {
335      if (force) {
336        delete(oldNodeForValue);
337      } else {
338        throw new IllegalArgumentException("value already present: " + value);
339      }
340    }
341
342    Node<K, V> newNode = new Node<>(key, keyHash, value, valueHash);
343    if (oldNodeForKey != null) {
344      replaceNodeForKey(oldNodeForKey, newNode);
345      return oldNodeForKey.value;
346    } else {
347      insertPlacingAtEndOfIterationOrder(newNode);
348      rehashIfNecessary();
349      return null;
350    }
351  }
352
353  @CanIgnoreReturnValue
354  @Override
355  public @Nullable V forcePut(@ParametricNullness K key, @ParametricNullness V value) {
356    return put(key, value, true);
357  }
358
359  @CanIgnoreReturnValue
360  private @Nullable K putInverse(
361      @ParametricNullness V value, @ParametricNullness K key, boolean force) {
362    int valueHash = smearedHash(value);
363    int keyHash = smearedHash(key);
364
365    Node<K, V> oldNodeForValue = seekByValue(value, valueHash);
366    Node<K, V> oldNodeForKey = seekByKey(key, keyHash);
367    if (oldNodeForValue != null
368        && keyHash == oldNodeForValue.keyHash
369        && Objects.equals(key, oldNodeForValue.key)) {
370      return key;
371    } else if (oldNodeForKey != null && !force) {
372      throw new IllegalArgumentException("key already present: " + key);
373    }
374
375    if (oldNodeForValue != null) {
376      delete(oldNodeForValue);
377    }
378
379    Node<K, V> newNode = new Node<>(key, keyHash, value, valueHash);
380    if (oldNodeForKey != null) {
381      replaceNodeForKey(oldNodeForKey, newNode);
382    } else {
383      insertPlacingAtEndOfIterationOrder(newNode);
384    }
385
386    // TODO(cpovirk): Don't perform rehash check if we replaced an existing entry (as in `put`)?
387    rehashIfNecessary();
388    return keyOrNull(oldNodeForValue);
389  }
390
391  private void rehashIfNecessary() {
392    @Nullable Node<K, V>[] oldKToV = hashTableKToV;
393    if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
394      int newTableSize = oldKToV.length * 2;
395
396      this.hashTableKToV = createTable(newTableSize);
397      this.hashTableVToK = createTable(newTableSize);
398      this.mask = newTableSize - 1;
399      this.size = 0;
400
401      for (Node<K, V> node = firstInKeyInsertionOrder;
402          node != null;
403          node = node.nextInKeyInsertionOrder) {
404        insertSplicingIntoIterationOrder(
405            node, node.prevInKeyInsertionOrder, node.nextInKeyInsertionOrder);
406      }
407      this.modCount++;
408    }
409  }
410
411  @SuppressWarnings({"unchecked", "rawtypes"})
412  private @Nullable Node<K, V>[] createTable(int length) {
413    return new @Nullable Node[length];
414  }
415
416  @CanIgnoreReturnValue
417  @Override
418  public @Nullable V remove(@Nullable Object key) {
419    Node<K, V> node = seekByKey(key, smearedHash(key));
420    if (node == null) {
421      return null;
422    } else {
423      delete(node);
424      node.prevInKeyInsertionOrder = null;
425      node.nextInKeyInsertionOrder = null;
426      return node.value;
427    }
428  }
429
430  @Override
431  public void clear() {
432    size = 0;
433    Arrays.fill(hashTableKToV, null);
434    Arrays.fill(hashTableVToK, null);
435    firstInKeyInsertionOrder = null;
436    lastInKeyInsertionOrder = null;
437    modCount++;
438  }
439
440  @Override
441  public int size() {
442    return size;
443  }
444
445  private abstract static class BiIterator<
446          K extends @Nullable Object, V extends @Nullable Object, T extends @Nullable Object>
447      implements Iterator<T> {
448    final HashBiMap<K, V> biMap;
449
450    @Nullable Node<K, V> next;
451    @Nullable Node<K, V> toRemove;
452    int expectedModCount;
453    int remaining;
454
455    BiIterator(HashBiMap<K, V> biMap) {
456      this.biMap = biMap;
457      next = biMap.firstInKeyInsertionOrder;
458      expectedModCount = biMap.modCount;
459      remaining = biMap.size();
460    }
461
462    @Override
463    public final boolean hasNext() {
464      if (biMap.modCount != expectedModCount) {
465        throw new ConcurrentModificationException();
466      }
467      return next != null && remaining > 0;
468    }
469
470    @Override
471    public final T next() {
472      if (!hasNext()) {
473        throw new NoSuchElementException();
474      }
475
476      // requireNonNull is safe because of the hasNext check.
477      Node<K, V> node = requireNonNull(next);
478      next = node.nextInKeyInsertionOrder;
479      toRemove = node;
480      remaining--;
481      return output(node);
482    }
483
484    @Override
485    public final void remove() {
486      if (biMap.modCount != expectedModCount) {
487        throw new ConcurrentModificationException();
488      }
489      if (toRemove == null) {
490        throw new IllegalStateException("no calls to next() since the last call to remove()");
491      }
492      biMap.delete(toRemove);
493      expectedModCount = biMap.modCount;
494      toRemove = null;
495    }
496
497    abstract T output(Node<K, V> node);
498  }
499
500  @Override
501  public Set<K> keySet() {
502    return new KeySet();
503  }
504
505  private final class KeySet extends Maps.KeySet<K, V> {
506    KeySet() {
507      super(HashBiMap.this);
508    }
509
510    @Override
511    public Iterator<K> iterator() {
512      return new BiIterator<K, V, K>(HashBiMap.this) {
513        @Override
514        @ParametricNullness
515        K output(Node<K, V> node) {
516          return node.key;
517        }
518      };
519    }
520
521    @Override
522    public boolean remove(@Nullable Object o) {
523      Node<K, V> node = seekByKey(o, smearedHash(o));
524      if (node == null) {
525        return false;
526      } else {
527        delete(node);
528        node.prevInKeyInsertionOrder = null;
529        node.nextInKeyInsertionOrder = null;
530        return true;
531      }
532    }
533  }
534
535  @Override
536  public Set<V> values() {
537    return inverse().keySet();
538  }
539
540  @Override
541  Iterator<Entry<K, V>> entryIterator() {
542    return new BiIterator<K, V, Entry<K, V>>(HashBiMap.this) {
543      @Override
544      Entry<K, V> output(Node<K, V> node) {
545        return new MapEntry(node);
546      }
547
548      final class MapEntry extends AbstractMapEntry<K, V> {
549        private Node<K, V> node;
550
551        MapEntry(Node<K, V> node) {
552          this.node = node;
553        }
554
555        @Override
556        @ParametricNullness
557        public K getKey() {
558          return node.key;
559        }
560
561        @Override
562        @ParametricNullness
563        public V getValue() {
564          return node.value;
565        }
566
567        @Override
568        @ParametricNullness
569        public V setValue(@ParametricNullness V value) {
570          V oldValue = node.value;
571          int valueHash = smearedHash(value);
572          if (valueHash == node.valueHash && Objects.equals(value, oldValue)) {
573            return value;
574          }
575          checkArgument(seekByValue(value, valueHash) == null, "value already present: %s", value);
576          Node<K, V> newNode = new Node<>(node.key, node.keyHash, value, valueHash);
577          replaceNodeForKey(node, newNode);
578          expectedModCount = modCount;
579          if (Objects.equals(toRemove, node)) {
580            toRemove = newNode;
581          }
582          node = newNode;
583          return oldValue;
584        }
585      }
586    };
587  }
588
589  @Override
590  public void forEach(BiConsumer<? super K, ? super V> action) {
591    checkNotNull(action);
592    for (Node<K, V> node = firstInKeyInsertionOrder;
593        node != null;
594        node = node.nextInKeyInsertionOrder) {
595      action.accept(node.key, node.value);
596    }
597  }
598
599  @Override
600  public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {
601    checkNotNull(function);
602    Node<K, V> oldFirst = firstInKeyInsertionOrder;
603    clear();
604    for (Node<K, V> node = oldFirst; node != null; node = node.nextInKeyInsertionOrder) {
605      put(node.key, function.apply(node.key, node.value));
606    }
607  }
608
609  @LazyInit @RetainedWith private transient @Nullable BiMap<V, K> inverse;
610
611  @Override
612  public BiMap<V, K> inverse() {
613    BiMap<V, K> result = inverse;
614    if (result == null) {
615      result = inverse = new Inverse<>(this);
616    }
617    return result;
618  }
619
620  private static final class Inverse<K extends @Nullable Object, V extends @Nullable Object>
621      extends IteratorBasedAbstractMap<V, K> implements BiMap<V, K>, Serializable {
622    final HashBiMap<K, V> obverse;
623
624    Inverse(HashBiMap<K, V> obverse) {
625      this.obverse = obverse;
626    }
627
628    @Override
629    public int size() {
630      return obverse.size;
631    }
632
633    @Override
634    public void clear() {
635      obverse.clear();
636    }
637
638    @Override
639    public boolean containsKey(@Nullable Object key) {
640      Object obverseValue = key;
641      return obverse.containsValue(obverseValue);
642    }
643
644    @Override
645    public @Nullable K get(@Nullable Object key) {
646      Object obverseValue = key;
647      return keyOrNull(obverse.seekByValue(obverseValue, smearedHash(obverseValue)));
648    }
649
650    @CanIgnoreReturnValue
651    @Override
652    public @Nullable K put(@ParametricNullness V key, @ParametricNullness K value) {
653      K obverseKey = value;
654      V obverseValue = key;
655      return obverse.putInverse(obverseValue, obverseKey, false);
656    }
657
658    @CanIgnoreReturnValue
659    @Override
660    public @Nullable K forcePut(@ParametricNullness V key, @ParametricNullness K value) {
661      K obverseKey = value;
662      V obverseValue = key;
663      return obverse.putInverse(obverseValue, obverseKey, true);
664    }
665
666    @CanIgnoreReturnValue
667    @Override
668    public @Nullable K remove(@Nullable Object key) {
669      Object obverseValue = key;
670      Node<K, V> node = obverse.seekByValue(obverseValue, smearedHash(obverseValue));
671      if (node == null) {
672        return null;
673      }
674      obverse.delete(node);
675      node.prevInKeyInsertionOrder = null;
676      node.nextInKeyInsertionOrder = null;
677      return node.key;
678    }
679
680    @Override
681    public BiMap<K, V> inverse() {
682      return obverse;
683    }
684
685    @Override
686    public Set<V> keySet() {
687      return new InverseKeySet();
688    }
689
690    private final class InverseKeySet extends Maps.KeySet<V, K> {
691      InverseKeySet() {
692        super(Inverse.this);
693      }
694
695      @Override
696      public boolean remove(@Nullable Object o) {
697        Node<K, V> node = obverse.seekByValue(o, smearedHash(o));
698        if (node == null) {
699          return false;
700        } else {
701          obverse.delete(node);
702          return true;
703        }
704      }
705
706      @Override
707      public Iterator<V> iterator() {
708        return new BiIterator<K, V, V>(obverse) {
709          @Override
710          @ParametricNullness
711          V output(Node<K, V> node) {
712            return node.value;
713          }
714        };
715      }
716    }
717
718    @Override
719    public Set<K> values() {
720      return obverse.keySet();
721    }
722
723    @Override
724    Iterator<Entry<V, K>> entryIterator() {
725      return new BiIterator<K, V, Entry<V, K>>(obverse) {
726        @Override
727        Entry<V, K> output(Node<K, V> node) {
728          return new InverseEntry(node);
729        }
730
731        final class InverseEntry extends AbstractMapEntry<V, K> {
732          private Node<K, V> node;
733
734          InverseEntry(Node<K, V> node) {
735            this.node = node;
736          }
737
738          @Override
739          @ParametricNullness
740          public V getKey() {
741            return node.value;
742          }
743
744          @Override
745          @ParametricNullness
746          public K getValue() {
747            return node.key;
748          }
749
750          @Override
751          @ParametricNullness
752          public K setValue(@ParametricNullness K value) {
753            K obverseKey = value;
754            return setObverseKey(obverseKey);
755          }
756
757          @ParametricNullness
758          private K setObverseKey(@ParametricNullness K obverseKey) {
759            int obverseKeyHash = smearedHash(obverseKey);
760            if (obverseKeyHash == node.keyHash && Objects.equals(obverseKey, node.key)) {
761              return obverseKey;
762            }
763            checkArgument(
764                obverse.seekByKey(obverseKey, obverseKeyHash) == null,
765                "value already present: %s",
766                obverseKey);
767            obverse.delete(node);
768            Node<K, V> newNode = new Node<>(obverseKey, obverseKeyHash, node.value, node.valueHash);
769            obverse.insertPlacingAtEndOfIterationOrder(newNode);
770            expectedModCount = obverse.modCount;
771            K oldObverseKey = node.key;
772            if (Objects.equals(toRemove, node)) {
773              toRemove = newNode;
774            }
775            node = newNode;
776            return oldObverseKey;
777          }
778        }
779      };
780    }
781
782    @Override
783    public void forEach(BiConsumer<? super V, ? super K> action) {
784      checkNotNull(action);
785      obverse.forEach((k, v) -> action.accept(v, k));
786    }
787
788    @Override
789    public void replaceAll(BiFunction<? super V, ? super K, ? extends K> function) {
790      checkNotNull(function);
791      Node<K, V> oldFirst = obverse.firstInKeyInsertionOrder;
792      clear();
793      for (Node<K, V> node = oldFirst; node != null; node = node.nextInKeyInsertionOrder) {
794        put(node.value, function.apply(node.value, node.key));
795      }
796    }
797
798    Object writeReplace() {
799      return new InverseSerializedForm<>(obverse);
800    }
801
802    @GwtIncompatible
803    @J2ktIncompatible
804        private void readObject(ObjectInputStream in) throws InvalidObjectException {
805      throw new InvalidObjectException("Use InverseSerializedForm");
806    }
807  }
808
809  private static <K extends @Nullable Object> @Nullable K keyOrNull(@Nullable Node<K, ?> node) {
810    return node == null ? null : node.key;
811  }
812
813  private static <V extends @Nullable Object> @Nullable V valueOrNull(@Nullable Node<?, V> node) {
814    return node == null ? null : node.value;
815  }
816
817  private static final class InverseSerializedForm<
818          K extends @Nullable Object, V extends @Nullable Object>
819      implements Serializable {
820    private final HashBiMap<K, V> bimap;
821
822    InverseSerializedForm(HashBiMap<K, V> bimap) {
823      this.bimap = bimap;
824    }
825
826    Object readResolve() {
827      return bimap.inverse();
828    }
829  }
830
831  /**
832   * @serialData the number of entries, first key, first value, second key, second value, and so on.
833   */
834  @GwtIncompatible
835  @J2ktIncompatible
836    private void writeObject(ObjectOutputStream stream) throws IOException {
837    stream.defaultWriteObject();
838    Serialization.writeMap(this, stream);
839  }
840
841  @GwtIncompatible
842  @J2ktIncompatible
843    private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
844    stream.defaultReadObject();
845    int size = stream.readInt();
846    init(16); // resist hostile attempts to allocate gratuitous heap
847    Serialization.populateMap(this, stream, size);
848  }
849
850  @GwtIncompatible @J2ktIncompatible private static final long serialVersionUID = 0;
851}