Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   * Copyright (C) 2007 The Guava Authors
   *
   * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
   * in compliance with the License. You may obtain a copy of the License at
   *
   * http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software distributed under the License
  * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
  * or implied. See the License for the specific language governing permissions and limitations under
  * the License.
  */
 
 package com.google.common.collect;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static com.google.common.base.Preconditions.checkState;
 
 
 import java.util.Map;
 import java.util.Set;
 
 import  javax.annotation.Nullable;

A BiMap backed by two hash tables. This implementation allows null keys and values. A HashBiMap and its inverse are both serializable.

See the Guava User Guide article on BiMap .

Author(s):
Louis Wasserman
Mike Bostock
Since:
2.0 (imported from Google Collections Library)
 
 @GwtCompatible(emulated = true)
 public final class HashBiMap<K, V> extends AbstractMap<K, V> implements BiMap<K, V>, Serializable {

  
Returns a new, empty HashBiMap with the default initial capacity (16).
 
   public static <K, V> HashBiMap<K, V> create() {
     return create(16);
   }

  
Constructs a new, empty bimap with the specified expected size.

Parameters:
expectedSize the expected number of entries
Throws:
IllegalArgumentException if the specified expected size is negative
 
   public static <K, V> HashBiMap<K, V> create(int expectedSize) {
     return new HashBiMap<K, V>(expectedSize);
   }

  
Constructs a new bimap containing initial values from map. The bimap is created with an initial capacity sufficient to hold the mappings in the specified map.
 
   public static <K, V> HashBiMap<K, V> create(Map<? extends K, ? extends V> map) {
     HashBiMap<K, V> bimap = create(map.size());
     bimap.putAll(map);
     return bimap;
   }
 
   private static final class BiEntry<K, V> {
     final K key;
     final int keyHash;
 
     final V value;
     final int valueHash;
 
     @Nullable
     BiEntry<K, V> nextInKToVBucket;
 
     @Nullable
     BiEntry<K, V> nextInVToKBucket;
 
     BiEntry(K keyint keyHash, V valueint valueHash) {
       this. = key;
       this. = keyHash;
       this. = value;
       this. = valueHash;
     }
   }
  private static final double LOAD_FACTOR = 1.0;
  
  private transient BiEntry<K, V>[] hashTableKToV;
  private transient BiEntry<K, V>[] hashTableVToK;
  private transient int size;
  private transient int mask;
  private transient int modCount;
  private HashBiMap(int expectedSize) {
    init(expectedSize);
  }
  private void init(int expectedSize) {
    checkArgument(expectedSize >= 0, "expectedSize must be >= 0 but was %s"expectedSize);
    int tableSize = Hashing.closedTableSize(expectedSize);
    this. = createTable(tableSize);
    this. = createTable(tableSize);
    this. = tableSize - 1;
    this. = 0;
    this. = 0;
  }

  
Finds and removes entry from the bucket linked lists in both the key-to-value direction and the value-to-key direction.
  private void delete(BiEntry<K, V> entry) {
    int keyBucket = entry.keyHash & ;
    BiEntry<K, V> prevBucketEntry = null;
    for (BiEntry<K, V> bucketEntry = [keyBucket]; true;
        bucketEntry = bucketEntry.nextInKToVBucket) {
      if (bucketEntry == entry) {
        if (prevBucketEntry == null) {
          [keyBucket] = entry.nextInKToVBucket;
        } else {
          prevBucketEntry.nextInKToVBucket = entry.nextInKToVBucket;
        }
        break;
      }
      prevBucketEntry = bucketEntry;
    }
    int valueBucket = entry.valueHash & ;
    prevBucketEntry = null;
    for (BiEntry<K, V> bucketEntry = [valueBucket];;
        bucketEntry = bucketEntry.nextInVToKBucket) {
      if (bucketEntry == entry) {
        if (prevBucketEntry == null) {
          [valueBucket] = entry.nextInVToKBucket;
        } else {
          prevBucketEntry.nextInVToKBucket = entry.nextInVToKBucket;
        }
        break;
      }
      prevBucketEntry = bucketEntry;
    }
    --;
    ++;
  }
  private void insert(BiEntry<K, V> entry) {
    int keyBucket = entry.keyHash & ;
    entry.nextInKToVBucket = [keyBucket];
    [keyBucket] = entry;
    int valueBucket = entry.valueHash & ;
    entry.nextInVToKBucket = [valueBucket];
    [valueBucket] = entry;
    ++;
    ++;
  }
  private static int hash(@Nullable Object o) {
    return Hashing.smear((o == null) ? 0 : o.hashCode());
  }
  private BiEntry<K, V> seekByKey(@Nullable Object keyint keyHash) {
    for (BiEntry<K, V> entry = [keyHash & ]; entry != null;
        entry = entry.nextInKToVBucket) {
      if (keyHash == entry.keyHash && Objects.equal(keyentry.key)) {
        return entry;
      }
    }
    return null;
  }
  private BiEntry<K, V> seekByValue(@Nullable Object valueint valueHash) {
    for (BiEntry<K, V> entry = [valueHash & ]; entry != null;
        entry = entry.nextInVToKBucket) {
      if (valueHash == entry.valueHash && Objects.equal(valueentry.value)) {
        return entry;
      }
    }
    return null;
  }
  public boolean containsKey(@Nullable Object key) {
    return seekByKey(keyhash(key)) != null;
  }
  public boolean containsValue(@Nullable Object value) {
    return seekByValue(valuehash(value)) != null;
  }
  @Nullable
  public V get(@Nullable Object key) {
    BiEntry<K, V> entry = seekByKey(keyhash(key));
    return (entry == null) ? null : entry.value;
  }
  public V put(@Nullable K key, @Nullable V value) {
    return put(keyvaluefalse);
  }
  public V forcePut(@Nullable K key, @Nullable V value) {
    return put(keyvaluetrue);
  }
  private V put(@Nullable K key, @Nullable V valueboolean force) {
    int keyHash = hash(key);
    int valueHash = hash(value);
    BiEntry<K, V> oldEntryForKey = seekByKey(keykeyHash);
    if (oldEntryForKey != null && valueHash == oldEntryForKey.valueHash
        && Objects.equal(valueoldEntryForKey.value)) {
      return value;
    }
    BiEntry<K, V> oldEntryForValue = seekByValue(valuevalueHash);
    if (oldEntryForValue != null) {
      if (force) {
        delete(oldEntryForValue);
      } else {
        throw new IllegalArgumentException("value already present: " + value);
      }
    }
    if (oldEntryForKey != null) {
      delete(oldEntryForKey);
    }
    BiEntry<K, V> newEntry = new BiEntry<K, V>(keykeyHashvaluevalueHash);
    insert(newEntry);
    return (oldEntryForKey == null) ? null : oldEntryForKey.value;
  }
  @Nullable
  private K putInverse(@Nullable V value, @Nullable K keyboolean force) {
    int valueHash = hash(value);
    int keyHash = hash(key);
    BiEntry<K, V> oldEntryForValue = seekByValue(valuevalueHash);
    if (oldEntryForValue != null && keyHash == oldEntryForValue.keyHash
        && Objects.equal(keyoldEntryForValue.key)) {
      return key;
    }
    BiEntry<K, V> oldEntryForKey = seekByKey(keykeyHash);
    if (oldEntryForKey != null) {
      if (force) {
        delete(oldEntryForKey);
      } else {
        throw new IllegalArgumentException("value already present: " + key);
      }
    }
    if (oldEntryForValue != null) {
      delete(oldEntryForValue);
    }
    BiEntry<K, V> newEntry = new BiEntry<K, V>(keykeyHashvaluevalueHash);
    insert(newEntry);
    return (oldEntryForValue == null) ? null : oldEntryForValue.key;
  }
  private void rehashIfNecessary() {
    BiEntry<K, V>[] oldKToV = ;
    if (Hashing.needsResizing(oldKToV.length)) {
      int newTableSize = oldKToV.length * 2;
      this. = createTable(newTableSize);
      this. = createTable(newTableSize);
      this. = newTableSize - 1;
      this. = 0;
      for (int bucket = 0; bucket < oldKToV.lengthbucket++) {
        BiEntry<K, V> entry = oldKToV[bucket];
        while (entry != null) {
          BiEntry<K, V> nextEntry = entry.nextInKToVBucket;
          insert(entry);
          entry = nextEntry;
        }
      }
      this.++;
    }
  }
  @SuppressWarnings("unchecked")
  private BiEntry<K, V>[] createTable(int length) {
    return new BiEntry[length];
  }
  public V remove(@Nullable Object key) {
    BiEntry<K, V> entry = seekByKey(keyhash(key));
    if (entry == null) {
      return null;
    } else {
      delete(entry);
      return entry.value;
    }
  }
  public void clear() {
     = 0;
    Arrays.fill(null);
    Arrays.fill(null);
    ++;
  }
  public int size() {
    return ;
  }
  abstract class Itr<T> implements Iterator<T> {
    int nextBucket = 0;
    BiEntry<K, V> next = null;
    BiEntry<K, V> toRemove = null;
    int expectedModCount = ;
    private void checkForConcurrentModification() {
      if ( != ) {
        throw new ConcurrentModificationException();
      }
    }
    @Override
    public boolean hasNext() {
      if ( != null) {
        return true;
      }
      while ( < .) {
        if ([] != null) {
           = [++];
          return true;
        }
        ++;
      }
      return false;
    }
    @Override
    public T next() {
      if (!hasNext()) {
        throw new NoSuchElementException();
      }
      BiEntry<K, V> entry = ;
       = entry.nextInKToVBucket;
       = entry;
      return output(entry);
    }
    @Override
    public void remove() {
      checkState( != null"Only one remove() call allowed per call to next");
      delete();
       = ;
       = null;
    }
    abstract T output(BiEntry<K, V> entry);
  }
  public Set<K> keySet() {
    return new KeySet();
  }
  private final class KeySet extends Maps.KeySet<K, V> {
    @Override
    Map<K, V> map() {
      return HashBiMap.this;
    }
    @Override
    public Iterator<K> iterator() {
      return new Itr<K>() {
        @Override
        K output(BiEntry<K, V> entry) {
          return entry.key;
        }
      };
    }
    @Override
    public boolean remove(@Nullable Object o) {
      BiEntry<K, V> entry = seekByKey(ohash(o));
      if (entry == null) {
        return false;
      } else {
        delete(entry);
        return true;
      }
    }
  }
  public Set<V> values() {
    return inverse().keySet();
  }
  public Set<Entry<K, V>> entrySet() {
    return new EntrySet();
  }
  private final class EntrySet extends Maps.EntrySet<K, V> {
    @Override
    Map<K, V> map() {
      return HashBiMap.this;
    }
    @Override
    public Iterator<Entry<K, V>> iterator() {
      return new Itr<Entry<K, V>>() {
        @Override
        Entry<K, V> output(BiEntry<K, V> entry) {
          return new MapEntry(entry);
        }
        class MapEntry extends AbstractMapEntry<K, V> {
          BiEntry<K, V> delegate;
          MapEntry(BiEntry<K, V> entry) {
            this. = entry;
          }
          @Override public K getKey() {
            return .;
          }
          @Override public V getValue() {
            return .;
          }
          @Override public V setValue(V value) {
            V oldValue = .;
            int valueHash = hash(value);
            if (valueHash == . && Objects.equal(valueoldValue)) {
              return value;
            }
            checkArgument(
                seekByValue(valuevalueHash) == null"value already present: %s"value);
            delete();
            BiEntry<K, V> newEntry =
                new BiEntry<K, V>(..valuevalueHash);
            insert(newEntry);
             = ;
            if ( == ) {
               = newEntry;
            }
             = newEntry;
            return oldValue;
          }
        }
      };
    }
  }
  private transient BiMap<V, K> inverse;
  public BiMap<V, K> inverse() {
    return ( == null) ?  = new Inverse() : ;
  }
  private final class Inverse extends AbstractMap<V, K> implements BiMap<V, K>, Serializable {
    BiMap<K, V> forward() {
      return HashBiMap.this;
    }
    @Override
    public int size() {
      return ;
    }
    @Override
    public void clear() {
      forward().clear();
    }
    @Override
    public boolean containsKey(@Nullable Object value) {
      return forward().containsValue(value);
    }
    @Override
    public K get(@Nullable Object value) {
      BiEntry<K, V> entry = seekByValue(valuehash(value));
      return (entry == null) ? null : entry.key;
    }
    @Override
    public K put(@Nullable V value, @Nullable K key) {
      return putInverse(valuekeyfalse);
    }
    @Override
    public K forcePut(@Nullable V value, @Nullable K key) {
      return putInverse(valuekeytrue);
    }
    @Override
    public K remove(@Nullable Object value) {
      BiEntry<K, V> entry = seekByValue(valuehash(value));
      if (entry == null) {
        return null;
      } else {
        delete(entry);
        return entry.key;
      }
    }
    @Override
    public BiMap<K, V> inverse() {
      return forward();
    }
    @Override
    public Set<V> keySet() {
      return new InverseKeySet();
    }
    private final class InverseKeySet extends Maps.KeySet<V, K> {
      @Override
      Map<V, K> map() {
        return Inverse.this;
      }
      @Override
      public boolean remove(@Nullable Object o) {
        BiEntry<K, V> entry = seekByValue(ohash(o));
        if (entry == null) {
          return false;
        } else {
          delete(entry);
          return true;
        }
      }
      @Override
      public Iterator<V> iterator() {
        return new Itr<V>() {
          @Override V output(BiEntry<K, V> entry) {
            return entry.value;
          }
        };
      }
    }
    @Override
    public Set<K> values() {
      return forward().keySet();
    }
    @Override
    public Set<Entry<V, K>> entrySet() {
      return new Maps.EntrySet<V, K>() {
        @Override
        Map<V, K> map() {
          return Inverse.this;
        }
        @Override
        public Iterator<Entry<V, K>> iterator() {
          return new Itr<Entry<V, K>>() {
            @Override
            Entry<V, K> output(BiEntry<K, V> entry) {
              return new InverseEntry(entry);
            }
            class InverseEntry extends AbstractMapEntry<V, K> {
              BiEntry<K, V> delegate;
              InverseEntry(BiEntry<K, V> entry) {
                this. = entry;
              }
              @Override
              public V getKey() {
                return .;
              }
              @Override
              public K getValue() {
                return .;
              }
              @Override
              public K setValue(K key) {
                K oldKey = .;
                int keyHash = hash(key);
                if (keyHash == . && Objects.equal(keyoldKey)) {
                  return key;
                }
                checkArgument(seekByKey(keykeyHash) == null"value already present: %s"key);
                delete();
                BiEntry<K, V> newEntry =
                    new BiEntry<K, V>(keykeyHash..);
                insert(newEntry);
                 = ;
                // This is safe because entries can only get bumped up to earlier in the iteration,
                // so they can't get revisited.
                return oldKey;
              }
            }
          };
        }
      };
    }
    Object writeReplace() {
      return new InverseSerializedForm<K, V>(HashBiMap.this);
    }
  }
  private static final class InverseSerializedForm<K, V> implements Serializable {
    private final HashBiMap<K, V> bimap;
    InverseSerializedForm(HashBiMap<K, V> bimap) {
      this. = bimap;
    }
    Object readResolve() {
      return .inverse();
    }
  }

  

SerialData:
the number of entries, first key, first value, second key, second value, and so on.
  @GwtIncompatible("java.io.ObjectOutputStream")
  private void writeObject(ObjectOutputStream streamthrows IOException {
    stream.defaultWriteObject();
    Serialization.writeMap(thisstream);
  }
  @GwtIncompatible("java.io.ObjectInputStream")
  private void readObject(ObjectInputStream streamthrows IOExceptionClassNotFoundException {
    stream.defaultReadObject();
    int size = Serialization.readCount(stream);
    init(size);
    Serialization.populateMap(thisstreamsize);
  }
  @GwtIncompatible("Not needed in emulated source")
  private static final long serialVersionUID = 0;
New to GrepCode? Check out our FAQ X