## org.apache.commons.math.util
Class OpenIntToFieldHashMap<T extends FieldElement<T>>

    java.lang.Object
      org.apache.commons.math.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
Version:
  $Revision: 990655 $ $Date: 2010-08-29 23:49:40 +0200 (dim. 29 août 2010) $
See Also:
  Serialized Form

Nested Class Summary
`class` `OpenIntToFieldHashMap.Iterator` Iterator class for the map.

Field Summary
`private int` `count` Modifications count.
`private static int` `DEFAULT_EXPECTED_SIZE` Default starting size.
`private Field<T>` `field` Field to which the elements belong.
`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 T` `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 T[]` `values` Values table.

Constructor Summary
`OpenIntToFieldHashMap(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 size
`OpenIntToFieldHashMap(OpenIntToFieldHashMap<T> source)` Copy constructor.

Method Summary
`private T[]` `buildArray(int length)` Build an array of elements.
`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 T` `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
`T` `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
`OpenIntToFieldHashMap.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
`T` `put(int key, T value)` Put a value associated with a key in the map.
`private void` `readObject(ObjectInputStream stream)` Read a serialized object.
`T` `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

### field

    private final Field<T extends FieldElement<T>> field

  Field to which the elements belong.

### keys

    private int[] keys

  Keys table.

### values

    private T extends FieldElement<T>[] values

  Values table.

### states

    private byte[] states

  States table.

### missingEntries

    private final T extends FieldElement<T> 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

### OpenIntToFieldHashMap

    public OpenIntToFieldHashMap(Field<T> field)

  Build an empty map with default size and using zero for missing entries.

  Parameters:
    `field` - field to which the elements belong

### OpenIntToFieldHashMap

    public OpenIntToFieldHashMap(Field<T> field,
                                 T missingEntries)

  Build an empty map with default size

  Parameters:
    `field` - field to which the elements belong
    `missingEntries` - value to return when a missing entry is fetched

### OpenIntToFieldHashMap

    public OpenIntToFieldHashMap(Field<T> field,
                                 int expectedSize)

  Build an empty map with specified size and using zero for missing entries.

  Parameters:
    `field` - field to which the elements belong
    `expectedSize` - expected number of elements in the map

### OpenIntToFieldHashMap

    public OpenIntToFieldHashMap(Field<T> field,
                                 int expectedSize,
                                 T missingEntries)

  Build an empty map with specified size.

  Parameters:
    `field` - field to which the elements belong
    `expectedSize` - expected number of elements in the map
    `missingEntries` - value to return when a missing entry is fetched

### OpenIntToFieldHashMap

    public OpenIntToFieldHashMap(OpenIntToFieldHashMap<T> 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 T 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 OpenIntToFieldHashMap.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 T 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 T doRemove(int index)

  Remove an element at specified index.

  Parameters:
    `index` - index of the element to remove
  Returns:
    removed value

### put

    public T put(int key,
                 T 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(ObjectInputStream stream)
                     throws IOException,
                            ClassNotFoundException

  Read a serialized object.

  Parameters:
    `stream` - input stream
  Throws:
    `IOException` - if object cannot be read
    `ClassNotFoundException` - if the class corresponding to the serialized object cannot be found

### buildArray

    private T[] buildArray(int length)

  Build an array of elements.

  Parameters:
    `length` - size of the array to build
  Returns:
    a new array

Copyright (c) 2003-2013 Apache Software Foundation