1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package com.google.common.collect;
16
17 import static com.google.common.base.Preconditions.checkArgument;
18 import static com.google.common.collect.CollectPreconditions.checkNonnegative;
19 import static com.google.common.collect.CollectPreconditions.checkRemove;
20
21 import com.google.common.annotations.GwtCompatible;
22 import com.google.common.annotations.GwtIncompatible;
23 import com.google.common.base.Objects;
24
25 import java.io.IOException;
26 import java.io.ObjectInputStream;
27 import java.io.ObjectOutputStream;
28 import java.io.Serializable;
29 import java.util.AbstractMap;
30 import java.util.Arrays;
31 import java.util.ConcurrentModificationException;
32 import java.util.Iterator;
33 import java.util.Map;
34 import java.util.NoSuchElementException;
35 import java.util.Set;
36
37 import javax.annotation.Nullable;
38
39
40
41
42
43
44
45
46
47
48
49
50
51 @GwtCompatible(emulated = true)
52 public final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K, V>, Serializable {
53
54
55
56
57 public static <K, V> HashBiMap<K, V> create() {
58 return create(16);
59 }
60
61
62
63
64
65
66
67 public static <K, V> HashBiMap<K, V> create(int expectedSize) {
68 return new HashBiMap<K, V>(expectedSize);
69 }
70
71
72
73
74
75 public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
76 HashBiMap<K, V> bimap = create(map.size());
77 bimap.putAll(map);
78 return bimap;
79 }
80
81 private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
82 final int keyHash;
83 final int valueHash;
84
85 @Nullable
86 BiEntry<K, V> nextInKToVBucket;
87
88 @Nullable
89 BiEntry<K, V> nextInVToKBucket;
90
91 BiEntry(K key, int keyHash, V value, int valueHash) {
92 super(key, value);
93 this.keyHash = keyHash;
94 this.valueHash = valueHash;
95 }
96 }
97
98 private static final double LOAD_FACTOR = 1.0;
99
100 private transient BiEntry<K, V>[] hashTableKToV;
101 private transient BiEntry<K, V>[] hashTableVToK;
102 private transient int size;
103 private transient int mask;
104 private transient int modCount;
105
106 private HashBiMap(int expectedSize) {
107 init(expectedSize);
108 }
109
110 private void init(int expectedSize) {
111 checkNonnegative(expectedSize, "expectedSize");
112 int tableSize = Hashing.closedTableSize(expectedSize, LOAD_FACTOR);
113 this.hashTableKToV = createTable(tableSize);
114 this.hashTableVToK = createTable(tableSize);
115 this.mask = tableSize - 1;
116 this.modCount = 0;
117 this.size = 0;
118 }
119
120
121
122
123
124 private void delete(BiEntry<K, V> entry) {
125 int keyBucket = entry.keyHash & mask;
126 BiEntry<K, V> prevBucketEntry = null;
127 for (BiEntry<K, V> bucketEntry = hashTableKToV[keyBucket]; true;
128 bucketEntry = bucketEntry.nextInKToVBucket) {
129 if (bucketEntry == entry) {
130 if (prevBucketEntry == null) {
131 hashTableKToV[keyBucket] = entry.nextInKToVBucket;
132 } else {
133 prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
134 }
135 break;
136 }
137 prevBucketEntry = bucketEntry;
138 }
139
140 int valueBucket = entry.valueHash & mask;
141 prevBucketEntry = null;
142 for (BiEntry<K, V> bucketEntry = hashTableVToK[valueBucket];;
143 bucketEntry = bucketEntry.nextInVToKBucket) {
144 if (bucketEntry == entry) {
145 if (prevBucketEntry == null) {
146 hashTableVToK[valueBucket] = entry.nextInVToKBucket;
147 } else {
148 prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
149 }
150 break;
151 }
152 prevBucketEntry = bucketEntry;
153 }
154
155 size--;
156 modCount++;
157 }
158
159 private void insert(BiEntry<K, V> entry) {
160 int keyBucket = entry.keyHash & mask;
161 entry.nextInKToVBucket = hashTableKToV[keyBucket];
162 hashTableKToV[keyBucket] = entry;
163
164 int valueBucket = entry.valueHash & mask;
165 entry.nextInVToKBucket = hashTableVToK[valueBucket];
166 hashTableVToK[valueBucket] = entry;
167
168 size++;
169 modCount++;
170 }
171
172 private static int hash(@Nullable Object o) {
173 return Hashing.smear((o == null) ? 0 : o.hashCode());
174 }
175
176 private BiEntry<K, V> seekByKey(@Nullable Object key, int keyHash) {
177 for (BiEntry<K, V> entry = hashTableKToV[keyHash & mask]; entry != null;
178 entry = entry.nextInKToVBucket) {
179 if (keyHash == entry.keyHash && Objects.equal(key, entry.key)) {
180 return entry;
181 }
182 }
183 return null;
184 }
185
186 private BiEntry<K, V> seekByValue(@Nullable Object value, int valueHash) {
187 for (BiEntry<K, V> entry = hashTableVToK[valueHash & mask]; entry != null;
188 entry = entry.nextInVToKBucket) {
189 if (valueHash == entry.valueHash && Objects.equal(value, entry.value)) {
190 return entry;
191 }
192 }
193 return null;
194 }
195
196 @Override
197 public boolean containsKey(@Nullable Object key) {
198 return seekByKey(key, hash(key)) != null;
199 }
200
201 @Override
202 public boolean containsValue(@Nullable Object value) {
203 return seekByValue(value, hash(value)) != null;
204 }
205
206 @Nullable
207 @Override
208 public V get(@Nullable Object key) {
209 BiEntry<K, V> entry = seekByKey(key, hash(key));
210 return (entry == null) ? null : entry.value;
211 }
212
213 @Override
214 public V put(@Nullable K key, @Nullable V value) {
215 return put(key, value, false);
216 }
217
218 @Override
219 public V forcePut(@Nullable K key, @Nullable V value) {
220 return put(key, value, true);
221 }
222
223 private V put(@Nullable K key, @Nullable V value, boolean force) {
224 int keyHash = hash(key);
225 int valueHash = hash(value);
226
227 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
228 if (oldEntryForKey != null && valueHash == oldEntryForKey.valueHash
229 && Objects.equal(value, oldEntryForKey.value)) {
230 return value;
231 }
232
233 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
234 if (oldEntryForValue != null) {
235 if (force) {
236 delete(oldEntryForValue);
237 } else {
238 throw new IllegalArgumentException("value already present: " + value);
239 }
240 }
241
242 if (oldEntryForKey != null) {
243 delete(oldEntryForKey);
244 }
245 BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
246 insert(newEntry);
247 rehashIfNecessary();
248 return (oldEntryForKey == null) ? null : oldEntryForKey.value;
249 }
250
251 @Nullable
252 private K putInverse(@Nullable V value, @Nullable K key, boolean force) {
253 int valueHash = hash(value);
254 int keyHash = hash(key);
255
256 BiEntry<K, V> oldEntryForValue = seekByValue(value, valueHash);
257 if (oldEntryForValue != null && keyHash == oldEntryForValue.keyHash
258 && Objects.equal(key, oldEntryForValue.key)) {
259 return key;
260 }
261
262 BiEntry<K, V> oldEntryForKey = seekByKey(key, keyHash);
263 if (oldEntryForKey != null) {
264 if (force) {
265 delete(oldEntryForKey);
266 } else {
267 throw new IllegalArgumentException("value already present: " + key);
268 }
269 }
270
271 if (oldEntryForValue != null) {
272 delete(oldEntryForValue);
273 }
274 BiEntry<K, V> newEntry = new BiEntry<K, V>(key, keyHash, value, valueHash);
275 insert(newEntry);
276 rehashIfNecessary();
277 return (oldEntryForValue == null) ? null : oldEntryForValue.key;
278 }
279
280 private void rehashIfNecessary() {
281 BiEntry<K, V>[] oldKToV = hashTableKToV;
282 if (Hashing.needsResizing(size, oldKToV.length, LOAD_FACTOR)) {
283 int newTableSize = oldKToV.length * 2;
284
285 this.hashTableKToV = createTable(newTableSize);
286 this.hashTableVToK = createTable(newTableSize);
287 this.mask = newTableSize - 1;
288 this.size = 0;
289
290 for (int bucket = 0; bucket < oldKToV.length; bucket++) {
291 BiEntry<K, V> entry = oldKToV[bucket];
292 while (entry != null) {
293 BiEntry<K, V> nextEntry = entry.nextInKToVBucket;
294 insert(entry);
295 entry = nextEntry;
296 }
297 }
298 this.modCount++;
299 }
300 }
301
302 @SuppressWarnings("unchecked")
303 private BiEntry<K, V>[] createTable(int length) {
304 return new BiEntry[length];
305 }
306
307 @Override
308 public V remove(@Nullable Object key) {
309 BiEntry<K, V> entry = seekByKey(key, hash(key));
310 if (entry == null) {
311 return null;
312 } else {
313 delete(entry);
314 return entry.value;
315 }
316 }
317
318 @Override
319 public void clear() {
320 size = 0;
321 Arrays.fill(hashTableKToV, null);
322 Arrays.fill(hashTableVToK, null);
323 modCount++;
324 }
325
326 @Override
327 public int size() {
328 return size;
329 }
330
331 abstract class Itr<T> implements Iterator<T> {
332 int nextBucket = 0;
333 BiEntry<K, V> next = null;
334 BiEntry<K, V> toRemove = null;
335 int expectedModCount = modCount;
336
337 private void checkForConcurrentModification() {
338 if (modCount != expectedModCount) {
339 throw new ConcurrentModificationException();
340 }
341 }
342
343 @Override
344 public boolean hasNext() {
345 checkForConcurrentModification();
346 if (next != null) {
347 return true;
348 }
349 while (nextBucket < hashTableKToV.length) {
350 if (hashTableKToV[nextBucket] != null) {
351 next = hashTableKToV[nextBucket++];
352 return true;
353 }
354 nextBucket++;
355 }
356 return false;
357 }
358
359 @Override
360 public T next() {
361 checkForConcurrentModification();
362 if (!hasNext()) {
363 throw new NoSuchElementException();
364 }
365
366 BiEntry<K, V> entry = next;
367 next = entry.nextInKToVBucket;
368 toRemove = entry;
369 return output(entry);
370 }
371
372 @Override
373 public void remove() {
374 checkForConcurrentModification();
375 checkRemove(toRemove != null);
376 delete(toRemove);
377 expectedModCount = modCount;
378 toRemove = null;
379 }
380
381 abstract T output(BiEntry<K, V> entry);
382 }
383
384 @Override
385 public Set<K> keySet() {
386 return new KeySet();
387 }
388
389 private final class KeySet extends Maps.KeySet<K, V> {
390 KeySet() {
391 super(HashBiMap.this);
392 }
393
394 @Override
395 public Iterator<K> iterator() {
396 return new Itr<K>() {
397 @Override
398 K output(BiEntry<K, V> entry) {
399 return entry.key;
400 }
401 };
402 }
403
404 @Override
405 public boolean remove(@Nullable Object o) {
406 BiEntry<K, V> entry = seekByKey(o, hash(o));
407 if (entry == null) {
408 return false;
409 } else {
410 delete(entry);
411 return true;
412 }
413 }
414 }
415
416 @Override
417 public Set<V> values() {
418 return inverse().keySet();
419 }
420
421 @Override
422 public Set<Entry<K, V>> entrySet() {
423 return new EntrySet();
424 }
425
426 private final class EntrySet extends Maps.EntrySet<K, V> {
427 @Override
428 Map<K, V> map() {
429 return HashBiMap.this;
430 }
431
432 @Override
433 public Iterator<Entry<K, V>> iterator() {
434 return new Itr<Entry<K, V>>() {
435 @Override
436 Entry<K, V> output(BiEntry<K, V> entry) {
437 return new MapEntry(entry);
438 }
439
440 class MapEntry extends AbstractMapEntry<K, V> {
441 BiEntry<K, V> delegate;
442
443 MapEntry(BiEntry<K, V> entry) {
444 this.delegate = entry;
445 }
446
447 @Override public K getKey() {
448 return delegate.key;
449 }
450
451 @Override public V getValue() {
452 return delegate.value;
453 }
454
455 @Override public V setValue(V value) {
456 V oldValue = delegate.value;
457 int valueHash = hash(value);
458 if (valueHash == delegate.valueHash && Objects.equal(value, oldValue)) {
459 return value;
460 }
461 checkArgument(
462 seekByValue(value, valueHash) == null, "value already present: %s", value);
463 delete(delegate);
464 BiEntry<K, V> newEntry =
465 new BiEntry<K, V>(delegate.key, delegate.keyHash, value, valueHash);
466 insert(newEntry);
467 expectedModCount = modCount;
468 if (toRemove == delegate) {
469 toRemove = newEntry;
470 }
471 delegate = newEntry;
472 return oldValue;
473 }
474 }
475 };
476 }
477 }
478
479 private transient BiMap<V, K> inverse;
480
481 @Override
482 public BiMap<V, K> inverse() {
483 return (inverse == null) ? inverse = new Inverse() : inverse;
484 }
485
486 private final class Inverse extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
487 BiMap<K, V> forward() {
488 return HashBiMap.this;
489 }
490
491 @Override
492 public int size() {
493 return size;
494 }
495
496 @Override
497 public void clear() {
498 forward().clear();
499 }
500
501 @Override
502 public boolean containsKey(@Nullable Object value) {
503 return forward().containsValue(value);
504 }
505
506 @Override
507 public K get(@Nullable Object value) {
508 BiEntry<K, V> entry = seekByValue(value, hash(value));
509 return (entry == null) ? null : entry.key;
510 }
511
512 @Override
513 public K put(@Nullable V value, @Nullable K key) {
514 return putInverse(value, key, false);
515 }
516
517 @Override
518 public K forcePut(@Nullable V value, @Nullable K key) {
519 return putInverse(value, key, true);
520 }
521
522 @Override
523 public K remove(@Nullable Object value) {
524 BiEntry<K, V> entry = seekByValue(value, hash(value));
525 if (entry == null) {
526 return null;
527 } else {
528 delete(entry);
529 return entry.key;
530 }
531 }
532
533 @Override
534 public BiMap<K, V> inverse() {
535 return forward();
536 }
537
538 @Override
539 public Set<V> keySet() {
540 return new InverseKeySet();
541 }
542
543 private final class InverseKeySet extends Maps.KeySet<V, K> {
544 InverseKeySet() {
545 super(Inverse.this);
546 }
547
548 @Override
549 public boolean remove(@Nullable Object o) {
550 BiEntry<K, V> entry = seekByValue(o, hash(o));
551 if (entry == null) {
552 return false;
553 } else {
554 delete(entry);
555 return true;
556 }
557 }
558
559 @Override
560 public Iterator<V> iterator() {
561 return new Itr<V>() {
562 @Override V output(BiEntry<K, V> entry) {
563 return entry.value;
564 }
565 };
566 }
567 }
568
569 @Override
570 public Set<K> values() {
571 return forward().keySet();
572 }
573
574 @Override
575 public Set<Entry<V, K>> entrySet() {
576 return new Maps.EntrySet<V, K>() {
577
578 @Override
579 Map<V, K> map() {
580 return Inverse.this;
581 }
582
583 @Override
584 public Iterator<Entry<V, K>> iterator() {
585 return new Itr<Entry<V, K>>() {
586 @Override
587 Entry<V, K> output(BiEntry<K, V> entry) {
588 return new InverseEntry(entry);
589 }
590
591 class InverseEntry extends AbstractMapEntry<V, K> {
592 BiEntry<K, V> delegate;
593
594 InverseEntry(BiEntry<K, V> entry) {
595 this.delegate = entry;
596 }
597
598 @Override
599 public V getKey() {
600 return delegate.value;
601 }
602
603 @Override
604 public K getValue() {
605 return delegate.key;
606 }
607
608 @Override
609 public K setValue(K key) {
610 K oldKey = delegate.key;
611 int keyHash = hash(key);
612 if (keyHash == delegate.keyHash && Objects.equal(key, oldKey)) {
613 return key;
614 }
615 checkArgument(seekByKey(key, keyHash) == null, "value already present: %s", key);
616 delete(delegate);
617 BiEntry<K, V> newEntry =
618 new BiEntry<K, V>(key, keyHash, delegate.value, delegate.valueHash);
619 insert(newEntry);
620 expectedModCount = modCount;
621
622
623 return oldKey;
624 }
625 }
626 };
627 }
628 };
629 }
630
631 Object writeReplace() {
632 return new InverseSerializedForm<K, V>(HashBiMap.this);
633 }
634 }
635
636 private static final class InverseSerializedForm<K, V> implements Serializable {
637 private final HashBiMap<K, V> bimap;
638
639 InverseSerializedForm(HashBiMap<K, V> bimap) {
640 this.bimap = bimap;
641 }
642
643 Object readResolve() {
644 return bimap.inverse();
645 }
646 }
647
648
649
650
651 @GwtIncompatible("java.io.ObjectOutputStream")
652 private void writeObject(ObjectOutputStream stream) throws IOException {
653 stream.defaultWriteObject();
654 Serialization.writeMap(this, stream);
655 }
656
657 @GwtIncompatible("java.io.ObjectInputStream")
658 private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException {
659 stream.defaultReadObject();
660 int size = Serialization.readCount(stream);
661 init(size);
662 Serialization.populateMap(this, stream, size);
663 }
664
665 @GwtIncompatible("Not needed in emulated source")
666 private static final long serialVersionUID = 0;
667 }