Class CompactHashMap<K,​V>

  • All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>
    Direct Known Subclasses:
    CompactLinkedHashMap

    @GwtIncompatible
    class CompactHashMap<K,​V>
    extends java.util.AbstractMap<K,​V>
    implements java.io.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.

    • Nested Class Summary

      Nested Classes 
      Modifier and Type Class Description
      (package private) class  CompactHashMap.EntrySetView  
      private class  CompactHashMap.Itr<T>  
      (package private) class  CompactHashMap.KeySetView  
      (package private) class  CompactHashMap.MapEntry  
      (package private) class  CompactHashMap.ValuesView  
      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) static int DEFAULT_SIZE  
      (package private) long[] entries
      Contains the logical entries, in the range of [0, size()).
      private java.util.Set<java.util.Map.Entry<K,​V>> entrySetView  
      private static long HASH_MASK
      Bitmask that selects the high 32 bits.
      (package private) java.lang.Object[] keys
      The keys of the entries in the map, in the range of [0, size()).
      private java.util.Set<K> keySetView  
      private static float LOAD_FACTOR  
      (package private) int modCount
      Keeps track of modifications of this set, to make it possible to throw ConcurrentModificationException in the iterator.
      private static long NEXT_MASK
      Bitmask that selects the low 32 bits.
      private int size
      The number of elements contained in the set.
      private int[] table
      The hashtable.
      (package private) static int UNSET  
      (package private) java.lang.Object[] values
      The values of the entries in the map, in the range of [0, size()).
      private java.util.Collection<V> valuesView  
    • Constructor Summary

      Constructors 
      Constructor Description
      CompactHashMap()
      Constructs a new empty instance of CompactHashMap.
      CompactHashMap​(int expectedSize)
      Constructs a new instance of CompactHashMap with the specified capacity.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void accessEntry​(int index)
      Mark an access of the specified entry.
      (package private) 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.
      (package private) void allocArrays()
      Handle lazy allocation of arrays.
      void clear()  
      boolean containsKey​(java.lang.Object key)  
      boolean containsValue​(java.lang.Object value)  
      static <K,​V>
      CompactHashMap<K,​V>
      create()
      Creates an empty CompactHashMap instance.
      (package private) java.util.Set<java.util.Map.Entry<K,​V>> createEntrySet()  
      (package private) java.util.Set<K> createKeySet()  
      (package private) java.util.Collection<V> createValues()  
      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.
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()  
      (package private) java.util.Iterator<java.util.Map.Entry<K,​V>> entrySetIterator()  
      (package private) int firstEntryIndex()  
      void forEach​(java.util.function.BiConsumer<? super K,​? super V> action)  
      V get​(java.lang.Object key)  
      private static int getHash​(long entry)  
      private static int getNext​(long entry)
      Returns the index, or UNSET if the pointer is "null"
      (package private) int getSuccessor​(int entryIndex)  
      private int hashTableMask()  
      private int indexOf​(java.lang.Object key)  
      (package private) void init​(int expectedSize)
      Pseudoconstructor for serialization support.
      (package private) void insertEntry​(int entryIndex, K key, V value, int hash)
      Creates a fresh entry with the specified object at the specified position in the entry arrays.
      boolean isEmpty()  
      java.util.Set<K> keySet()  
      (package private) java.util.Iterator<K> keySetIterator()  
      (package private) void moveLastEntry​(int dstIndex)
      Moves the last entry in the entry array into dstIndex, and nulls out its old position.
      (package private) boolean needsAllocArrays()
      Returns whether arrays need to be allocated.
      private static long[] newEntries​(int size)  
      private static int[] newTable​(int size)  
      V put​(K key, V value)  
      private void readObject​(java.io.ObjectInputStream stream)  
      V remove​(java.lang.Object key)  
      private V remove​(java.lang.Object key, int hash)  
      private V removeEntry​(int entryIndex)  
      void replaceAll​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)  
      (package private) void resizeEntries​(int newCapacity)
      Resizes the internal entries array to the specified capacity, which may be greater or less than the current capacity.
      private void resizeMeMaybe​(int newSize)
      Resizes the entries storage if necessary.
      private void resizeTable​(int newCapacity)  
      int size()  
      private static long swapNext​(long entry, int newNext)
      Returns a new entry value by changing the "next" index of an existing entry
      void trimToSize()
      Ensures that this CompactHashMap has the smallest representation in memory, given its current size.
      java.util.Collection<V> values()  
      (package private) java.util.Iterator<V> valuesIterator()  
      private void writeObject​(java.io.ObjectOutputStream stream)  
      • Methods inherited from class java.util.AbstractMap

        clone, equals, hashCode, putAll, toString
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, getOrDefault, merge, putIfAbsent, remove, replace, replace
    • Field Detail

      • NEXT_MASK

        private static final long NEXT_MASK
        Bitmask that selects the low 32 bits.
        See Also:
        Constant Field Values
      • HASH_MASK

        private static final long HASH_MASK
        Bitmask that selects the high 32 bits.
        See Also:
        Constant Field Values
      • table

        private transient int[] table
        The hashtable. Its values are indexes to the keys, values, and entries arrays.

        Currently, the UNSET value means "null pointer", and any non negative value x is the actual index.

        Its size must be a power of two.

      • entries

        transient long[] entries
        Contains the logical entries, in the range of [0, size()). The high 32 bits of each long is the smeared hash of the element, whereas the low 32 bits is the "next" pointer (pointing to the next entry in the bucket chain). The pointers in [size(), entries.length) are all "null" (UNSET).
      • keys

        transient java.lang.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

        transient java.lang.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.
      • modCount

        transient int modCount
        Keeps track of modifications of this set, 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.
      • size

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

        private transient java.util.Set<K> keySetView
      • entrySetView

        private transient java.util.Set<java.util.Map.Entry<K,​V>> entrySetView
      • valuesView

        private transient java.util.Collection<V> valuesView
    • Constructor Detail

      • 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 Detail

      • 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:
        java.lang.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

        void allocArrays()
        Handle lazy allocation of arrays.
      • newTable

        private static int[] newTable​(int size)
      • newEntries

        private static long[] newEntries​(int size)
      • hashTableMask

        private int hashTableMask()
      • getHash

        private static int getHash​(long entry)
      • getNext

        private static int getNext​(long entry)
        Returns the index, or UNSET if the pointer is "null"
      • swapNext

        private static long swapNext​(long entry,
                                     int newNext)
        Returns a new entry value by changing the "next" index of an existing entry
      • accessEntry

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

        public V put​(K key,
                     V value)
        Specified by:
        put in interface java.util.Map<K,​V>
        Overrides:
        put in class java.util.AbstractMap<K,​V>
      • insertEntry

        void insertEntry​(int entryIndex,
                         K key,
                         V value,
                         int hash)
        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 void resizeTable​(int newCapacity)
      • indexOf

        private int indexOf​(java.lang.Object key)
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>
      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<K,​V>
        Overrides:
        remove in class java.util.AbstractMap<K,​V>
      • remove

        private V remove​(java.lang.Object key,
                         int hash)
      • removeEntry

        private V removeEntry​(int entryIndex)
      • moveLastEntry

        void moveLastEntry​(int dstIndex)
        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​(java.util.function.BiFunction<? super K,​? super V,​? extends V> function)
        Specified by:
        replaceAll in interface java.util.Map<K,​V>
      • keySet

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

        java.util.Set<K> createKeySet()
      • keySetIterator

        java.util.Iterator<K> keySetIterator()
      • forEach

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

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

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

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

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

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

        public boolean containsValue​(java.lang.Object value)
        Specified by:
        containsValue in interface java.util.Map<K,​V>
        Overrides:
        containsValue in class java.util.AbstractMap<K,​V>
      • values

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

        java.util.Collection<V> createValues()
      • valuesIterator

        java.util.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 java.util.Map<K,​V>
        Overrides:
        clear in class java.util.AbstractMap<K,​V>
      • writeObject

        private void writeObject​(java.io.ObjectOutputStream stream)
                          throws java.io.IOException
        Throws:
        java.io.IOException
      • readObject

        private void readObject​(java.io.ObjectInputStream stream)
                         throws java.io.IOException,
                                java.lang.ClassNotFoundException
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException