Package org.jibx.runtime.impl
Class StringIntHashMap
java.lang.Object
org.jibx.runtime.impl.StringIntHashMap
Hash map using
String
values as keys mapped to primitive
int
values. This implementation is unsynchronized in order to
provide the best possible performance for typical usage scenarios, so
explicit synchronization must be implemented by a wrapper class or directly
by the application in cases where instances are modified in a multithreaded
environment. The map implementation is not very efficient when resizing, but
works well when the size of the map is known in advance.- Version:
- 1.1
- Author:
- Dennis M. Sosnoski
-
Field Summary
FieldsModifier and TypeFieldDescriptionprotected static final double
Default fill fraction allowed before growing table.static final int
Default value returned when key not found in table.protected int
Size of array used for keys.protected int
Number of entries present in table.protected int
Entries allowed before growing table.protected final double
Fill fraction allowed for this hash table.protected int
Offset added (modulo table size) to slot number on collision.protected String[]
Array of key table slots.protected int
Value returned when key not found in table.protected int[]
Array of value table slots.protected static final int
Minimum size used for hash table. -
Constructor Summary
ConstructorsConstructorDescriptionDefault constructor.StringIntHashMap
(int count) Constructor with only size supplied.StringIntHashMap
(int count, double fill) Constructor with size and fill fraction specified.StringIntHashMap
(int count, double fill, int miss) Constructor with full specification.Copy (clone) constructor. -
Method Summary
Modifier and TypeMethodDescriptionint
Add an entry to the table.private int
assignSlot
(String key, int value) Assign slot for entry.clone()
Construct a copy of the table.final boolean
containsKey
(String key) Check if an entry is present in the table.private final int
freeSlot
(int slot) Find free slot number for entry.final int
Find an entry in the table.protected void
internalRemove
(int slot) Internal remove pair from the table.private boolean
reinsert
(int slot) Reinsert an entry into the hash map.int
Remove an entry from the table.private void
restructure
(String[] keys, int[] values) Restructure the table.private int
standardFind
(Object key) Standard find key in table.private final int
standardSlot
(Object key) Standard base slot computation for a key.private final int
stepSlot
(int slot) Step the slot number for an entry.
-
Field Details
-
DEFAULT_NOT_FOUND
public static final int DEFAULT_NOT_FOUNDDefault value returned when key not found in table.- See Also:
-
DEFAULT_FILL
protected static final double DEFAULT_FILLDefault fill fraction allowed before growing table.- See Also:
-
MINIMUM_SIZE
protected static final int MINIMUM_SIZEMinimum size used for hash table.- See Also:
-
m_fillFraction
protected final double m_fillFractionFill fraction allowed for this hash table. -
m_entryCount
protected int m_entryCountNumber of entries present in table. -
m_entryLimit
protected int m_entryLimitEntries allowed before growing table. -
m_arraySize
protected int m_arraySizeSize of array used for keys. -
m_hitOffset
protected int m_hitOffsetOffset added (modulo table size) to slot number on collision. -
m_keyTable
Array of key table slots. -
m_valueTable
protected int[] m_valueTableArray of value table slots. -
m_notFoundValue
protected int m_notFoundValueValue returned when key not found in table.
-
-
Constructor Details
-
StringIntHashMap
public StringIntHashMap(int count, double fill, int miss) Constructor with full specification.- Parameters:
count
- number of values to assume in initial sizing of tablefill
- fraction full allowed for table before growingmiss
- value returned when key not found in table
-
StringIntHashMap
public StringIntHashMap(int count, double fill) Constructor with size and fill fraction specified. Uses default hash technique and value returned when key not found in table.- Parameters:
count
- number of values to assume in initial sizing of tablefill
- fraction full allowed for table before growing
-
StringIntHashMap
public StringIntHashMap(int count) Constructor with only size supplied. Uses default hash technique and values for fill fraction and value returned when key not found in table.- Parameters:
count
- number of values to assume in initial sizing of table
-
StringIntHashMap
public StringIntHashMap()Default constructor. -
StringIntHashMap
Copy (clone) constructor.- Parameters:
base
- instance being copied
-
-
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.- Parameters:
key
- key value to be computed- Returns:
- base slot for key
-
standardFind
Standard find key in table. This method may be used directly for key lookup using either thehashCode()
method defined for the key objects or theSystem.identityHashCode()
method, and either theequals()
method defined for the key objects or the==
operator, 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
- 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)
-
reinsert
private boolean reinsert(int slot) Reinsert an entry into the hash map. This is used when the table is being directly modified, and does not adjust the count present or check the table capacity.- Parameters:
slot
- position of entry to be reinserted into hash map- Returns:
true
if the slot number used by the entry has has changed,false
if not
-
internalRemove
protected void internalRemove(int slot) Internal remove pair from the table. Removes the pair from the table by setting the key entry tonull
and adjusting the count present, then chains through the table to reinsert any other pairs which may have collided with the removed pair. If the associated value is an object reference, it should be set tonull
before this method is called.- Parameters:
slot
- index number of pair to be removed
-
restructure
Restructure the table. This is used when the table is increasing or decreasing in size, and works directly with the old table representation arrays. It inserts pairs from the old arrays directly into the table without adjusting the count present or checking the table size.- Parameters:
keys
- array of keysvalues
- array of values
-
assignSlot
Assign slot for entry. Starts at the slot found by the hashed key value. If this slot is already occupied, it steps the slot number and checks the resulting slot, repeating until an unused slot is found. This method does not check for duplicate keys, so it should only be used for internal reordering of the tables.- Parameters:
key
- to be added to tablevalue
- associated value for key- Returns:
- slot at which entry was added
-
add
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
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
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
-
remove
Remove an entry from the table. If multiple entries are present with the same key value, only the first one found will be removed.- Parameters:
key
- key to be removed from table- Returns:
- value associated with removed key, or reserved not found value if key not found in table
-
clone
Construct a copy of the table.
-