1 /*
2 * Copyright (C) 2007 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied. See the License for the specific language governing permissions and limitations under
12 * the License.
13 */
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.base.Preconditions.checkNotNull;
19 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
20 import static com.google.common.collect.CollectPreconditions.checkRemove;
21 import static com.google.common.collect.Hashing.smearedHash;
22
23 import com.google.common.annotations.GwtCompatible;
24 import com.google.common.annotations.GwtIncompatible;
25 import com.google.common.base.Objects;
26 import com.google.common.collect.Maps.IteratorBasedAbstractMap;
27 import com.google.errorprone.annotations.CanIgnoreReturnValue;
28 import com.google.errorprone.annotations.concurrent.LazyInit;
29 import com.google.j2objc.annotations.RetainedWith;
30 import com.google.j2objc.annotations.Weak;
31 import java.io.IOException;
32 import java.io.ObjectInputStream;
33 import java.io.ObjectOutputStream;
34 import java.io.Serializable;
35 import java.util.Arrays;
36 import java.util.ConcurrentModificationException;
37 import java.util.Iterator;
38 import java.util.Map;
39 import java.util.NoSuchElementException;
40 import java.util.Set;
41 import java.util.function.BiConsumer;
42 import java.util.function.BiFunction;
43 import org.checkerframework.checker.nullness.qual.Nullable;
44
45 /**
46 * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
47 * {@code HashBiMap} and its inverse are both serializable.
48 *
49 * <p>This implementation guarantees insertion-based iteration order of its keys.
50 *
51 * <p>See the Guava User Guide article on <a href=
52 * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap"> {@code BiMap} </a>.
53 *
54 * @author Louis Wasserman
55 * @author Mike Bostock
56 * @since 2.0
57 */
58 @GwtCompatible(emulated = true)
59 public final class HashBiMap<K, V> extends IteratorBasedAbstractMap<K, V>
60 implements BiMap<K, V>, Serializable {
61
62 /** Returns a new, empty {@code HashBiMap} with the default initial capacity (16). */
63 public static <K, V> HashBiMap<K, V> create() {
64 return create(16);
65 }
66
67 /**
68 * Constructs a new, empty bimap with the specified expected size.
69 *
70 * @param expectedSize the expected number of entries
71 * @throws IllegalArgumentException if the specified expected size is negative
72 */
73 public static <K, V> HashBiMap<K, V> create(int expectedSize) {
74 return new HashBiMap<>(expectedSize);
75 }
76
77 /**
78 * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
79 * initial capacity sufficient to hold the mappings in the specified map.
80 */
81 public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
82 HashBiMap<K, V> bimap = create(map.size());
83 bimap.putAll(map);
84 return bimap;
85 }
86
87 private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
88 final int keyHash;
89 final int valueHash;
90
91 // All BiEntry instances are strongly reachable from owning HashBiMap through
92 // "HashBiMap.hashTableKToV" and "BiEntry.nextInKToVBucket" references.
93 // Under that assumption, the remaining references can be safely marked as @Weak.
94 // Using @Weak is necessary to avoid retain-cycles between BiEntry instances on iOS,
95 // which would cause memory leaks when non-empty HashBiMap with cyclic BiEntry
96 // instances is deallocated.
97 @Nullable BiEntry<K, V> nextInKToVBucket;
98 @Weak @Nullable BiEntry<K, V> nextInVToKBucket;
99
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 }