org.apache.commons.math.util
Class OpenIntToDoubleHashMap

java.lang.Object
  extended by org.apache.commons.math.util.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
Version:
$Revision: 746578 $ $Date: 2009-02-21 15:01:14 -0500 (Sat, 21 Feb 2009) $
See Also:
Serialized Form

Nested Class Summary
 class OpenIntToDoubleHashMap.Iterator
          Iterator class for the map.
 
Field Summary
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.
 
Constructor Summary
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
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

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

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

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


Copyright (c) 2003-2010 Apache Software Foundation