gnu.trove

Class THash

Implemented Interfaces:
Cloneable

public abstract class THash
extends java.lang.Object
implements Cloneable

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.9 2007/06/29 20:03:10 robeden Exp $
Authors:
Eric D. Friedman
Rob Eden (auto-compaction)

Field Summary

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.
protected int
_autoCompactRemovesRemaining
The number of removes that should be performed before an auto-compaction occurs.
protected float
_autoCompactionFactor
The auto-compaction falctor for the table.
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.

Constructor Summary

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

protected int
calculateGrownCapacity()
protected abstract int
capacity()
void
clear()
Empties the collection.
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.
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() automatcially 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.

Field Details

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.
Field Value:
10

DEFAULT_LOAD_FACTOR

protected static final float DEFAULT_LOAD_FACTOR
the load above which rehashing occurs.
Field Value:
0.0f

_autoCompactRemovesRemaining

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

_autoCompactionFactor

protected float _autoCompactionFactor
The auto-compaction falctor for the table.

_free

protected 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 <10 loadFactor <321.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.

_size

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

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

Method Details

calculateGrownCapacity

protected int calculateGrownCapacity()

capacity

protected abstract int capacity()
Returns:
the current physical capacity of the hash table.

clear

public void clear()
Empties the collection.

clone

public Object clone()

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.

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

getAutoCompactionFactor

public float getAutoCompactionFactor()

isEmpty

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

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.

reenableAutoCompaction

protected void reenableAutoCompaction(boolean check_for_compaction)
Parameters:
check_for_compaction - True if compaction should be performed if needed before returning. If false, no compaction will be performed.

rehash

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

removeAt

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

setAutoCompactionFactor

public void setAutoCompactionFactor(float factor)
The auto-compaction factor controls whether and when a table performs a compact() automatcially 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.


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

size

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

tempDisableAutoCompaction

protected void tempDisableAutoCompaction()

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()

GNU Trove is copyright B) 2001-2007 Eric D. Friedman. All Rights Reserved.