Package org.apache.commons.math3.util

Class OpenIntToDoubleHashMap

java.lang.Object
org.apache.commons.math3.util.OpenIntToDoubleHashMap
All Implemented Interfaces:
Serializable
public class OpenIntToDoubleHashMap extends Object implements 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
See Also:

  • 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 final int
    DEFAULT_EXPECTED_SIZE
    Default starting size.
    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 double
    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 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 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

    Modifier and Type
    Method
    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(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 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:

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

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