Class IntObjectHashMap<V>

  • Type Parameters:
    V - The value type stored in the map.
    All Implemented Interfaces:
    IntObjectMap<V>, java.util.Map<java.lang.Integer,​V>

    public class IntObjectHashMap<V>
    extends java.lang.Object
    implements IntObjectMap<V>
    A hash map implementation of IntObjectMap that uses open addressing for keys. To minimize the memory footprint, this class uses open addressing rather than chaining. Collisions are resolved using linear probing. Deletions implement compaction, so cost of remove can approach O(N) for full maps, which makes a small loadFactor recommended.
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static int DEFAULT_CAPACITY
      Default initial capacity.
      static float DEFAULT_LOAD_FACTOR
      Default load factor.
      private java.lang.Iterable<IntObjectMap.PrimitiveEntry<V>> entries  
      private java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet  
      private int[] keys  
      private java.util.Set<java.lang.Integer> keySet  
      private float loadFactor
      The load factor for the map.
      private int mask  
      private int maxSize
      The maximum number of elements allowed without allocating more space.
      private static java.lang.Object NULL_VALUE
      Placeholder for null values, so we can use the actual null to mean available.
      private int size  
      private V[] values  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private int calcMaxSize​(int capacity)
      Calculates the maximum size allowed before rehashing.
      void clear()  
      boolean containsKey​(int key)
      Indicates whether or not this map contains a value for the specified key.
      boolean containsKey​(java.lang.Object key)  
      boolean containsValue​(java.lang.Object value)  
      java.lang.Iterable<IntObjectMap.PrimitiveEntry<V>> entries()
      Gets an iterable to traverse over the primitive entries contained in this map.
      java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet()  
      boolean equals​(java.lang.Object obj)  
      V get​(int key)
      Gets the value in the map with the specified key.
      V get​(java.lang.Object key)  
      private void growSize()
      Grows the map size after an insertion.
      int hashCode()  
      private static int hashCode​(int key)
      Returns the hash code for the key.
      private int hashIndex​(int key)
      Returns the hashed index for the given key.
      private int indexOf​(int key)
      Locates the index for the given key.
      boolean isEmpty()  
      java.util.Set<java.lang.Integer> keySet()  
      protected java.lang.String keyToString​(int key)
      Helper method called by toString() in order to convert a single map key into a string.
      private int objectToKey​(java.lang.Object key)  
      private int probeNext​(int index)
      Get the next sequential index after index and wraps if necessary.
      V put​(int key, V value)
      Puts the given entry into the map.
      V put​(java.lang.Integer key, V value)  
      void putAll​(java.util.Map<? extends java.lang.Integer,​? extends V> sourceMap)  
      private void rehash​(int newCapacity)
      Rehashes the map for the given capacity.
      V remove​(int key)
      Removes the entry with the specified key.
      V remove​(java.lang.Object key)  
      private boolean removeAt​(int index)
      Removes entry at the given index position.
      int size()  
      private static <T> T toExternal​(T value)  
      private static <T> T toInternal​(T value)  
      java.lang.String toString()  
      java.util.Collection<V> values()  
      • Methods inherited from class java.lang.Object

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

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

      • DEFAULT_CAPACITY

        public static final int DEFAULT_CAPACITY
        Default initial capacity. Used if not specified in the constructor
        See Also:
        Constant Field Values
      • DEFAULT_LOAD_FACTOR

        public static final float DEFAULT_LOAD_FACTOR
        Default load factor. Used if not specified in the constructor
        See Also:
        Constant Field Values
      • NULL_VALUE

        private static final java.lang.Object NULL_VALUE
        Placeholder for null values, so we can use the actual null to mean available. (Better than using a placeholder for available: less references for GC processing.)
      • maxSize

        private int maxSize
        The maximum number of elements allowed without allocating more space.
      • loadFactor

        private final float loadFactor
        The load factor for the map. Used to calculate maxSize.
      • keys

        private int[] keys
      • values

        private V[] values
      • size

        private int size
      • mask

        private int mask
      • keySet

        private final java.util.Set<java.lang.Integer> keySet
      • entrySet

        private final java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet
    • Constructor Detail

      • IntObjectHashMap

        public IntObjectHashMap()
      • IntObjectHashMap

        public IntObjectHashMap​(int initialCapacity)
      • IntObjectHashMap

        public IntObjectHashMap​(int initialCapacity,
                                float loadFactor)
    • Method Detail

      • toExternal

        private static <T> T toExternal​(T value)
      • toInternal

        private static <T> T toInternal​(T value)
      • get

        public V get​(int key)
        Description copied from interface: IntObjectMap
        Gets the value in the map with the specified key.
        Specified by:
        get in interface IntObjectMap<V>
        Parameters:
        key - the key whose associated value is to be returned.
        Returns:
        the value or null if the key was not found in the map.
      • put

        public V put​(int key,
                     V value)
        Description copied from interface: IntObjectMap
        Puts the given entry into the map.
        Specified by:
        put in interface IntObjectMap<V>
        Parameters:
        key - the key of the entry.
        value - the value of the entry.
        Returns:
        the previous value for this key or null if there was no previous mapping.
      • putAll

        public void putAll​(java.util.Map<? extends java.lang.Integer,​? extends V> sourceMap)
        Specified by:
        putAll in interface java.util.Map<java.lang.Integer,​V>
      • remove

        public V remove​(int key)
        Description copied from interface: IntObjectMap
        Removes the entry with the specified key.
        Specified by:
        remove in interface IntObjectMap<V>
        Parameters:
        key - the key for the entry to be removed from this map.
        Returns:
        the previous value for the key, or null if there was no mapping.
      • size

        public int size()
        Specified by:
        size in interface java.util.Map<java.lang.Integer,​V>
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<java.lang.Integer,​V>
      • clear

        public void clear()
        Specified by:
        clear in interface java.util.Map<java.lang.Integer,​V>
      • containsKey

        public boolean containsKey​(int key)
        Description copied from interface: IntObjectMap
        Indicates whether or not this map contains a value for the specified key.
        Specified by:
        containsKey in interface IntObjectMap<V>
      • containsValue

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

        public java.util.Collection<V> values()
        Specified by:
        values in interface java.util.Map<java.lang.Integer,​V>
      • hashCode

        public int hashCode()
        Specified by:
        hashCode in interface java.util.Map<java.lang.Integer,​V>
        Overrides:
        hashCode in class java.lang.Object
      • equals

        public boolean equals​(java.lang.Object obj)
        Specified by:
        equals in interface java.util.Map<java.lang.Integer,​V>
        Overrides:
        equals in class java.lang.Object
      • containsKey

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

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<java.lang.Integer,​V>
      • put

        public V put​(java.lang.Integer key,
                     V value)
        Specified by:
        put in interface java.util.Map<java.lang.Integer,​V>
      • remove

        public V remove​(java.lang.Object key)
        Specified by:
        remove in interface java.util.Map<java.lang.Integer,​V>
      • keySet

        public java.util.Set<java.lang.Integer> keySet()
        Specified by:
        keySet in interface java.util.Map<java.lang.Integer,​V>
      • entrySet

        public java.util.Set<java.util.Map.Entry<java.lang.Integer,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<java.lang.Integer,​V>
      • objectToKey

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

        private int indexOf​(int key)
        Locates the index for the given key. This method probes using double hashing.
        Parameters:
        key - the key for an entry in the map.
        Returns:
        the index where the key was found, or -1 if no entry is found for that key.
      • hashIndex

        private int hashIndex​(int key)
        Returns the hashed index for the given key.
      • hashCode

        private static int hashCode​(int key)
        Returns the hash code for the key.
      • probeNext

        private int probeNext​(int index)
        Get the next sequential index after index and wraps if necessary.
      • growSize

        private void growSize()
        Grows the map size after an insertion. If necessary, performs a rehash of the map.
      • removeAt

        private boolean removeAt​(int index)
        Removes entry at the given index position. Also performs opportunistic, incremental rehashing if necessary to not break conflict chains.
        Parameters:
        index - the index position of the element to remove.
        Returns:
        true if the next item was moved back. false otherwise.
      • calcMaxSize

        private int calcMaxSize​(int capacity)
        Calculates the maximum size allowed before rehashing.
      • rehash

        private void rehash​(int newCapacity)
        Rehashes the map for the given capacity.
        Parameters:
        newCapacity - the new capacity for the map.
      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object
      • keyToString

        protected java.lang.String keyToString​(int key)
        Helper method called by toString() in order to convert a single map key into a string. This is protected to allow subclasses to override the appearance of a given key.