Class THash

java.lang.Object
gnu.trove.impl.hash.THash
All Implemented Interfaces:
Externalizable, Serializable
Direct Known Subclasses:
TObjectHash, TPrimitiveHash

public abstract class THash extends Object implements Externalizable
Base class for hashtables that use open addressing to resolve collisions. Created: Wed Nov 28 21:11:16 2001
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected float
    The auto-compaction factor for the table.
    protected int
    The number of removes that should be performed before an auto-compaction occurs.
    protected boolean
     
    protected int
    the current number of free slots in the hash.
    protected float
    Determines how full the internal table can become before rehashing is required.
    protected int
    The maximum number of elements allowed without allocating more space.
    protected int
    the current number of occupied slots in the hash.
    protected static final int
    the default initial capacity for the hash table.
    protected static final float
    the load above which rehashing occurs.
  • Constructor Summary

    Constructors
    Constructor
    Description
    Creates a new THash instance with the default capacity and load factor.
    THash(int initialCapacity)
    Creates a new THash instance with a prime capacity at or near the specified capacity and with the default load factor.
    THash(int initialCapacity, float loadFactor)
    Creates a new THash instance with a prime capacity at or near the minimum needed to hold initialCapacity elements with load factor loadFactor without triggering a rehash.
  • Method Summary

    Modifier and Type
    Method
    Description
    protected int
     
    abstract int
     
    void
    Empties the collection.
    void
    Compresses the hashtable to the minimum prime size (as defined by PrimeFinder) that will hold all of the elements currently in the table.
    protected void
    computeMaxSize(int capacity)
    Computes the values of maxSize.
    protected void
    Computes the number of removes that need to happen before the next auto-compaction will occur.
    void
    ensureCapacity(int desiredCapacity)
    Ensure that this hashtable has sufficient capacity to hold desiredCapacity additional elements without requiring a rehash.
    protected static long
    fastCeil(double v)
     
    float
     
    boolean
    Tells whether this set is currently holding any elements.
    protected final void
    postInsertHook(boolean usedFreeSlot)
    After an insert, this hook is called to adjust the size/free values of the set and to perform rehashing if necessary.
    void
     
    void
    reenableAutoCompaction(boolean check_for_compaction)
    Re-enable auto-compaction after it was disabled via tempDisableAutoCompaction().
    protected abstract void
    rehash(int newCapacity)
    Rehashes the set.
    protected void
    removeAt(int index)
    Delete the record at index.
    protected static int
    saturatedCast(long v)
     
    void
    The auto-compaction factor controls whether and when a table performs a compact() automatically after a certain number of remove operations.
    protected int
    setUp(int initialCapacity)
    initializes the hashtable to a prime capacity which is at least initialCapacity + 1.
    int
    Returns the number of distinct elements in this collection.
    void
    Temporarily disables auto-compaction.
    final void
    This simply calls compact.
    void
     

    Methods inherited from class java.lang.Object

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

    • DEFAULT_LOAD_FACTOR

      protected static final float DEFAULT_LOAD_FACTOR
      the load above which rehashing occurs.
      See Also:
    • DEFAULT_CAPACITY

      protected static final int DEFAULT_CAPACITY
      the default initial capacity for the hash table. This is one less than a prime value because one is added to it when searching for a prime capacity to account for the free slot required by open addressing. Thus, the real default capacity is 11.
      See Also:
    • _size

      protected transient int _size
      the current number of occupied slots in the hash.
    • _free

      protected transient int _free
      the current number of free slots in the hash.
    • _loadFactor

      protected float _loadFactor
      Determines how full the internal table can become before rehashing is required. This must be a value in the range: 0.0 < loadFactor < 1.0. The default value is 0.5, which is about as large as you can get in open addressing without hurting performance. Cf. Knuth, Volume 3., Chapter 6.
    • _maxSize

      protected int _maxSize
      The maximum number of elements allowed without allocating more space.
    • _autoCompactRemovesRemaining

      protected int _autoCompactRemovesRemaining
      The number of removes that should be performed before an auto-compaction occurs.
    • _autoCompactionFactor

      protected float _autoCompactionFactor
      The auto-compaction factor for the table.
      See Also:
    • _autoCompactTemporaryDisable

      protected transient boolean _autoCompactTemporaryDisable
      See Also:
  • Constructor Details

    • THash

      public THash()
      Creates a new THash instance with the default capacity and load factor.
    • THash

      public THash(int initialCapacity)
      Creates a new THash instance with a prime capacity at or near the specified capacity and with the default load factor.
      Parameters:
      initialCapacity - an int value
    • THash

      public THash(int initialCapacity, float loadFactor)
      Creates a new THash instance with a prime capacity at or near the minimum needed to hold initialCapacity elements with load factor loadFactor without triggering a rehash.
      Parameters:
      initialCapacity - a positive int value
      loadFactor - a positive float
  • Method Details

    • fastCeil

      protected static long fastCeil(double v)
    • saturatedCast

      protected static int saturatedCast(long v)
    • isEmpty

      public boolean isEmpty()
      Tells whether this set is currently holding any elements.
      Returns:
      a boolean value
    • size

      public int size()
      Returns the number of distinct elements in this collection.
      Returns:
      an int value
    • capacity

      public abstract int capacity()
      Returns:
      the current physical capacity of the hash table.
    • ensureCapacity

      public void ensureCapacity(int desiredCapacity)
      Ensure that this hashtable has sufficient capacity to hold desiredCapacity additional elements without requiring a rehash. This is a tuning method you can call before doing a large insert.
      Parameters:
      desiredCapacity - an int value
    • compact

      public void compact()
      Compresses the hashtable to the minimum prime size (as defined by PrimeFinder) that will hold all of the elements currently in the table. If you have done a lot of remove operations and plan to do a lot of queries or insertions or iteration, it is a good idea to invoke this method. Doing so will accomplish two things:
      1. You'll free memory allocated to the table but no longer needed because of the remove()s.
      2. You'll get better query/insert/iterator performance because there won't be any REMOVED slots to skip over when probing for indices in the table.
    • setAutoCompactionFactor

      public void setAutoCompactionFactor(float factor)
      The auto-compaction factor controls whether and when a table performs a compact() automatically after a certain number of remove operations. If the value is non-zero, the number of removes that need to occur for auto-compaction is the size of table at the time of the previous compaction (or the initial capacity) multiplied by this factor.
      Setting this value to zero will disable auto-compaction.
      Parameters:
      factor - a float that indicates the auto-compaction factor
    • getAutoCompactionFactor

      public float getAutoCompactionFactor()
      Returns:
      a float that represents the auto-compaction factor.
      See Also:
    • trimToSize

      public final void trimToSize()
      This simply calls compact. It is included for symmetry with other collection classes. Note that the name of this method is somewhat misleading (which is why we prefer compact) as the load factor may require capacity above and beyond the size of this collection.
      See Also:
    • removeAt

      protected void removeAt(int index)
      Delete the record at index. Reduces the size of the collection by one.
      Parameters:
      index - an int value
    • clear

      public void clear()
      Empties the collection.
    • setUp

      protected int setUp(int initialCapacity)
      initializes the hashtable to a prime capacity which is at least initialCapacity + 1.
      Parameters:
      initialCapacity - an int value
      Returns:
      the actual capacity chosen
    • rehash

      protected abstract void rehash(int newCapacity)
      Rehashes the set.
      Parameters:
      newCapacity - an int value
    • tempDisableAutoCompaction

      public void tempDisableAutoCompaction()
      Temporarily disables auto-compaction. MUST be followed by calling reenableAutoCompaction(boolean).
    • reenableAutoCompaction

      public void reenableAutoCompaction(boolean check_for_compaction)
      Re-enable auto-compaction after it was disabled via tempDisableAutoCompaction().
      Parameters:
      check_for_compaction - True if compaction should be performed if needed before returning. If false, no compaction will be performed.
    • computeMaxSize

      protected void computeMaxSize(int capacity)
      Computes the values of maxSize. There will always be at least one free slot required.
      Parameters:
      capacity - an int value
    • computeNextAutoCompactionAmount

      protected void computeNextAutoCompactionAmount(int size)
      Computes the number of removes that need to happen before the next auto-compaction will occur.
      Parameters:
      size - an int that sets the auto-compaction limit.
    • postInsertHook

      protected final void postInsertHook(boolean usedFreeSlot)
      After an insert, this hook is called to adjust the size/free values of the set and to perform rehashing if necessary.
      Parameters:
      usedFreeSlot - the slot
    • calculateGrownCapacity

      protected int calculateGrownCapacity()
    • writeExternal

      public void writeExternal(ObjectOutput out) throws IOException
      Specified by:
      writeExternal in interface Externalizable
      Throws:
      IOException
    • readExternal

      public void readExternal(ObjectInput in) throws IOException, ClassNotFoundException
      Specified by:
      readExternal in interface Externalizable
      Throws:
      IOException
      ClassNotFoundException