Package org.jibx.util
Class StringSizedSet
java.lang.Object
org.jibx.util.StringSizedSet
Fixed size hash set of
String
values.- Author:
- Dennis M. Sosnoski
-
Field Summary
FieldsModifier and TypeFieldDescriptionstatic final double
Default fill fraction for sizing of tables.protected final int
Size of array used for keys.protected final int
Offset added (modulo table size) to slot number on collision.protected final String[]
Array of key table slots. -
Constructor Summary
ConstructorsConstructorDescriptionStringSizedSet
(int count) Constructor with only value count specified.StringSizedSet
(int count, double fill) Constructor with full specification. -
Method Summary
Modifier and TypeMethodDescriptionboolean
Add a key to the set.void
clear()
Set the table to the empty state.final boolean
Check if an entry is present in the table.private final int
freeSlot
(int slot) Find free slot number for entry.private int
standardFind
(String key) Standard find key in table.private final int
standardSlot
(String key) Standard base slot computation for a key.private final int
stepSlot
(int slot) Step the slot number for an entry.
-
Field Details
-
DEFAULT_FILL_FRACTION
public static final double DEFAULT_FILL_FRACTIONDefault fill fraction for sizing of tables.- See Also:
-
m_arraySize
protected final int m_arraySizeSize of array used for keys. -
m_keyTable
Array of key table slots. -
m_hitOffset
protected final int m_hitOffsetOffset added (modulo table size) to slot number on collision.
-
-
Constructor Details
-
StringSizedSet
public StringSizedSet(int count, double fill) Constructor with full specification.- Parameters:
count
- number of values to assume in sizing of tablefill
- fraction fill for table (maximum of0.7
, to prevent excessive collisions)
-
StringSizedSet
public StringSizedSet(int count) Constructor with only value count specified. Uses default fill fraction and miss value.- Parameters:
count
- number of values to assume in initial sizing of table
-
-
Method Details
-
stepSlot
private final int stepSlot(int slot) Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.- Parameters:
slot
- slot number to be stepped- Returns:
- stepped slot number
-
freeSlot
private final int freeSlot(int slot) Find free slot number for entry. Starts at the slot based directly on the hashed key value. If this slot is already occupied, it adds the collision offset (modulo the table size) to the slot number and checks that slot, repeating until an unused slot is found.- Parameters:
slot
- initial slot computed from key- Returns:
- slot at which entry was added
-
standardSlot
Standard base slot computation for a key. This method may be used directly for key lookup using either thehashCode()
method defined for the key objects or theSystem.identityHashCode()
method, as selected by the hash technique constructor parameter. To implement a hash class based on some other methods of hashing and/or equality testing, define a separate method in the subclass with a different name and use that method instead. This avoids the overhead caused by overrides of a very heavily used method.- Parameters:
key
- key value to be computed- Returns:
- base slot for key
-
standardFind
Standard find key in table. This usesequals
comparisons for the key values.- Parameters:
key
- to be found in table- Returns:
- index of matching key, or
-index-1
of slot to be used for inserting key in table if not already present (always negative)
-
add
Add a key to the set. If the key is already present in the set, this does nothing.- Parameters:
key
- key to be added to table (non-null
)- Returns:
true
if added,false
if already present value if key not previously present in table
-
contains
Check if an entry is present in the table.- Parameters:
key
- key to be found- Returns:
true
if key found in table,false
if not
-
clear
public void clear()Set the table to the empty state.
-