Package org.apache.commons.math3.util
Class OpenIntToFieldHashMap<T extends FieldElement<T>>
java.lang.Object
org.apache.commons.math3.util.OpenIntToFieldHashMap<T>
- Type Parameters:
T
- the type of the field elements
- All Implemented Interfaces:
Serializable
public class OpenIntToFieldHashMap<T extends FieldElement<T>>
extends Object
implements Serializable
Open addressed map from int to FieldElement.
This class provides a dedicated map from integers to FieldElements with a
much smaller memory overhead than standard java.util.Map
.
This class is not synchronized. The specialized iterators returned by
iterator()
are fail-fast: they throw a
ConcurrentModificationException
when they detect the map has been
modified during iteration.
- Since:
- 2.0
- See Also:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionclass
Iterator class for the map. -
Field Summary
FieldsModifier and TypeFieldDescriptionprivate int
Modifications count.private static final int
Default starting size.Field to which the elements belong.protected static final byte
Status indicator for free table entries.protected static final byte
Status indicator for full table entries.private int[]
Keys table.private static final float
Load factor for the map.private int
Bit mask for hash values.private final T
Return value for missing entries.private static final int
Number of bits to perturb the index when probing for collision resolution.protected static final byte
Status indicator for removed table entries.private static final int
Multiplier for size growth when map fills up.private static final long
Serializable version identifier.private int
Current size of the map.private byte[]
States table.private T[]
Values table. -
Constructor Summary
ConstructorsConstructorDescriptionOpenIntToFieldHashMap
(Field<T> field) Build an empty map with default size and using zero for missing entries.OpenIntToFieldHashMap
(Field<T> field, int expectedSize) Build an empty map with specified size and using zero for missing entries.OpenIntToFieldHashMap
(Field<T> field, int expectedSize, T missingEntries) Build an empty map with specified size.OpenIntToFieldHashMap
(Field<T> field, T missingEntries) Build an empty map with default sizeOpenIntToFieldHashMap
(OpenIntToFieldHashMap<T> source) Copy constructor. -
Method Summary
Modifier and TypeMethodDescriptionprivate T[]
buildArray
(int length) Build an array of elements.private static int
changeIndexSign
(int index) Change the index signprivate static int
computeCapacity
(int expectedSize) Compute the capacity needed for a given size.boolean
containsKey
(int key) Check if a value is associated with a key.private boolean
containsKey
(int key, int index) Check if the tables contain an element associated with specified key at specified index.private T
doRemove
(int index) Remove an element at specified index.private int
findInsertionIndex
(int key) Find the index at which a key should be insertedprivate static int
findInsertionIndex
(int[] keys, byte[] states, int key, int mask) Find the index at which a key should be insertedget
(int key) Get the stored value associated with the given keyprivate void
Grow the tables.private static int
hashOf
(int key) Compute the hash value of a keyiterator()
Get an iterator over map elements.private static int
nextPowerOfTwo
(int i) Find the smallest power of two greater than the input valueprivate static int
perturb
(int hash) Perturb the hash for starting probing.private static int
probe
(int perturb, int j) Compute next probe for collision resolutionPut a value associated with a key in the map.private void
readObject
(ObjectInputStream stream) Read a serialized object.remove
(int key) Remove the value associated with a key.private boolean
Check if tables should grow due to increased size.int
size()
Get the number of elements stored in the map.
-
Field Details
-
FREE
protected static final byte FREEStatus indicator for free table entries.- See Also:
-
FULL
protected static final byte FULLStatus indicator for full table entries.- See Also:
-
REMOVED
protected static final byte REMOVEDStatus indicator for removed table entries.- See Also:
-
serialVersionUID
private static final long serialVersionUIDSerializable version identifier.- See Also:
-
LOAD_FACTOR
private static final float LOAD_FACTORLoad factor for the map.- See Also:
-
DEFAULT_EXPECTED_SIZE
private static final int DEFAULT_EXPECTED_SIZEDefault starting size.This must be a power of two for bit mask to work properly.
- See Also:
-
RESIZE_MULTIPLIER
private static final int RESIZE_MULTIPLIERMultiplier for size growth when map fills up.This must be a power of two for bit mask to work properly.
- See Also:
-
PERTURB_SHIFT
private static final int PERTURB_SHIFTNumber of bits to perturb the index when probing for collision resolution.- See Also:
-
field
Field to which the elements belong. -
keys
private int[] keysKeys table. -
values
Values table. -
states
private byte[] statesStates table. -
missingEntries
Return value for missing entries. -
size
private int sizeCurrent size of the map. -
mask
private int maskBit mask for hash values. -
count
private transient int countModifications count.
-
-
Constructor Details
-
OpenIntToFieldHashMap
Build an empty map with default size and using zero for missing entries.- Parameters:
field
- field to which the elements belong
-
OpenIntToFieldHashMap
Build an empty map with default size- Parameters:
field
- field to which the elements belongmissingEntries
- value to return when a missing entry is fetched
-
OpenIntToFieldHashMap
Build an empty map with specified size and using zero for missing entries.- Parameters:
field
- field to which the elements belongexpectedSize
- expected number of elements in the map
-
OpenIntToFieldHashMap
Build an empty map with specified size.- Parameters:
field
- field to which the elements belongexpectedSize
- expected number of elements in the mapmissingEntries
- value to return when a missing entry is fetched
-
OpenIntToFieldHashMap
Copy constructor.- Parameters:
source
- map to copy
-
-
Method Details
-
computeCapacity
private static int computeCapacity(int expectedSize) Compute the capacity needed for a given size.- Parameters:
expectedSize
- expected size of the map- Returns:
- capacity to use for the specified size
-
nextPowerOfTwo
private static int nextPowerOfTwo(int i) Find the smallest power of two greater than the input value- Parameters:
i
- input value- Returns:
- smallest power of two greater than the input value
-
get
Get the stored value associated with the given key- Parameters:
key
- key associated with the data- Returns:
- data associated with the key
-
containsKey
public boolean containsKey(int key) Check if a value is associated with a key.- Parameters:
key
- key to check- Returns:
- true if a value is associated with key
-
iterator
Get an iterator over map elements.The specialized iterators returned are fail-fast: they throw a
ConcurrentModificationException
when they detect the map has been modified during iteration.- Returns:
- iterator over the map elements
-
perturb
private static int perturb(int hash) Perturb the hash for starting probing.- Parameters:
hash
- initial hash- Returns:
- perturbed hash
-
findInsertionIndex
private int findInsertionIndex(int key) Find the index at which a key should be inserted- Parameters:
key
- key to lookup- Returns:
- index at which key should be inserted
-
findInsertionIndex
private static int findInsertionIndex(int[] keys, byte[] states, int key, int mask) Find the index at which a key should be inserted- Parameters:
keys
- keys tablestates
- states tablekey
- key to lookupmask
- bit mask for hash values- Returns:
- index at which key should be inserted
-
probe
private static int probe(int perturb, int j) Compute next probe for collision resolution- Parameters:
perturb
- perturbed hashj
- previous probe- Returns:
- next probe
-
changeIndexSign
private static int changeIndexSign(int index) Change the index sign- Parameters:
index
- initial index- Returns:
- changed index
-
size
public int size()Get the number of elements stored in the map.- Returns:
- number of elements stored in the map
-
remove
Remove the value associated with a key.- Parameters:
key
- key to which the value is associated- Returns:
- removed value
-
containsKey
private boolean containsKey(int key, int index) Check if the tables contain an element associated with specified key at specified index.- Parameters:
key
- key to checkindex
- index to check- Returns:
- true if an element is associated with key at index
-
doRemove
Remove an element at specified index.- Parameters:
index
- index of the element to remove- Returns:
- removed value
-
put
Put a value associated with a key in the map.- Parameters:
key
- key to which value is associatedvalue
- value to put in the map- Returns:
- previous value associated with the key
-
growTable
private void growTable()Grow the tables. -
shouldGrowTable
private boolean shouldGrowTable()Check if tables should grow due to increased size.- Returns:
- true if tables should grow
-
hashOf
private static int hashOf(int key) Compute the hash value of a key- Parameters:
key
- key to hash- Returns:
- hash value of the key
-
readObject
Read a serialized object.- Parameters:
stream
- input stream- Throws:
IOException
- if object cannot be readClassNotFoundException
- if the class corresponding to the serialized object cannot be found
-
buildArray
Build an array of elements.- Parameters:
length
- size of the array to build- Returns:
- a new array
-