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}