|
| |
|
| java.lang.Object
 gnu.trove.THash
All known Subclasses: gnu.trove.TPrimitiveHash, gnu.trove.TObjectHash,
| THash | | abstract public class THash implements Cloneable(Code) | | Base class for hashtables that use open addressing to resolve
collisions.
Created: Wed Nov 28 21:11:16 2001
author:
Eric D. Friedman
author:
Rob Eden (auto-compaction)
version:
$Id: THash.java,v 1.10 2007/11/01 16:08:14 robeden Exp $ |
| Field Summary | |
| final protected static int | DEFAULT_INITIAL_CAPACITY
the default initial capacity for the hash table. | | final 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 factor for the table. | | protected transient 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 transient int | _size
the current number of occupied slots in the hash. |
| Constructor Summary | |
| public | THash()
Creates a new THash instance with the default
capacity and load factor. | | 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. | | 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. |
| Method Summary | |
| protected int | calculateGrownCapacity()
| | abstract protected int | capacity()
| | public void | clear()
Empties the collection. | | public Object | clone()
| | 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. | | public void | ensureCapacity(int desiredCapacity)
Ensure that this hashtable has sufficient capacity to hold
desiredCapacity additional elements without
requiring a rehash. | | public float | getAutoCompactionFactor()
| | public boolean | isEmpty()
Tells whether this set is currently holding any elements. | | final 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
THash.tempDisableAutoCompaction() .
Parameters:
check_for_compaction - True if compaction should be performed if neededbefore returning. | | abstract protected void | rehash(int newCapacity)
Rehashes the set. | | protected void | removeAt(int index)
Delete the record at index. | | public void | setAutoCompactionFactor(float factor)
The auto-compaction factor controls whether and when a table performs a
THash.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. | | public int | size()
Returns the number of distinct elements in this collection. | | protected void | tempDisableAutoCompaction()
Temporarily disables auto-compaction. | | final public void | trimToSize()
This simply calls
THash.compact compact . |
| DEFAULT_INITIAL_CAPACITY | | final protected static int DEFAULT_INITIAL_CAPACITY(Code) | | 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 | | final protected static float DEFAULT_LOAD_FACTOR(Code) | | the load above which rehashing occurs.
|
| _autoCompactRemovesRemaining | | protected int _autoCompactRemovesRemaining(Code) | | The number of removes that should be performed before an auto-compaction occurs.
|
| _free | | protected transient int _free(Code) | | the current number of free slots in the hash.
|
| _loadFactor | | protected float _loadFactor(Code) | | 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(Code) | | The maximum number of elements allowed without allocating more
space.
|
| _size | | protected transient int _size(Code) | | the current number of occupied slots in the hash.
|
| THash | | public THash()(Code) | | Creates a new THash instance with the default
capacity and load factor.
|
| THash | | public THash(int initialCapacity)(Code) | | 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)(Code) | | 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
Parameters:
loadFactor - a float value |
| calculateGrownCapacity | | protected int calculateGrownCapacity()(Code) | | |
| capacity | | abstract protected int capacity()(Code) | | the current physical capacity of the hash table. |
| clear | | public void clear()(Code) | | Empties the collection.
|
| compact | | public void compact()(Code) | | 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.
|
| ensureCapacity | | public void ensureCapacity(int desiredCapacity)(Code) | | 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()(Code) | | Tells whether this set is currently holding any elements.
a boolean value |
| postInsertHook | | final protected void postInsertHook(boolean usedFreeSlot)(Code) | | 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)(Code) | | Re-enable auto-compaction after it was disabled via
THash.tempDisableAutoCompaction() .
Parameters:
check_for_compaction - True if compaction should be performed if neededbefore returning. If false, no compaction will beperformed. |
| rehash | | abstract protected void rehash(int newCapacity)(Code) | | Rehashes the set.
Parameters:
newCapacity - an int value |
| removeAt | | protected void removeAt(int index)(Code) | | Delete the record at index. Reduces the size of the
collection by one.
Parameters:
index - an int value |
| setAutoCompactionFactor | | public void setAutoCompactionFactor(float factor)(Code) | | The auto-compaction factor controls whether and when a table performs a
THash.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.
|
| setUp | | protected int setUp(int initialCapacity)(Code) | | initializes the hashtable to a prime capacity which is at least
initialCapacity + 1.
Parameters:
initialCapacity - an int value the actual capacity chosen |
| size | | public int size()(Code) | | Returns the number of distinct elements in this collection.
an int value |
| tempDisableAutoCompaction | | protected void tempDisableAutoCompaction()(Code) | | Temporarily disables auto-compaction. MUST be followed by calling
THash.reenableAutoCompaction .
|
| trimToSize | | final public void trimToSize()(Code) | | This simply calls
THash.compact 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.compact |
|
|
|