View Javadoc
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.j2objc.annotations.RetainedWith;
29  import com.google.j2objc.annotations.WeakOuter;
30  import java.io.IOException;
31  import java.io.ObjectInputStream;
32  import java.io.ObjectOutputStream;
33  import java.io.Serializable;
34  import java.util.Arrays;
35  import java.util.ConcurrentModificationException;
36  import java.util.Iterator;
37  import java.util.Map;
38  import java.util.NoSuchElementException;
39  import java.util.Set;
40  import java.util.function.BiConsumer;
41  import java.util.function.BiFunction;
42  import javax.annotation.Nullable;
43  
44  /**
45   * A {@link BiMap} backed by two hash tables. This implementation allows null keys and values. A
46   * {@code HashBiMap} and its inverse are both serializable.
47   *
48   * <p>This implementation guarantees insertion-based iteration order of its keys.
49   *
50   * <p>See the Guava User Guide article on <a href=
51   * "https://github.com/google/guava/wiki/NewCollectionTypesExplained#bimap"> {@code BiMap} </a>.
52   *
53   * @author Louis Wasserman
54   * @author Mike Bostock
55   * @since 2.0
56   */
57  @GwtCompatible(emulated = true)
58  public final class HashBiMap<K, V> extends IteratorBasedAbstractMap<K, V>
59      implements BiMap<K, V>, Serializable {
60  
61    /**
62     * Returns a new, empty {@code HashBiMap} with the default initial capacity (16).
63     */
64    public static <K, V> HashBiMap<K, V> create() {
65      return create(16);
66    }
67  
68    /**
69     * Constructs a new, empty bimap with the specified expected size.
70     *
71     * @param expectedSize the expected number of entries
72     * @throws IllegalArgumentException if the specified expected size is negative
73     */
74    public static <K, V> HashBiMap<K, V> create(int expectedSize) {
75      return new HashBiMap<>(expectedSize);
76    }
77  
78    /**
79     * Constructs a new bimap containing initial values from {@code map}. The bimap is created with an
80     * initial capacity sufficient to hold the mappings in the specified map.
81     */
82    public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
83      HashBiMap<K, V> bimap = create(map.size());
84      bimap.putAll(map);
85      return bimap;
86    }
87  
88    private static final class BiEntry<K, V> extends ImmutableEntry<K, V> {
89      final int keyHash;
90      final int valueHash;
91  
92      @Nullable BiEntry<K, V> nextInKToVBucket;
93      @Nullable BiEntry<K, V> nextInVToKBucket;
94  
95      @Nullable BiEntry<K, V> nextInKeyInsertionOrder;
96      @Nullable BiEntry<K, V> prevInKeyInsertionOrder;
97  
98      BiEntry(K key, int keyHash, V value, int valueHash) {
99        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 }