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 Classes
    Modifier and Type
    Class
    Description
    class 
    OpenIntToFieldHashMap.Iterator
    Iterator class for the map.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private int
    count
    Modifications count.
    private static final int
    DEFAULT_EXPECTED_SIZE
    Default starting size.
    private final Field<T>
    field
    Field to which the elements belong.
    protected static final byte
    FREE
    Status indicator for free table entries.
    protected static final byte
    FULL
    Status indicator for full table entries.
    private int[]
    keys
    Keys table.
    private static final float
    LOAD_FACTOR
    Load factor for the map.
    private int
    mask
    Bit mask for hash values.
    private final T
    missingEntries
    Return value for missing entries.
    private static final int
    PERTURB_SHIFT
    Number of bits to perturb the index when probing for collision resolution.
    protected static final byte
    REMOVED
    Status indicator for removed table entries.
    private static final int
    RESIZE_MULTIPLIER
    Multiplier for size growth when map fills up.
    private static final 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

    Constructors
    Constructor
    Description
    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

    Modifier and Type
    Method
    Description
    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<T>.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 Object

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

  • Field Details

    • FREE

      protected static final byte FREE
      Status indicator for free table entries.
      See Also:

    • FULL

      protected static final byte FULL
      Status indicator for full table entries.
      See Also:

    • REMOVED

      protected static final byte REMOVED
      Status indicator for removed table entries.
      See Also:

    • serialVersionUID

      private static final long serialVersionUID
      Serializable version identifier.
      See Also:

    • LOAD_FACTOR

      private static final float LOAD_FACTOR
      Load factor for the map.
      See Also:

    • 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:

    • 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:

    • PERTURB_SHIFT

      private static final int PERTURB_SHIFT
      Number of bits to perturb the index when probing for collision resolution.
      See Also:

    • 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 Details

    • 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 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

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