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