public class OpenIntToDoubleHashMap
extends java.lang.Object
implements java.io.Serializable
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 a
ConcurrentModificationException
when they detect the map has been
modified during iteration.
Modifier and Type | Class and Description |
---|---|
class |
OpenIntToDoubleHashMap.Iterator
Iterator class for the map.
|
Modifier and Type | Field and 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 identifier
|
private int |
size
Current size of the map.
|
private byte[] |
states
States table.
|
private double[] |
values
Values table.
|
Constructor and Description |
---|
OpenIntToDoubleHashMap()
Build an empty map with default size and using NaN for missing entries.
|
OpenIntToDoubleHashMap(double missingEntries)
Build an empty map with default size
|
OpenIntToDoubleHashMap(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.
|
Modifier and Type | Method and Description |
---|---|
private static int |
changeIndexSign(int index)
Change the index sign
|
private 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 inserted
|
private static int |
findInsertionIndex(int[] keys,
byte[] states,
int key,
int mask)
Find the index at which a key should be inserted
|
double |
get(int key)
Get the stored value associated with the given key
|
private void |
growTable()
Grow the tables.
|
private static int |
hashOf(int key)
Compute the hash value of a key
|
OpenIntToDoubleHashMap.Iterator |
iterator()
Get an iterator over map elements.
|
private static int |
nextPowerOfTwo(int i)
Find the smallest power of two greater than the input value
|
private static int |
perturb(int hash)
Perturb the hash for starting probing.
|
private static int |
probe(int perturb,
int j)
Compute next probe for collision resolution
|
double |
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.
|
protected static final byte FREE
protected static final byte FULL
protected static final byte REMOVED
private static final long serialVersionUID
private static final float LOAD_FACTOR
private static final int DEFAULT_EXPECTED_SIZE
This must be a power of two for bit mask to work properly.
private static final int RESIZE_MULTIPLIER
This must be a power of two for bit mask to work properly.
private static final int PERTURB_SHIFT
private int[] keys
private double[] values
private byte[] states
private final double missingEntries
private int size
private int mask
private transient int count
public OpenIntToDoubleHashMap()
public OpenIntToDoubleHashMap(double missingEntries)
missingEntries
- value to return when a missing entry is fetchedpublic OpenIntToDoubleHashMap(int expectedSize)
expectedSize
- expected number of elements in the mappublic OpenIntToDoubleHashMap(int expectedSize, double missingEntries)
expectedSize
- expected number of elements in the mapmissingEntries
- value to return when a missing entry is fetchedpublic OpenIntToDoubleHashMap(OpenIntToDoubleHashMap source)
source
- map to copyprivate static int computeCapacity(int expectedSize)
expectedSize
- expected size of the mapprivate static int nextPowerOfTwo(int i)
i
- input valuepublic double get(int key)
key
- key associated with the datapublic boolean containsKey(int key)
key
- key to checkpublic OpenIntToDoubleHashMap.Iterator iterator()
The specialized iterators returned are fail-fast: they throw a
ConcurrentModificationException
when they detect the map
has been modified during iteration.
private static int perturb(int hash)
hash
- initial hashprivate int findInsertionIndex(int key)
key
- key to lookupprivate static int findInsertionIndex(int[] keys, byte[] states, int key, int mask)
keys
- keys tablestates
- states tablekey
- key to lookupmask
- bit mask for hash valuesprivate static int probe(int perturb, int j)
perturb
- perturbed hashj
- previous probeprivate static int changeIndexSign(int index)
index
- initial indexpublic int size()
public double remove(int key)
key
- key to which the value is associatedprivate boolean containsKey(int key, int index)
key
- key to checkindex
- index to checkprivate double doRemove(int index)
index
- index of the element to removepublic double put(int key, double value)
key
- key to which value is associatedvalue
- value to put in the mapprivate void growTable()
private boolean shouldGrowTable()
private static int hashOf(int key)
key
- key to hashprivate void readObject(java.io.ObjectInputStream stream) throws java.io.IOException, java.lang.ClassNotFoundException
stream
- input streamjava.io.IOException
- if object cannot be readjava.lang.ClassNotFoundException
- if the class corresponding
to the serialized object cannot be foundCopyright (c) 2003-2013 Apache Software Foundation