Class 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
    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.
      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.
    • Method Summary

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