Class StringIntHashMap


  • public class StringIntHashMap
    extends java.lang.Object
    Hash map using String values as keys mapped to primitive int values. This implementation is unsynchronized in order to provide the best possible performance for typical usage scenarios, so explicit synchronization must be implemented by a wrapper class or directly by the application in cases where instances are modified in a multithreaded environment. The map implementation is not very efficient when resizing, but works well when the size of the map is known in advance.
    Version:
    1.1
    Author:
    Dennis M. Sosnoski
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected static double DEFAULT_FILL
      Default fill fraction allowed before growing table.
      static int DEFAULT_NOT_FOUND
      Default value returned when key not found in table.
      protected int m_arraySize
      Size of array used for keys.
      protected int m_entryCount
      Number of entries present in table.
      protected int m_entryLimit
      Entries allowed before growing table.
      protected double m_fillFraction
      Fill fraction allowed for this hash table.
      protected int m_hitOffset
      Offset added (modulo table size) to slot number on collision.
      protected java.lang.String[] m_keyTable
      Array of key table slots.
      protected int m_notFoundValue
      Value returned when key not found in table.
      protected int[] m_valueTable
      Array of value table slots.
      protected static int MINIMUM_SIZE
      Minimum size used for hash table.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      int add​(java.lang.String key, int value)
      Add an entry to the table.
      private int assignSlot​(java.lang.String key, int value)
      Assign slot for entry.
      java.lang.Object clone()
      Construct a copy of the table.
      boolean containsKey​(java.lang.String key)
      Check if an entry is present in the table.
      private int freeSlot​(int slot)
      Find free slot number for entry.
      int get​(java.lang.String key)
      Find an entry in the table.
      protected void internalRemove​(int slot)
      Internal remove pair from the table.
      private boolean reinsert​(int slot)
      Reinsert an entry into the hash map.
      int remove​(java.lang.String key)
      Remove an entry from the table.
      private void restructure​(java.lang.String[] keys, int[] values)
      Restructure the table.
      private int standardFind​(java.lang.Object key)
      Standard find key in table.
      private int standardSlot​(java.lang.Object key)
      Standard base slot computation for a key.
      private int stepSlot​(int slot)
      Step the slot number for an entry.
      • Methods inherited from class java.lang.Object

        equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • DEFAULT_NOT_FOUND

        public static final int DEFAULT_NOT_FOUND
        Default value returned when key not found in table.
        See Also:
        Constant Field Values
      • DEFAULT_FILL

        protected static final double DEFAULT_FILL
        Default fill fraction allowed before growing table.
        See Also:
        Constant Field Values
      • MINIMUM_SIZE

        protected static final int MINIMUM_SIZE
        Minimum size used for hash table.
        See Also:
        Constant Field Values
      • m_fillFraction

        protected final double m_fillFraction
        Fill fraction allowed for this hash table.
      • m_entryCount

        protected int m_entryCount
        Number of entries present in table.
      • m_entryLimit

        protected int m_entryLimit
        Entries allowed before growing table.
      • m_arraySize

        protected int m_arraySize
        Size of array used for keys.
      • m_hitOffset

        protected int m_hitOffset
        Offset added (modulo table size) to slot number on collision.
      • m_keyTable

        protected java.lang.String[] m_keyTable
        Array of key table slots.
      • m_valueTable

        protected int[] m_valueTable
        Array of value table slots.
      • m_notFoundValue

        protected int m_notFoundValue
        Value returned when key not found in table.
    • Constructor Detail

      • StringIntHashMap

        public StringIntHashMap​(int count,
                                double fill,
                                int miss)
        Constructor with full specification.
        Parameters:
        count - number of values to assume in initial sizing of table
        fill - fraction full allowed for table before growing
        miss - value returned when key not found in table
      • StringIntHashMap

        public StringIntHashMap​(int count,
                                double fill)
        Constructor with size and fill fraction specified. Uses default hash technique and value returned when key not found in table.
        Parameters:
        count - number of values to assume in initial sizing of table
        fill - fraction full allowed for table before growing
      • StringIntHashMap

        public StringIntHashMap​(int count)
        Constructor with only size supplied. Uses default hash technique and values for fill fraction and value returned when key not found in table.
        Parameters:
        count - number of values to assume in initial sizing of table
      • StringIntHashMap

        public StringIntHashMap()
        Default constructor.
      • StringIntHashMap

        public StringIntHashMap​(StringIntHashMap base)
        Copy (clone) constructor.
        Parameters:
        base - instance being copied
    • Method Detail

      • stepSlot

        private final int stepSlot​(int slot)
        Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.
        Parameters:
        slot - slot number to be stepped
        Returns:
        stepped slot number
      • freeSlot

        private final int freeSlot​(int slot)
        Find free slot number for entry. Starts at the slot based directly on the hashed key value. If this slot is already occupied, it adds the collision offset (modulo the table size) to the slot number and checks that slot, repeating until an unused slot is found.
        Parameters:
        slot - initial slot computed from key
        Returns:
        slot at which entry was added
      • standardSlot

        private final int standardSlot​(java.lang.Object key)
        Standard base slot computation for a key.
        Parameters:
        key - key value to be computed
        Returns:
        base slot for key
      • standardFind

        private int standardFind​(java.lang.Object key)
        Standard find key in table. This method may be used directly for key lookup using either the hashCode() method defined for the key objects or the System.identityHashCode() method, and either the equals() method defined for the key objects or the == operator, as selected by the hash technique constructor parameter. To implement a hash class based on some other methods of hashing and/or equality testing, define a separate method in the subclass with a different name and use that method instead. This avoids the overhead caused by overrides of a very heavily used method.
        Parameters:
        key - to be found in table
        Returns:
        index of matching key, or -index-1 of slot to be used for inserting key in table if not already present (always negative)
      • reinsert

        private boolean reinsert​(int slot)
        Reinsert an entry into the hash map. This is used when the table is being directly modified, and does not adjust the count present or check the table capacity.
        Parameters:
        slot - position of entry to be reinserted into hash map
        Returns:
        true if the slot number used by the entry has has changed, false if not
      • internalRemove

        protected void internalRemove​(int slot)
        Internal remove pair from the table. Removes the pair from the table by setting the key entry to null and adjusting the count present, then chains through the table to reinsert any other pairs which may have collided with the removed pair. If the associated value is an object reference, it should be set to null before this method is called.
        Parameters:
        slot - index number of pair to be removed
      • restructure

        private void restructure​(java.lang.String[] keys,
                                 int[] values)
        Restructure the table. This is used when the table is increasing or decreasing in size, and works directly with the old table representation arrays. It inserts pairs from the old arrays directly into the table without adjusting the count present or checking the table size.
        Parameters:
        keys - array of keys
        values - array of values
      • assignSlot

        private int assignSlot​(java.lang.String key,
                               int value)
        Assign slot for entry. Starts at the slot found by the hashed key value. If this slot is already occupied, it steps the slot number and checks the resulting slot, repeating until an unused slot is found. This method does not check for duplicate keys, so it should only be used for internal reordering of the tables.
        Parameters:
        key - to be added to table
        value - associated value for key
        Returns:
        slot at which entry was added
      • add

        public int add​(java.lang.String key,
                       int value)
        Add an entry to the table. If the key is already present in the table, this replaces the existing value associated with the key.
        Parameters:
        key - key to be added to table (non- null)
        value - associated value for key
        Returns:
        value previously associated with key, or reserved not found value if key not previously present in table
      • containsKey

        public final boolean containsKey​(java.lang.String key)
        Check if an entry is present in the table. This method is supplied to support the use of values matching the reserved not found value.
        Parameters:
        key - key for entry to be found
        Returns:
        true if key found in table, false if not
      • get

        public final int get​(java.lang.String key)
        Find an entry in the table.
        Parameters:
        key - key for entry to be returned
        Returns:
        value for key, or reserved not found value if key not found
      • remove

        public int remove​(java.lang.String key)
        Remove an entry from the table. If multiple entries are present with the same key value, only the first one found will be removed.
        Parameters:
        key - key to be removed from table
        Returns:
        value associated with removed key, or reserved not found value if key not found in table
      • clone

        public java.lang.Object clone()
        Construct a copy of the table.
        Overrides:
        clone in class java.lang.Object
        Returns:
        shallow copy of table