Package gnu.trove

Class THash

  • All Implemented Interfaces:
    java.io.Externalizable, java.io.Serializable, java.lang.Cloneable
    Direct Known Subclasses:
    TObjectHash, TPrimitiveHash

    public abstract class THash
    extends java.lang.Object
    implements java.lang.Cloneable, java.io.Externalizable
    Base class for hashtables that use open addressing to resolve collisions. Created: Wed Nov 28 21:11:16 2001
    Version:
    $Id: THash.java,v 1.14 2008/10/08 16:39:10 robeden Exp $
    Author:
    Eric D. Friedman, Rob Eden (auto-compaction)
    See Also:
    Serialized Form
    • Field Summary

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

      Constructors 
      Constructor Description
      THash()
      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

      All Methods Instance Methods Abstract Methods Concrete Methods 
      Modifier and Type Method Description
      protected int calculateGrownCapacity()  
      protected abstract int capacity()  
      void clear()
      Empties the collection.
      java.lang.Object clone()  
      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.
      void ensureCapacity​(int desiredCapacity)
      Ensure that this hashtable has sufficient capacity to hold desiredCapacity additional elements without requiring a rehash.
      float getAutoCompactionFactor()  
      boolean isEmpty()
      Tells whether this set is currently holding any elements.
      protected 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 readExternal​(java.io.ObjectInput in)  
      protected 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.
      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.
      protected int setUp​(int initialCapacity)
      initializes the hashtable to a prime capacity which is at least initialCapacity + 1.
      int size()
      Returns the number of distinct elements in this collection.
      protected void tempDisableAutoCompaction()
      Temporarily disables auto-compaction.
      void trimToSize()
      This simply calls compact.
      void writeExternal​(java.io.ObjectOutput out)  
      • Methods inherited from class java.lang.Object

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

      • DEFAULT_LOAD_FACTOR

        protected static final float DEFAULT_LOAD_FACTOR
        the load above which rehashing occurs.
        See Also:
        Constant Field Values
      • DEFAULT_INITIAL_CAPACITY

        protected static final int DEFAULT_INITIAL_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:
        Constant Field Values
      • _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.
    • Constructor Detail

      • 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 - an int value
        loadFactor - a float value
    • Method Detail

      • clone

        public java.lang.Object clone()
        Overrides:
        clone in class java.lang.Object
      • 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

        protected 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.

      • 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:
        compact()
      • 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

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

        protected 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.
      • 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.
      • calculateGrownCapacity

        protected int calculateGrownCapacity()
      • writeExternal

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

        public void readExternal​(java.io.ObjectInput in)
                          throws java.io.IOException,
                                 java.lang.ClassNotFoundException
        Specified by:
        readExternal in interface java.io.Externalizable
        Throws:
        java.io.IOException
        java.lang.ClassNotFoundException