Package org.apache.commons.math3.util
Class OpenIntToDoubleHashMap
- java.lang.Object
-
- org.apache.commons.math3.util.OpenIntToDoubleHashMap
-
- All Implemented Interfaces:
java.io.Serializable
public class OpenIntToDoubleHashMap extends java.lang.Object implements java.io.Serializable
Open addressed map from int to double.This class provides a dedicated map from integers to doubles 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 aConcurrentModificationException
when they detect the map has been modified during iteration.- Since:
- 2.0
- See Also:
- Serialized Form
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description class
OpenIntToDoubleHashMap.Iterator
Iterator class for the map.
-
Field Summary
Fields Modifier and Type Field Description private int
count
Modifications count.private static int
DEFAULT_EXPECTED_SIZE
Default starting size.protected static byte
FREE
Status indicator for free table entries.protected static byte
FULL
Status indicator for full table entries.private int[]
keys
Keys table.private static float
LOAD_FACTOR
Load factor for the map.private int
mask
Bit mask for hash values.private double
missingEntries
Return value for missing entries.private static int
PERTURB_SHIFT
Number of bits to perturb the index when probing for collision resolution.protected static byte
REMOVED
Status indicator for removed table entries.private static int
RESIZE_MULTIPLIER
Multiplier for size growth when map fills up.private static long
serialVersionUID
Serializable version identifierprivate int
size
Current size of the map.private byte[]
states
States table.private double[]
values
Values table.
-
Constructor Summary
Constructors Constructor Description OpenIntToDoubleHashMap()
Build an empty map with default size and using NaN for missing entries.OpenIntToDoubleHashMap(double missingEntries)
Build an empty map with default sizeOpenIntToDoubleHashMap(int expectedSize)
Build an empty map with specified size and using NaN for missing entries.OpenIntToDoubleHashMap(int expectedSize, double missingEntries)
Build an empty map with specified size.OpenIntToDoubleHashMap(OpenIntToDoubleHashMap source)
Copy constructor.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description 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 double
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 inserteddouble
get(int key)
Get the stored value associated with the given keyprivate void
growTable()
Grow the tables.private static int
hashOf(int key)
Compute the hash value of a keyOpenIntToDoubleHashMap.Iterator
iterator()
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 resolutiondouble
put(int key, double value)
Put a value associated with a key in the map.private void
readObject(java.io.ObjectInputStream stream)
Read a serialized object.double
remove(int key)
Remove the value associated with a key.private boolean
shouldGrowTable()
Check if tables should grow due to increased size.int
size()
Get the number of elements stored in the map.
-
-
-
Field Detail
-
FREE
protected static final byte FREE
Status indicator for free table entries.- See Also:
- Constant Field Values
-
FULL
protected static final byte FULL
Status indicator for full table entries.- See Also:
- Constant Field Values
-
REMOVED
protected static final byte REMOVED
Status indicator for removed table entries.- See Also:
- Constant Field Values
-
serialVersionUID
private static final long serialVersionUID
Serializable version identifier- See Also:
- Constant Field Values
-
LOAD_FACTOR
private static final float LOAD_FACTOR
Load factor for the map.- See Also:
- Constant Field Values
-
DEFAULT_EXPECTED_SIZE
private static final int DEFAULT_EXPECTED_SIZE
Default starting size.This must be a power of two for bit mask to work properly.
- See Also:
- Constant Field Values
-
RESIZE_MULTIPLIER
private static final int RESIZE_MULTIPLIER
Multiplier for size growth when map fills up.This must be a power of two for bit mask to work properly.
- See Also:
- Constant Field Values
-
PERTURB_SHIFT
private static final int PERTURB_SHIFT
Number of bits to perturb the index when probing for collision resolution.- See Also:
- Constant Field Values
-
keys
private int[] keys
Keys table.
-
values
private double[] values
Values table.
-
states
private byte[] states
States table.
-
missingEntries
private final double missingEntries
Return value for missing entries.
-
size
private int size
Current size of the map.
-
mask
private int mask
Bit mask for hash values.
-
count
private transient int count
Modifications count.
-
-
Constructor Detail
-
OpenIntToDoubleHashMap
public OpenIntToDoubleHashMap()
Build an empty map with default size and using NaN for missing entries.
-
OpenIntToDoubleHashMap
public OpenIntToDoubleHashMap(double missingEntries)
Build an empty map with default size- Parameters:
missingEntries
- value to return when a missing entry is fetched
-
OpenIntToDoubleHashMap
public OpenIntToDoubleHashMap(int expectedSize)
Build an empty map with specified size and using NaN for missing entries.- Parameters:
expectedSize
- expected number of elements in the map
-
OpenIntToDoubleHashMap
public OpenIntToDoubleHashMap(int expectedSize, double missingEntries)
Build an empty map with specified size.- Parameters:
expectedSize
- expected number of elements in the mapmissingEntries
- value to return when a missing entry is fetched
-
OpenIntToDoubleHashMap
public OpenIntToDoubleHashMap(OpenIntToDoubleHashMap source)
Copy constructor.- Parameters:
source
- map to copy
-
-
Method Detail
-
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
public double get(int key)
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
public OpenIntToDoubleHashMap.Iterator 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
public double remove(int key)
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
private double doRemove(int index)
Remove an element at specified index.- Parameters:
index
- index of the element to remove- Returns:
- removed value
-
put
public double put(int key, double value)
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
private void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
Read a serialized object.- Parameters:
stream
- input stream- Throws:
java.io.IOException
- if object cannot be readjava.lang.ClassNotFoundException
- if the class corresponding to the serialized object cannot be found
-
-