Class CompactHashMap<K,V>

java.lang.Object
java.util.AbstractMap<K,V>
com.google.common.collect.CompactHashMap<K,V>
All Implemented Interfaces:
Serializable, Map<K,V>
Direct Known Subclasses:
CompactLinkedHashMap

class CompactHashMap<K,V> extends AbstractMap<K,V> implements Serializable
CompactHashMap is an implementation of a Map. All optional operations (put and remove) are supported. Null keys and values are supported.

containsKey(k), put(k, v) and remove(k) are all (expected and amortized) constant time operations. Expected in the hashtable sense (depends on the hash function doing a good job of distributing the elements to the buckets to a distribution not far from uniform), and amortized since some operations can trigger a hash table resize.

Unlike java.util.HashMap, iteration is only proportional to the actual size(), which is optimal, and not the size of the internal hashtable, which could be much larger than size(). Furthermore, this structure places significantly reduced load on the garbage collector by only using a constant number of internal objects.

If there are no removals, then iteration order for the entrySet(), keySet(), and values views is the same as insertion order. Any removal invalidates any ordering guarantees.

This class should not be assumed to be universally superior to java.util.HashMap. Generally speaking, this class reduces object allocation and memory consumption at the price of moderately increased constant factors of CPU. Only use this class when there is a specific reason to prioritize memory over CPU.

  • Field Details

    • NOT_FOUND

      private static final Object NOT_FOUND
    • HASH_FLOODING_FPP

      static final double HASH_FLOODING_FPP
      Maximum allowed false positive probability of detecting a hash flooding attack given random input.
      See Also:
    • MAX_HASH_BUCKET_LENGTH

      private static final int MAX_HASH_BUCKET_LENGTH
      Maximum allowed length of a hash table bucket before falling back to a j.u.LinkedHashMap-based implementation. Experimentally determined.
      See Also:
    • table

      @CheckForNull private transient Object table
      The hashtable object. This can be either:
      • a byte[], short[], or int[], with size a power of two, created by CompactHashing.createTable, whose values are either
        • UNSET, meaning "null pointer"
        • one plus an index into the keys, values, and entries arrays
      • another java.util.Map delegate implementation. In most modern JDKs, normal java.util hash collections intelligently fall back to a binary search tree if hash table collisions are detected. Rather than going to all the trouble of reimplementing this ourselves, we simply switch over to use the JDK implementation wholesale if probable hash flooding is detected, sacrificing the compactness guarantee in very rare cases in exchange for much more reliable worst-case behavior.
      • null, if no entries have yet been added to the map
    • entries

      @CheckForNull transient int[] entries
      Contains the logical entries, in the range of [0, size()). The high bits of each int are the part of the smeared hash of the key not covered by the hashtable mask, whereas the low bits are the "next" pointer (pointing to the next entry in the bucket chain), which will always be less than or equal to the hashtable mask.
       hash  = aaaaaaaa
       mask  = 00000fff
       next  = 00000bbb
       entry = aaaaabbb
       

      The pointers in [size(), entries.length) are all "null" (UNSET).

    • keys

      @CheckForNull transient Object[] keys
      The keys of the entries in the map, in the range of [0, size()). The keys in [size(), keys.length) are all null.
    • values

      @CheckForNull transient Object[] values
      The values of the entries in the map, in the range of [0, size()). The values in [size(), values.length) are all null.
    • metadata

      private transient int metadata
      Keeps track of metadata like the number of hash table bits and modifications of this data structure (to make it possible to throw ConcurrentModificationException in the iterator). Note that we choose not to make this volatile, so we do less of a "best effort" to track such errors, for better performance.

      For a new instance, where the arrays above have not yet been allocated, the value of metadata is the size that the arrays should be allocated with. Once the arrays have been allocated, the value of metadata combines the number of bits in the "short hash", in its bottom 5 bits, with a modification count in the remaining bits that is used to detect concurrent modification during iteration.

    • size

      private transient int size
      The number of elements contained in the set.
    • keySetView

      @CheckForNull private transient Set<K> keySetView
    • entrySetView

      @CheckForNull private transient Set<Map.Entry<K,V>> entrySetView
    • valuesView

      @CheckForNull private transient Collection<V> valuesView
  • Constructor Details

    • CompactHashMap

      CompactHashMap()
      Constructs a new empty instance of CompactHashMap.
    • CompactHashMap

      CompactHashMap(int expectedSize)
      Constructs a new instance of CompactHashMap with the specified capacity.
      Parameters:
      expectedSize - the initial capacity of this CompactHashMap.
  • Method Details

    • create

      public static <K, V> CompactHashMap<K,V> create()
      Creates an empty CompactHashMap instance.
    • createWithExpectedSize

      public static <K, V> CompactHashMap<K,V> createWithExpectedSize(int expectedSize)
      Creates a CompactHashMap instance, with a high enough "initial capacity" that it should hold expectedSize elements without growth.
      Parameters:
      expectedSize - the number of elements you expect to add to the returned set
      Returns:
      a new, empty CompactHashMap with enough capacity to hold expectedSize elements without resizing
      Throws:
      IllegalArgumentException - if expectedSize is negative
    • init

      void init(int expectedSize)
      Pseudoconstructor for serialization support.
    • needsAllocArrays

      boolean needsAllocArrays()
      Returns whether arrays need to be allocated.
    • allocArrays

      int allocArrays()
      Handle lazy allocation of arrays.
    • delegateOrNull

      @CheckForNull Map<K,V> delegateOrNull()
    • createHashFloodingResistantDelegate

      Map<K,V> createHashFloodingResistantDelegate(int tableSize)
    • convertToHashFloodingResistantImplementation

      Map<K,V> convertToHashFloodingResistantImplementation()
    • setHashTableMask

      private void setHashTableMask(int mask)
      Stores the hash table mask as the number of bits needed to represent an index.
    • hashTableMask

      private int hashTableMask()
      Gets the hash table mask using the stored number of hash table bits.
    • incrementModCount

      void incrementModCount()
    • accessEntry

      void accessEntry(int index)
      Mark an access of the specified entry. Used only in CompactLinkedHashMap for LRU ordering.
    • put

      @CheckForNull public V put(K key, V value)
      Specified by:
      put in interface Map<K,V>
      Overrides:
      put in class AbstractMap<K,V>
    • insertEntry

      void insertEntry(int entryIndex, K key, V value, int hash, int mask)
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
    • resizeMeMaybe

      private void resizeMeMaybe(int newSize)
      Resizes the entries storage if necessary.
    • resizeEntries

      void resizeEntries(int newCapacity)
      Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
    • resizeTable

      private int resizeTable(int oldMask, int newCapacity, int targetHash, int targetEntryIndex)
    • indexOf

      private int indexOf(@CheckForNull Object key)
    • containsKey

      public boolean containsKey(@CheckForNull Object key)
      Specified by:
      containsKey in interface Map<K,V>
      Overrides:
      containsKey in class AbstractMap<K,V>
    • get

      @CheckForNull public V get(@CheckForNull Object key)
      Specified by:
      get in interface Map<K,V>
      Overrides:
      get in class AbstractMap<K,V>
    • remove

      @CheckForNull public V remove(@CheckForNull Object key)
      Specified by:
      remove in interface Map<K,V>
      Overrides:
      remove in class AbstractMap<K,V>
    • removeHelper

      private Object removeHelper(@CheckForNull Object key)
    • moveLastEntry

      void moveLastEntry(int dstIndex, int mask)
      Moves the last entry in the entry array into dstIndex, and nulls out its old position.
    • firstEntryIndex

      int firstEntryIndex()
    • getSuccessor

      int getSuccessor(int entryIndex)
    • adjustAfterRemove

      int adjustAfterRemove(int indexBeforeRemove, int indexRemoved)
      Updates the index an iterator is pointing to after a call to remove: returns the index of the entry that should be looked at after a removal on indexRemoved, with indexBeforeRemove as the index that *was* the next entry that would be looked at.
    • replaceAll

      public void replaceAll(BiFunction<? super K,? super V,? extends V> function)
      Specified by:
      replaceAll in interface Map<K,V>
    • keySet

      public Set<K> keySet()
      Specified by:
      keySet in interface Map<K,V>
      Overrides:
      keySet in class AbstractMap<K,V>
    • createKeySet

      Set<K> createKeySet()
    • keySetIterator

      Iterator<K> keySetIterator()
    • forEach

      public void forEach(BiConsumer<? super K,? super V> action)
      Specified by:
      forEach in interface Map<K,V>
    • entrySet

      public Set<Map.Entry<K,V>> entrySet()
      Specified by:
      entrySet in interface Map<K,V>
      Specified by:
      entrySet in class AbstractMap<K,V>
    • createEntrySet

      Set<Map.Entry<K,V>> createEntrySet()
    • entrySetIterator

      Iterator<Map.Entry<K,V>> entrySetIterator()
    • size

      public int size()
      Specified by:
      size in interface Map<K,V>
      Overrides:
      size in class AbstractMap<K,V>
    • isEmpty

      public boolean isEmpty()
      Specified by:
      isEmpty in interface Map<K,V>
      Overrides:
      isEmpty in class AbstractMap<K,V>
    • containsValue

      public boolean containsValue(@CheckForNull Object value)
      Specified by:
      containsValue in interface Map<K,V>
      Overrides:
      containsValue in class AbstractMap<K,V>
    • values

      public Collection<V> values()
      Specified by:
      values in interface Map<K,V>
      Overrides:
      values in class AbstractMap<K,V>
    • createValues

      Collection<V> createValues()
    • valuesIterator

      Iterator<V> valuesIterator()
    • trimToSize

      public void trimToSize()
      Ensures that this CompactHashMap has the smallest representation in memory, given its current size.
    • clear

      public void clear()
      Specified by:
      clear in interface Map<K,V>
      Overrides:
      clear in class AbstractMap<K,V>
    • writeObject

      private void writeObject(ObjectOutputStream stream) throws IOException
      Throws:
      IOException
    • readObject

      private void readObject(ObjectInputStream stream) throws IOException, ClassNotFoundException
      Throws:
      IOException
      ClassNotFoundException
    • requireTable

      private Object requireTable()
    • requireEntries

      private int[] requireEntries()
    • requireKeys

      private Object[] requireKeys()
    • requireValues

      private Object[] requireValues()
    • key

      private K key(int i)
    • value

      private V value(int i)
    • entry

      private int entry(int i)
    • setKey

      private void setKey(int i, K key)
    • setValue

      private void setValue(int i, V value)
    • setEntry

      private void setEntry(int i, int value)