Package org.jibx.util

Class StringSizedSet


  • public class StringSizedSet
    extends java.lang.Object
    Fixed size hash set of String values.
    Author:
    Dennis M. Sosnoski
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static double DEFAULT_FILL_FRACTION
      Default fill fraction for sizing of tables.
      protected int m_arraySize
      Size of array used for keys.
      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.
    • Constructor Summary

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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      boolean add​(java.lang.String key)
      Add a key to the set.
      void clear()
      Set the table to the empty state.
      boolean contains​(java.lang.String key)
      Check if an entry is present in the table.
      private int freeSlot​(int slot)
      Find free slot number for entry.
      private int standardFind​(java.lang.String key)
      Standard find key in table.
      private int standardSlot​(java.lang.String 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

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

      • DEFAULT_FILL_FRACTION

        public static final double DEFAULT_FILL_FRACTION
        Default fill fraction for sizing of tables.
        See Also:
        Constant Field Values
      • m_arraySize

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

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

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

      • StringSizedSet

        public StringSizedSet​(int count,
                              double fill)
        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)
      • StringSizedSet

        public StringSizedSet​(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 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.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​(java.lang.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 boolean add​(java.lang.String key)
        Add a key to the set. If the key is already present in the set, this does nothing.
        Parameters:
        key - key to be added to table (non-null)
        Returns:
        true if added, false if already present value if key not previously present in table
      • contains

        public final boolean contains​(java.lang.String key)
        Check if an entry is present in the table.
        Parameters:
        key - key to be found
        Returns:
        true if key found in table, false if not
      • clear

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