Package org.jibx.util

Class StringIntSizedMap

java.lang.Object
org.jibx.util.StringIntSizedMap

public class StringIntSizedMap extends Object
Fixed size hash map using String values as keys mapped to primitive int values.
Author:
Dennis M. Sosnoski
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final double
    Default fill fraction for sizing of tables.
    static final int
    Default value returned when key not found in table.
    protected final int
    Size of array used for keys.
    protected final int
    Offset added (modulo table size) to slot number on collision.
    protected final String[]
    Array of key table slots.
    protected final int
    Value returned when key not found in table.
    protected final int[]
    Array of value table slots.
  • Constructor Summary

    Constructors
    Constructor
    Description
    StringIntSizedMap(int count)
    Constructor with only value count specified.
    StringIntSizedMap(int count, double fill, int miss)
    Constructor with full specification.
    StringIntSizedMap(int count, int miss)
    Constructor with value count and miss value specified.
  • Method Summary

    Modifier and Type
    Method
    Description
    int
    add(String key, int value)
    Add an entry to the table.
    void
    Set the table to the empty state.
    final boolean
    Check if an entry is present in the table.
    private final int
    freeSlot(int slot)
    Find free slot number for entry.
    final int
    get(String key)
    Find an entry in the table.
    private int
    Standard find key in table.
    private final int
    Standard base slot computation for a key.
    private final int
    stepSlot(int slot)
    Step the slot number for an entry.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • DEFAULT_FILL_FRACTION

      public static final double DEFAULT_FILL_FRACTION
      Default fill fraction for sizing of tables.
      See Also:
    • DEFAULT_NOT_FOUND

      public static final int DEFAULT_NOT_FOUND
      Default value returned when key not found in table.
      See Also:
    • m_arraySize

      protected final int m_arraySize
      Size of array used for keys.
    • m_keyTable

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

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

      protected final int m_notFoundValue
      Value returned when key not found in table.
    • m_hitOffset

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

    • StringIntSizedMap

      public StringIntSizedMap(int count, double fill, int miss)
      Constructor with full specification.
      Parameters:
      count - number of values to assume in sizing of table
      fill - fraction fill for table (maximum of 0.7, to prevent excessive collisions)
      miss - value returned when key not found in table
    • StringIntSizedMap

      public StringIntSizedMap(int count, int miss)
      Constructor with value count and miss value specified. Uses default fill fraction.
      Parameters:
      count - number of values to assume in initial sizing of table
      miss - value returned when key not found in table
    • StringIntSizedMap

      public StringIntSizedMap(int count)
      Constructor with only value count specified. Uses default fill fraction and miss value.
      Parameters:
      count - number of values to assume in initial sizing of table
  • Method Details

    • 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(String key)
      Standard base slot computation for a key. This method may be used directly for key lookup using either the hashCode() method defined for the key objects or the System.identityHashCode() method, 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 - key value to be computed
      Returns:
      base slot for key
    • standardFind

      private int standardFind(String key)
      Standard find key in table. This uses equals comparisons for the key values.
      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)
    • add

      public int add(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(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(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
    • clear

      public void clear()
      Set the table to the empty state.