Package org.jibx.util
Class StringIntSizedMap
- java.lang.Object
-
- org.jibx.util.StringIntSizedMap
-
public class StringIntSizedMap extends java.lang.Object
Fixed size hash map usingString
values as keys mapped to primitiveint
values.- Author:
- Dennis M. Sosnoski
-
-
Field Summary
Fields Modifier and Type Field Description static double
DEFAULT_FILL_FRACTION
Default fill fraction for sizing of tables.static int
DEFAULT_NOT_FOUND
Default value returned when key not found in table.protected int
m_arraySize
Size of array used for keys.protected int
m_hitOffset
Offset added (modulo table size) to slot number on collision.protected java.lang.String[]
m_keyTable
Array of key table slots.protected int
m_notFoundValue
Value returned when key not found in table.protected int[]
m_valueTable
Array of value table slots.
-
Constructor Summary
Constructors Constructor Description StringIntSizedMap(int count)
Constructor with only value count specified.StringIntSizedMap(int count, double fill, int miss)
Constructor with full specification.StringIntSizedMap(int count, int miss)
Constructor with value count and miss value specified.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description int
add(java.lang.String key, int value)
Add an entry to the table.void
clear()
Set the table to the empty state.boolean
containsKey(java.lang.String key)
Check if an entry is present in the table.private int
freeSlot(int slot)
Find free slot number for entry.int
get(java.lang.String key)
Find an entry in the table.private int
standardFind(java.lang.String key)
Standard find key in table.private int
standardSlot(java.lang.String key)
Standard base slot computation for a key.private int
stepSlot(int slot)
Step the slot number for an entry.
-
-
-
Field Detail
-
DEFAULT_FILL_FRACTION
public static final double DEFAULT_FILL_FRACTION
Default fill fraction for sizing of tables.- See Also:
- Constant Field Values
-
DEFAULT_NOT_FOUND
public static final int DEFAULT_NOT_FOUND
Default value returned when key not found in table.- See Also:
- Constant Field Values
-
m_arraySize
protected final int m_arraySize
Size of array used for keys.
-
m_keyTable
protected final java.lang.String[] m_keyTable
Array of key table slots.
-
m_valueTable
protected final int[] m_valueTable
Array of value table slots.
-
m_notFoundValue
protected final int m_notFoundValue
Value returned when key not found in table.
-
m_hitOffset
protected final int m_hitOffset
Offset added (modulo table size) to slot number on collision.
-
-
Constructor Detail
-
StringIntSizedMap
public StringIntSizedMap(int count, double fill, int miss)
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)miss
- value returned when key not found in table
-
StringIntSizedMap
public StringIntSizedMap(int count, int miss)
Constructor with value count and miss value specified. Uses default fill fraction.- Parameters:
count
- number of values to assume in initial sizing of tablemiss
- value returned when key not found in table
-
StringIntSizedMap
public StringIntSizedMap(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 Detail
-
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
private final int standardSlot(java.lang.String key)
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
private int standardFind(java.lang.String key)
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
public int add(java.lang.String key, int value)
Add an entry to the table. If the key is already present in the table, this replaces the existing value associated with the key.- Parameters:
key
- key to be added to table (non-null
)value
- associated value for key- Returns:
- value previously associated with key, or reserved not found value if key not previously present in table
-
containsKey
public final boolean containsKey(java.lang.String key)
Check if an entry is present in the table. This method is supplied to support the use of values matching the reserved not found value.- Parameters:
key
- key for entry to be found- Returns:
true
if key found in table,false
if not
-
get
public final int get(java.lang.String key)
Find an entry in the table.- Parameters:
key
- key for entry to be returned- Returns:
- value for key, or reserved not found value if key not found
-
clear
public void clear()
Set the table to the empty state.
-
-