com.carrotsearch.hppc
Class DoubleDoubleOpenHashMap

java.lang.Object
  com.carrotsearch.hppc.DoubleDoubleOpenHashMap

All Implemented Interfaces:

DoubleDoubleAssociativeContainer, DoubleDoubleMap, java.lang.Cloneable, java.lang.Iterable<DoubleDoubleCursor>

@Generated(date="2011-07-12T16:58:51+0200",
           value="HPPC generated from: DoubleDoubleOpenHashMap.java")
public class DoubleDoubleOpenHashMap
extends java.lang.Object
implements DoubleDoubleMap, java.lang.Cloneable

A hash map of double to double, implemented using open addressing with linear probing for collision resolution.

The internal buffers of this implementation (keys, values, allocated) are always allocated to the nearest size that is a power of two. When the capacity exceeds the given load factor, the buffer size is doubled.

See ObjectObjectOpenHashMap class for API similarities and differences against Java Collections.

Important node. The implementation uses power-of-two tables and linear probing, which may cause poor performance (many collisions) if hash values are not properly distributed. This implementation uses rehashing using MurmurHash3.

Author:

This code is inspired by the collaboration and implementation in the fastutil project.

Nested Class Summary

class

DoubleDoubleOpenHashMap.KeysContainer A view of the keys inside this hash map.

Field Summary

boolean[]	allocated Information if an entry (slot) in the values table is allocated or empty.
int	assigned Cached number of assigned slots in allocated.
static int	DEFAULT_CAPACITY Default capacity.
static float	DEFAULT_LOAD_FACTOR Default load factor.
double[]	keys Hash-indexed array holding all keys.
float	loadFactor The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).
static int	MIN_CAPACITY Minimum capacity for the map.
double[]	values Hash-indexed array holding all values associated to the keys stored in keys.

Constructor Summary

DoubleDoubleOpenHashMap()
Creates a hash map with the default capacity of 16, load factor of 0.75f.

DoubleDoubleOpenHashMap(DoubleDoubleAssociativeContainer container)
Create a hash map from all key-value pairs of another container.

DoubleDoubleOpenHashMap(int initialCapacity)
Creates a hash map with the given initial capacity, default load factor of 0.75f.

DoubleDoubleOpenHashMap(int initialCapacity, float loadFactor)
Creates a hash map with the given initial capacity, load factor.

Method Summary

void	clear() Clear all keys and values in the container.
DoubleDoubleOpenHashMap	clone()
boolean	containsKey(double key) Returns true if this container has an association to a value for the given key.
boolean	equals(java.lang.Object obj) Compares the specified object with this set for equality.
<T extends DoubleDoubleProcedure> T	forEach(T procedure) Applies a given procedure to all keys-value pairs in this container.
static DoubleDoubleOpenHashMap	from(double[] keys, double[] values) Creates a hash map from two index-aligned arrays of key-value pairs.
static DoubleDoubleOpenHashMap	from(DoubleDoubleAssociativeContainer container) Create a hash map from another associative container.
double	get(double key)
int	hashCode()
boolean	isEmpty()
java.util.Iterator<DoubleDoubleCursor>	iterator() Returns a cursor over the entries (key-value pairs) in this map.
DoubleDoubleOpenHashMap.KeysContainer	keys() Returns a specialized view of the keys of this associated container.
double	lget() Returns the last value saved in a call to containsKey(double).
double	lset(double key) Sets the value corresponding to the key saved in the last call to containsKey(double), if and only if the key exists in the map already.
static DoubleDoubleOpenHashMap	newInstance() Create a new hash map without providing the full generic signature (constructor shortcut).
static DoubleDoubleOpenHashMap	newInstance(int initialCapacity, float loadFactor) Create a new hash map without providing the full generic signature (constructor shortcut).
protected int	nextCapacity(int current) Return the next possible capacity, counting from the current buffers' size.
double	put(double key, double value) Place a given key and value in the container.
int	putAll(DoubleDoubleAssociativeContainer container) Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.
int	putAll(java.lang.Iterable<? extends DoubleDoubleCursor> iterable) Puts all key/value pairs from a given iterable into this map.
boolean	putIfAbsent(double key, double value) Trove-inspired API method.
double	putOrAdd(double key, double putValue, double additionValue) Trove-inspired API method.
double	remove(double key) Remove all values at the given key.
int	removeAll(DoubleContainer container) Removes all keys (and associated values) present in a given container.
int	removeAll(DoublePredicate predicate) Removes all keys (and associated values) for which the predicate returns true.
protected int	roundCapacity(int requestedCapacity) Round the capacity to the next allowed value.
protected void	shiftConflictingKeys(int slotCurr) Shift all the slot-conflicting keys allocated to (and including) slot.
int	size()
java.lang.String	toString() Convert the contents of this map to a human-friendly string.
DoubleContainer	values() Returns a container view of all values present in this container.

Methods inherited from class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Field Detail

DEFAULT_CAPACITY

public static final int DEFAULT_CAPACITY

Default capacity.

See Also:

Constant Field Values

MIN_CAPACITY

public static final int MIN_CAPACITY

Minimum capacity for the map.

See Also:

Constant Field Values

DEFAULT_LOAD_FACTOR

public static final float DEFAULT_LOAD_FACTOR

Default load factor.

See Also:

Constant Field Values

keys

public double[] keys

Hash-indexed array holding all keys.

See Also:

values

values

public double[] values

Hash-indexed array holding all values associated to the keys stored in keys.

See Also:

keys

allocated

public boolean[] allocated

Information if an entry (slot) in the values table is allocated or empty.

See Also:

assigned

assigned

public int assigned

Cached number of assigned slots in allocated.

loadFactor

public final float loadFactor

The load factor for this map (fraction of allocated slots before the buffers must be rehashed or reallocated).

Constructor Detail

DoubleDoubleOpenHashMap

public DoubleDoubleOpenHashMap()

Creates a hash map with the default capacity of 16, load factor of 0.75f.

See class notes about hash distribution importance.

DoubleDoubleOpenHashMap

public DoubleDoubleOpenHashMap(int initialCapacity)

Creates a hash map with the given initial capacity, default load factor of 0.75f.

See class notes about hash distribution importance.

Parameters:

initialCapacity - Initial capacity (greater than zero and automatically rounded to the next power of two).

DoubleDoubleOpenHashMap

public DoubleDoubleOpenHashMap(int initialCapacity,
                               float loadFactor)

Creates a hash map with the given initial capacity, load factor.

See class notes about hash distribution importance.

Parameters:

initialCapacity - Initial capacity (greater than zero and automatically rounded to the next power of two).

loadFactor - The load factor (greater than zero and smaller than 1).

DoubleDoubleOpenHashMap

public DoubleDoubleOpenHashMap(DoubleDoubleAssociativeContainer container)

Create a hash map from all key-value pairs of another container.

Method Detail

put

public double put(double key,
                  double value)

Place a given key and value in the container.

Specified by:

put in interface DoubleDoubleMap

Returns:

The value previously stored under the given key in the map is returned.

putAll

public final int putAll(DoubleDoubleAssociativeContainer container)

Puts all keys from another container to this map, replacing the values of existing keys, if such keys are present.

Specified by:

putAll in interface DoubleDoubleMap

Returns:

Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.

putAll

public final int putAll(java.lang.Iterable<? extends DoubleDoubleCursor> iterable)

Puts all key/value pairs from a given iterable into this map.

Specified by:

putAll in interface DoubleDoubleMap

Returns:

Returns the number of keys added to the map as a result of this call (not previously present in the map). Values of existing keys are overwritten.

putIfAbsent

public final boolean putIfAbsent(double key,
                                 double value)

Trove-inspired API method. An equivalent of the following code:

 if (!map.containsKey(key)) map.put(value);
 

Parameters:

key - The key of the value to check.

value - The value to put if key does not exist.

Returns:

true if key did not exist and value was placed in the map.

putOrAdd

public final double putOrAdd(double key,
                             double putValue,
                             double additionValue)

Trove-inspired API method. An equivalent of the following code:

 if (map.containsKey(key)) 
    map.lset(map.lget() + additionValue);
 else
    map.put(key, putValue);
 

Parameters:

key - The key of the value to adjust.

putValue - The value to put if key does not exist.

additionValue - The value to add to the existing value if key exists.

Returns:

Returns the current value associated with key (after changes).

remove

public double remove(double key)

Remove all values at the given key. The default value for the key type is returned if the value does not exist in the map.

Specified by:

remove in interface DoubleDoubleMap

shiftConflictingKeys

protected final void shiftConflictingKeys(int slotCurr)

Shift all the slot-conflicting keys allocated to (and including) slot.

removeAll

public final int removeAll(DoubleContainer container)

Removes all keys (and associated values) present in a given container. An alias to:

 keys().removeAll(container)
 

but with no additional overhead.

Specified by:

removeAll in interface DoubleDoubleAssociativeContainer

Returns:

Returns the number of elements actually removed as a result of this call.

removeAll

public final int removeAll(DoublePredicate predicate)

Removes all keys (and associated values) for which the predicate returns true. An alias to:

 keys().removeAll(container)
 

but with no additional overhead.

Specified by:

removeAll in interface DoubleDoubleAssociativeContainer

Returns:

Returns the number of elements actually removed as a result of this call.

get

public double get(double key)

Use the following snippet of code to check for key existence first and then retrieve the value if it exists.

 if (map.containsKey(key))
   value = map.lget(); 
 

Specified by:

get in interface DoubleDoubleMap

Returns:

Returns the value associated with the given key or the default value for the key type, if the key is not associated with any value. Important note: For primitive type values, the value returned for a non-existing key may not be the default value of the primitive type (it may be any value previously assigned to that slot).

lget

public double lget()

Returns the last value saved in a call to containsKey(double).

See Also:

containsKey(double)

lset

public double lset(double key)

Sets the value corresponding to the key saved in the last call to containsKey(double), if and only if the key exists in the map already.

Returns:

Returns the previous value stored under the given key.

See Also:

containsKey(double)

containsKey

public boolean containsKey(double key)

Returns true if this container has an association to a value for the given key.

Saves the associated value for fast access using lget() or lset(double).

 if (map.containsKey(key))
   value = map.lget();
 

or, for example to modify the value at the given key without looking up its slot twice:

 if (map.containsKey(key))
   map.lset(map.lget() + 1);
 

Specified by:

containsKey in interface DoubleDoubleAssociativeContainer

roundCapacity

protected int roundCapacity(int requestedCapacity)

Round the capacity to the next allowed value.

nextCapacity

protected int nextCapacity(int current)

Return the next possible capacity, counting from the current buffers' size.

clear

public void clear()

Clear all keys and values in the container.

Does not release internal buffers.

Specified by:

clear in interface DoubleDoubleAssociativeContainer

size

public int size()

Specified by:

size in interface DoubleDoubleAssociativeContainer

Returns:

Returns the current size (number of assigned keys) in the container.

isEmpty

public boolean isEmpty()

Note that an empty container may still contain many deleted keys (that occupy buffer space). Adding even a single element to such a container may cause rehashing.

Specified by:

isEmpty in interface DoubleDoubleAssociativeContainer

Returns:

Return true if this hash map contains no assigned keys.

hashCode

public int hashCode()

Specified by:

hashCode in interface DoubleDoubleMap

Overrides:

hashCode in class java.lang.Object

Returns:

A hash code of elements stored in the map. The hash code is defined as a sum of hash codes of keys and values stored within the set). Because sum is commutative, this ensures that different order of elements in a set does not affect the hash code.

equals

public boolean equals(java.lang.Object obj)

Compares the specified object with this set for equality. Returns true if and only if the specified object is also a DoubleDoubleMap and both objects contains exactly the same key-value pairs.

Specified by:

equals in interface DoubleDoubleMap

Overrides:

equals in class java.lang.Object

iterator

public java.util.Iterator<DoubleDoubleCursor> iterator()

Returns a cursor over the entries (key-value pairs) in this map. The iterator is implemented as a cursor and it returns the same cursor instance on every call to Iterator.next(). To read the current key and value use the cursor's public fields. An example is shown below.

 for (IntShortCursor c : intShortMap)
 {
     System.out.println("index=" + c.index 
       + " key=" + c.key
       + " value=" + c.value);
 }
 

The index field inside the cursor gives the internal index inside the container's implementation. The interpretation of this index depends on to the container.

Specified by:

iterator in interface DoubleDoubleAssociativeContainer

Specified by:

iterator in interface java.lang.Iterable<DoubleDoubleCursor>

forEach

public <T extends DoubleDoubleProcedure> T forEach(T procedure)

Applies a given procedure to all keys-value pairs in this container. Returns the argument (any subclass of DoubleDoubleProcedure. This lets the caller to call methods of the argument by chaining the call (even if the argument is an anonymous type) to retrieve computed values, for example.

Specified by:

forEach in interface DoubleDoubleAssociativeContainer

keys

public DoubleDoubleOpenHashMap.KeysContainer keys()

Returns a specialized view of the keys of this associated container. The view additionally implements ObjectLookupContainer.

Specified by:

keys in interface DoubleDoubleAssociativeContainer

values

public DoubleContainer values()

Description copied from interface: DoubleDoubleAssociativeContainer

Returns a container view of all values present in this container. The returned collection is a view over the key set and any modifications (if allowed) introduced to the collection will propagate to the associative container immediately.

Specified by:

values in interface DoubleDoubleAssociativeContainer

Returns:

Returns a container with all values stored in this map.

clone

public DoubleDoubleOpenHashMap clone()

Overrides:

clone in class java.lang.Object

toString

public java.lang.String toString()

Convert the contents of this map to a human-friendly string.

Overrides:

toString in class java.lang.Object

from

public static DoubleDoubleOpenHashMap from(double[] keys,
                                           double[] values)

Creates a hash map from two index-aligned arrays of key-value pairs.

from

public static DoubleDoubleOpenHashMap from(DoubleDoubleAssociativeContainer container)

Create a hash map from another associative container.

newInstance

public static DoubleDoubleOpenHashMap newInstance()

Create a new hash map without providing the full generic signature (constructor shortcut).

newInstance

public static DoubleDoubleOpenHashMap newInstance(int initialCapacity,
                                                  float loadFactor)

Create a new hash map without providing the full generic signature (constructor shortcut).