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