org.apache.commons.math.util

## Class OpenIntToDoubleHashMap

- java.lang.Object
- - org.apache.commons.math.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 a `ConcurrentModificationException` when they detect the map has been modified during iteration.

Since:
  2.0
Version:
  $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
See Also:
  Serialized Form

### Nested Class Summary

Nested Classes
`class` `OpenIntToDoubleHashMap.Iterator` Iterator class for the map.

### Field Summary

Fields
`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 Summary

Constructors
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.

### Method Summary

Methods
`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.

### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

### 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 map
  `missingEntries` - 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 table
  `states` - states table
  `key` - key to lookup
  `mask` - 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 hash
  `j` - 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 check
  `index` - 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 associated
  `value` - 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 read
  `java.lang.ClassNotFoundException` - if the class corresponding to the serialized object cannot be found