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