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 @Override 248 public boolean containsValue(@Nullable Object value) { 249 return seekByValue(value, smearedHash(value)) != null; 250 } 251 252 @Override 253 public @Nullable V get(@Nullable Object key) { 254 return Maps.valueOrNull(seekByKey(key, smearedHash(key))); 255 } 256 257 @CanIgnoreReturnValue 258 @Override 259 public V put(@Nullable K key, @Nullable V value) { 260 return put(key, value, false); 261 } 262 263 private V put(@Nullable K key, @Nullable V value, boolean force) { 264 int keyHash = smearedHash(key); 265 int valueHash = smearedHash(value); 266 267 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 268 if (oldEntryForKey != null 269 && valueHash == oldEntryForKey.valueHash 270 && Objects.equal(value, oldEntryForKey.value)) { 271 return value; 272 } 273 274 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 275 if (oldEntryForValue != null) { 276 if (force) { 277 delete(oldEntryForValue); 278 } else { 279 throw new IllegalArgumentException("value already present: " + value); 280 } 281 } 282 283 BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash); 284 if (oldEntryForKey != null) { 285 delete(oldEntryForKey); 286 insert(newEntry, oldEntryForKey); 287 oldEntryForKey.prevInKeyInsertionOrder = null; 288 oldEntryForKey.nextInKeyInsertionOrder = null; 289 return oldEntryForKey.value; 290 } else { 291 insert(newEntry, null); 292 rehashIfNecessary(); 293 return null; 294 } 295 } 296 297 @CanIgnoreReturnValue 298 @Override 299 @Nullable 300 public V forcePut(@Nullable K key, @Nullable V value) { 301 return put(key, value, true); 302 } 303 304 private @Nullable K putInverse(@Nullable V value, @Nullable K key, boolean force) { 305 int valueHash = smearedHash(value); 306 int keyHash = smearedHash(key); 307 308 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash); 309 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash); 310 if (oldEntryForValue != null 311 && keyHash == oldEntryForValue.keyHash 312 && Objects.equal(key, oldEntryForValue.key)) { 313 return key; 314 } else if (oldEntryForKey != null && !force) { 315 throw new IllegalArgumentException("key already present: " + key); 316 } 317 318 /* 319 * The ordering here is important: if we deleted the key entry and then the value entry, 320 * the key entry's prev or next pointer might point to the dead value entry, and when we 321 * put the new entry in the key entry's position in iteration order, it might invalidate 322 * the linked list. 323 */ 324 325 if (oldEntryForValue != null) { 326 delete(oldEntryForValue); 327 } 328 329 if (oldEntryForKey != null) { 330 delete(oldEntryForKey); 331 } 332 333 BiEntry<K, V> newEntry = new BiEntry<>(key, keyHash, value, valueHash); 334 insert(newEntry, oldEntryForKey); 335 336 if (oldEntryForKey != null) { 337 oldEntryForKey.prevInKeyInsertionOrder = null; 338 oldEntryForKey.nextInKeyInsertionOrder = null; 339 } 340 if (oldEntryForValue != null) { 341 oldEntryForValue.prevInKeyInsertionOrder = null; 342 oldEntryForValue.nextInKeyInsertionOrder = null; 343 } 344 rehashIfNecessary(); 345 return Maps.keyOrNull(oldEntryForValue); 346 } 347 348 private void rehashIfNecessary() { 349 BiEntry<K, V>[] oldKToV = hashTableKToV; 350 if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) { 351 int newTableSize = oldKToV.length * 2; 352 353 this.hashTableKToV = createTable(newTableSize); 354 this.hashTableVToK = createTable(newTableSize); 355 this.mask = newTableSize - 1; 356 this.size = 0; 357 358 for (BiEntry<K, V> entry = firstInKeyInsertionOrder; 359 entry != null; 360 entry = entry.nextInKeyInsertionOrder) { 361 insert(entry, entry); 362 } 363 this.modCount++; 364 } 365 } 366 367 @SuppressWarnings("unchecked") 368 private BiEntry<K, V>[] createTable(int length) { 369 return new BiEntry[length]; 370 } 371 372 @CanIgnoreReturnValue 373 @Override 374 @Nullable 375 public V remove(@Nullable Object key) { 376 BiEntry<K, V> entry = seekByKey(key, smearedHash(key)); 377 if (entry == null) { 378 return null; 379 } else { 380 delete(entry); 381 entry.prevInKeyInsertionOrder = null; 382 entry.nextInKeyInsertionOrder = null; 383 return entry.value; 384 } 385 } 386 387 @Override 388 public void clear() { 389 size = 0; 390 Arrays.fill(hashTableKToV, null); 391 Arrays.fill(hashTableVToK, null); 392 firstInKeyInsertionOrder = null; 393 lastInKeyInsertionOrder = null; 394 modCount++; 395 } 396 397 @Override 398 public int size() { 399 return size; 400 } 401 402 abstract class Itr<T> implements Iterator<T> { 403 BiEntry<K, V> next = firstInKeyInsertionOrder; 404 BiEntry<K, V> toRemove = null; 405 int expectedModCount = modCount; 406 int remaining = size(); 407 408 @Override 409 public boolean hasNext() { 410 if (modCount != expectedModCount) { 411 throw new ConcurrentModificationException(); 412 } 413 return next != null && remaining > 0; 414 } 415 416 @Override 417 public T next() { 418 if (!hasNext()) { 419 throw new NoSuchElementException(); 420 } 421 422 BiEntry<K, V> entry = next; 423 next = entry.nextInKeyInsertionOrder; 424 toRemove = entry; 425 remaining--; 426 return output(entry); 427 } 428 429 @Override 430 public void remove() { 431 if (modCount != expectedModCount) { 432 throw new ConcurrentModificationException(); 433 } 434 checkRemove(toRemove != null); 435 delete(toRemove); 436 expectedModCount = modCount; 437 toRemove = null; 438 } 439 440 abstract T output(BiEntry<K, V> entry); 441 } 442 443 @Override 444 public Set<K> keySet() { 445 return new KeySet(); 446 } 447 448 @WeakOuter 449 private final class KeySet extends Maps.KeySet<K, V> { 450 KeySet() { 451 super(HashBiMap.this); 452 } 453 454 @Override 455 public Iterator<K> iterator() { 456 return new Itr<K>() { 457 @Override 458 K output(BiEntry<K, V> entry) { 459 return entry.key; 460 } 461 }; 462 } 463 464 @Override 465 public boolean remove(@Nullable Object o) { 466 BiEntry<K, V> entry = seekByKey(o, smearedHash(o)); 467 if (entry == null) { 468 return false; 469 } else { 470 delete(entry); 471 entry.prevInKeyInsertionOrder = null; 472 entry.nextInKeyInsertionOrder = null; 473 return true; 474 } 475 } 476 } 477 478 @Override 479 public Set<V> values() { 480 return inverse().keySet(); 481 } 482 483 @Override 484 Iterator<Entry<K, V>> entryIterator() { 485 return new Itr<Entry<K, V>>() { 486 @Override 487 Entry<K, V> output(BiEntry<K, V> entry) { 488 return new MapEntry(entry); 489 } 490 491 class MapEntry extends AbstractMapEntry<K, V> { 492 BiEntry<K, V> delegate; 493 494 MapEntry(BiEntry<K, V> entry) { 495 this.delegate = entry; 496 } 497 498 @Override 499 public K getKey() { 500 return delegate.key; 501 } 502 503 @Override 504 public V getValue() { 505 return delegate.value; 506 } 507 508 @Override 509 public V setValue(V value) { 510 V oldValue = delegate.value; 511 int valueHash = smearedHash(value); 512 if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) { 513 return value; 514 } 515 checkArgument(seekByValue(value, valueHash) == null, "value already present: %s", value); 516 delete(delegate); 517 BiEntry<K, V> newEntry = new BiEntry<>(delegate.key, delegate.keyHash, value, valueHash); 518 insert(newEntry, delegate); 519 delegate.prevInKeyInsertionOrder = null; 520 delegate.nextInKeyInsertionOrder = null; 521 expectedModCount = modCount; 522 if (toRemove == delegate) { 523 toRemove = newEntry; 524 } 525 delegate = newEntry; 526 return oldValue; 527 } 528 } 529 }; 530 } 531 532 @Override 533 public void forEach(BiConsumer<? super K, ? super V> action) { 534 checkNotNull(action); 535 for (BiEntry<K, V> entry = firstInKeyInsertionOrder; 536 entry != null; 537 entry = entry.nextInKeyInsertionOrder) { 538 action.accept(entry.key, entry.value); 539 } 540 } 541 542 @Override 543 public void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) { 544 checkNotNull(function); 545 BiEntry<K, V> oldFirst = firstInKeyInsertionOrder; 546 clear(); 547 for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) { 548 put(entry.key, function.apply(entry.key, entry.value)); 549 } 550 } 551 552 @MonotonicNonNull @RetainedWith private transient BiMap<V, K> inverse; 553 554 @Override 555 public BiMap<V, K> inverse() { 556 BiMap<V, K> result = inverse; 557 return (result == null) ? inverse = new Inverse() : result; 558 } 559 560 private final class Inverse extends IteratorBasedAbstractMap<V, K> 561 implements BiMap<V, K>, Serializable { 562 BiMap<K, V> forward() { 563 return HashBiMap.this; 564 } 565 566 @Override 567 public int size() { 568 return size; 569 } 570 571 @Override 572 public void clear() { 573 forward().clear(); 574 } 575 576 @Override 577 public boolean containsKey(@Nullable Object value) { 578 return forward().containsValue(value); 579 } 580 581 @Override 582 public K get(@Nullable Object value) { 583 return Maps.keyOrNull(seekByValue(value, smearedHash(value))); 584 } 585 586 @CanIgnoreReturnValue 587 @Override 588 @Nullable 589 public K put(@Nullable V value, @Nullable K key) { 590 return putInverse(value, key, false); 591 } 592 593 @Override 594 @Nullable 595 public K forcePut(@Nullable V value, @Nullable K key) { 596 return putInverse(value, key, true); 597 } 598 599 @Override 600 @Nullable 601 public K remove(@Nullable Object value) { 602 BiEntry<K, V> entry = seekByValue(value, smearedHash(value)); 603 if (entry == null) { 604 return null; 605 } else { 606 delete(entry); 607 entry.prevInKeyInsertionOrder = null; 608 entry.nextInKeyInsertionOrder = null; 609 return entry.key; 610 } 611 } 612 613 @Override 614 public BiMap<K, V> inverse() { 615 return forward(); 616 } 617 618 @Override 619 public Set<V> keySet() { 620 return new InverseKeySet(); 621 } 622 623 @WeakOuter 624 private final class InverseKeySet extends Maps.KeySet<V, K> { 625 InverseKeySet() { 626 super(Inverse.this); 627 } 628 629 @Override 630 public boolean remove(@Nullable Object o) { 631 BiEntry<K, V> entry = seekByValue(o, smearedHash(o)); 632 if (entry == null) { 633 return false; 634 } else { 635 delete(entry); 636 return true; 637 } 638 } 639 640 @Override 641 public Iterator<V> iterator() { 642 return new Itr<V>() { 643 @Override 644 V output(BiEntry<K, V> entry) { 645 return entry.value; 646 } 647 }; 648 } 649 } 650 651 @Override 652 public Set<K> values() { 653 return forward().keySet(); 654 } 655 656 @Override 657 Iterator<Entry<V, K>> entryIterator() { 658 return new Itr<Entry<V, K>>() { 659 @Override 660 Entry<V, K> output(BiEntry<K, V> entry) { 661 return new InverseEntry(entry); 662 } 663 664 class InverseEntry extends AbstractMapEntry<V, K> { 665 BiEntry<K, V> delegate; 666 667 InverseEntry(BiEntry<K, V> entry) { 668 this.delegate = entry; 669 } 670 671 @Override 672 public V getKey() { 673 return delegate.value; 674 } 675 676 @Override 677 public K getValue() { 678 return delegate.key; 679 } 680 681 @Override 682 public K setValue(K key) { 683 K oldKey = delegate.key; 684 int keyHash = smearedHash(key); 685 if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) { 686 return key; 687 } 688 checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key); 689 delete(delegate); 690 BiEntry<K, V> newEntry = 691 new BiEntry<>(key, keyHash, delegate.value, delegate.valueHash); 692 delegate = newEntry; 693 insert(newEntry, null); 694 expectedModCount = modCount; 695 return oldKey; 696 } 697 } 698 }; 699 } 700 701 @Override 702 public void forEach(BiConsumer<? super V, ? super K> action) { 703 checkNotNull(action); 704 HashBiMap.this.forEach((k, v) -> action.accept(v, k)); 705 } 706 707 @Override 708 public void replaceAll(BiFunction<? super V, ? super K, ? extends K> function) { 709 checkNotNull(function); 710 BiEntry<K, V> oldFirst = firstInKeyInsertionOrder; 711 clear(); 712 for (BiEntry<K, V> entry = oldFirst; entry != null; entry = entry.nextInKeyInsertionOrder) { 713 put(entry.value, function.apply(entry.value, entry.key)); 714 } 715 } 716 717 Object writeReplace() { 718 return new InverseSerializedForm<>(HashBiMap.this); 719 } 720 } 721 722 private static final class InverseSerializedForm<K, V> implements Serializable { 723 private final HashBiMap<K, V> bimap; 724 725 InverseSerializedForm(HashBiMap<K, V> bimap) { 726 this.bimap = bimap; 727 } 728 729 Object readResolve() { 730 return bimap.inverse(); 731 } 732 } 733 734 /** 735 * @serialData the number of entries, first key, first value, second key, second value, and so on. 736 */ 737 @GwtIncompatible // java.io.ObjectOutputStream 738 private void writeObject(ObjectOutputStream stream) throws IOException { 739 stream.defaultWriteObject(); 740 Serialization.writeMap(this, stream); 741 } 742 743 @GwtIncompatible // java.io.ObjectInputStream 744 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException { 745 stream.defaultReadObject(); 746 int size = Serialization.readCount(stream); 747 init(16); // resist hostile attempts to allocate gratuitous heap 748 Serialization.populateMap(this, stream, size); 749 } 750 751 @GwtIncompatible // Not needed in emulated source 752 private static final long serialVersionUID = 0; 753}