Package org.apache.commons.math3.util

Class OpenIntToFieldHashMap<T extends FieldElement<T>>

  • Type Parameters:
    T - the type of the field elements
    All Implemented Interfaces:
    java.io.Serializable
    public class OpenIntToFieldHashMap<T extends FieldElement<T>>
extends java.lang.Object
implements java.io.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:
    Serialized Form

    • Field Summary

      Fields 
      Modifier and Type Field Description
      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.

    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      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.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​(java.io.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.

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

      • buildArray

        private T[] buildArray​(int length)
        Build an array of elements.
        Parameters:
        length - size of the array to build
        Returns:
        a new array