Package gnu.trove.impl.hash
Class THash
java.lang.Object
gnu.trove.impl.hash.THash
- All Implemented Interfaces:
Externalizable
,Serializable
- Direct Known Subclasses:
TObjectHash
,TPrimitiveHash
Base class for hashtables that use open addressing to resolve
collisions.
Created: Wed Nov 28 21:11:16 2001
- See Also:
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected 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
ConstructorsConstructorDescriptionTHash()
Creates a newTHash
instance with the default capacity and load factor.THash
(int initialCapacity) Creates a newTHash
instance with a prime capacity at or near the specified capacity and with the default load factor.THash
(int initialCapacity, float loadFactor) Creates a newTHash
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 TypeMethodDescriptionprotected int
abstract int
capacity()
void
clear()
Empties the collection.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.protected void
computeMaxSize
(int capacity) Computes the values of maxSize.protected void
computeNextAutoCompactionAmount
(int size) 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
isEmpty()
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 viatempDisableAutoCompaction()
.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
setAutoCompactionFactor
(float factor) The auto-compaction factor controls whether and when a table performs acompact()
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.void
Temporarily disables auto-compaction.final void
This simply callscompact
.void
-
Field Details
-
DEFAULT_LOAD_FACTOR
protected static final float DEFAULT_LOAD_FACTORthe load above which rehashing occurs.- See Also:
-
DEFAULT_CAPACITY
protected static final int DEFAULT_CAPACITYthe 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 _sizethe current number of occupied slots in the hash. -
_free
protected transient int _freethe current number of free slots in the hash. -
_loadFactor
protected float _loadFactorDetermines 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 _maxSizeThe maximum number of elements allowed without allocating more space. -
_autoCompactRemovesRemaining
protected int _autoCompactRemovesRemainingThe number of removes that should be performed before an auto-compaction occurs. -
_autoCompactionFactor
protected float _autoCompactionFactorThe auto-compaction factor for the table.- See Also:
-
_autoCompactTemporaryDisable
protected transient boolean _autoCompactTemporaryDisable- See Also:
-
-
Constructor Details
-
THash
public THash()Creates a newTHash
instance with the default capacity and load factor. -
THash
public THash(int initialCapacity) Creates a newTHash
instance with a prime capacity at or near the specified capacity and with the default load factor.- Parameters:
initialCapacity
- anint
value
-
THash
public THash(int initialCapacity, float loadFactor) Creates a newTHash
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 positiveint
valueloadFactor
- a positivefloat
-
-
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
- anint
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:
- 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.
-
setAutoCompactionFactor
public void setAutoCompactionFactor(float factor) The auto-compaction factor controls whether and when a table performs acompact()
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 callscompact
. 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
- anint
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
- anint
value- Returns:
- the actual capacity chosen
-
rehash
protected abstract void rehash(int newCapacity) Rehashes the set.- Parameters:
newCapacity
- anint
value
-
tempDisableAutoCompaction
public void tempDisableAutoCompaction()Temporarily disables auto-compaction. MUST be followed by callingreenableAutoCompaction(boolean)
. -
reenableAutoCompaction
public void reenableAutoCompaction(boolean check_for_compaction) Re-enable auto-compaction after it was disabled viatempDisableAutoCompaction()
.- 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
- anint
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
- Specified by:
writeExternal
in interfaceExternalizable
- Throws:
IOException
-
readExternal
- Specified by:
readExternal
in interfaceExternalizable
- Throws:
IOException
ClassNotFoundException
-