gnu.trove

Class THash

public abstract class THash extends 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.6 2002/09/25 05:43:04 ericdf Exp $

Author: Eric D. Friedman

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	_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 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	computeMaxSize(int capacity) Computes the values of maxSize.
void	ensureCapacity(int desiredCapacity) Ensure that this hashtable has sufficient capacity to hold `desiredCapacity additional elements without requiring a rehash.`
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 abstract void	rehash(int newCapacity) Rehashes the set.
protected void	removeAt(int index) Delete the record at `index`.
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.
void	trimToSize() This simply calls `compact`.

Field Detail

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.

DEFAULT_LOAD_FACTOR

protected static final float DEFAULT_LOAD_FACTOR

the load above which rehashing occurs.

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

_size

protected transient int _size

the current number of occupied slots in the hash.

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

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:

You'll free memory allocated to the table but no longer needed because of the remove()s.
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.

computeMaxSize

private final void computeMaxSize(int capacity)

Computes the values of maxSize. There will always be at least one free slot required.

Parameters: capacity an int value

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

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. 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 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 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: THash Overview Package Class Use Tree Deprecated Index Help Prev Class Next Class Frames NoFrames All Classes Summary: Nested Field Constr Method Detail: Field Constr Method