Package cern.colt.map

Class QuickOpenIntIntHashMap

java.lang.Object

cern.colt.PersistentObject

cern.colt.map.AbstractMap

cern.colt.map.AbstractIntIntMap

cern.colt.map.OpenIntIntHashMap

cern.colt.map.QuickOpenIntIntHashMap

All Implemented Interfaces:

Serializable, Cloneable

public class QuickOpenIntIntHashMap
extends OpenIntIntHashMap

Status: Experimental; Do not use for production yet. Hash map holding (key,value) associations of type (int-->int); Automatically grows and shrinks as needed; Implemented using open addressing with double hashing. First see the package summary and javadoc tree view to get the broad picture. Implements open addressing with double hashing, using "Brent's variation". Brent's variation slows insertions a bit down (not much) but reduces probes (collisions) for successful searches, in particular for large load factors. (It does not improve unsuccessful searches.) See D. Knuth, Searching and Sorting, 3rd ed., p.533-545

Version:

1.0, 09/24/99

Author:

wolfgang.hoschek@cern.ch

See Also:

HashMap, Serialized Form

Field Summary

Fields

Modifier and Type	Field	Description
int	totalProbesSaved

Fields inherited from class cern.colt.map.OpenIntIntHashMap

FREE, freeEntries, FULL, REMOVED, state, table, values

Fields inherited from class cern.colt.map.AbstractMap

defaultCapacity, defaultMaxLoadFactor, defaultMinLoadFactor, distinct, highWaterMark, lowWaterMark, maxLoadFactor, minLoadFactor

Constructor Summary

Constructors

Constructor	Description
QuickOpenIntIntHashMap()	Constructs an empty map with default capacity and default load factors.
QuickOpenIntIntHashMap(int initialCapacity)	Constructs an empty map with the specified initial capacity and default load factors.
QuickOpenIntIntHashMap(int initialCapacity, double minLoadFactor, double maxLoadFactor)	Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.

Method Summary

Modifier and Type	Method	Description
boolean	put(int key, int value)	Associates the given key with the given value.
protected void	rehash(int newCapacity)	Rehashes the contents of the receiver into a new table with a smaller or larger capacity.

Methods inherited from class cern.colt.map.OpenIntIntHashMap

clear, clone, containsKey, containsValue, ensureCapacity, forEachKey, forEachPair, get, indexOfInsertion, indexOfKey, indexOfValue, keyOf, keys, pairsMatching, removeKey, setUp, trimToSize, values

Methods inherited from class cern.colt.map.AbstractIntIntMap

copy, equals, keys, keysSortedByValue, pairsSortedByKey, pairsSortedByValue, toString, toStringByValue, values

Methods inherited from class cern.colt.map.AbstractMap

chooseGrowCapacity, chooseHighWaterMark, chooseLowWaterMark, chooseMeanCapacity, chooseShrinkCapacity, isEmpty, nextPrime, size

Methods inherited from class java.lang.Object

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

Field Detail

totalProbesSaved

public int totalProbesSaved

Constructor Detail

QuickOpenIntIntHashMap

public QuickOpenIntIntHashMap()

Constructs an empty map with default capacity and default load factors.

QuickOpenIntIntHashMap

public QuickOpenIntIntHashMap(int initialCapacity)

Constructs an empty map with the specified initial capacity and default load factors.

Parameters:

initialCapacity - the initial capacity of the map.

Throws:

IllegalArgumentException - if the initial capacity is less than zero.

QuickOpenIntIntHashMap

public QuickOpenIntIntHashMap(int initialCapacity,
                              double minLoadFactor,
                              double maxLoadFactor)

Constructs an empty map with the specified initial capacity and the specified minimum and maximum load factor.

Parameters:

initialCapacity - the initial capacity.

minLoadFactor - the minimum load factor.

maxLoadFactor - the maximum load factor.

Throws:

IllegalArgumentException - if initialCapacity < 0 || (minLoadFactor < 0.0 || minLoadFactor >= 1.0) || (maxLoadFactor <= 0.0 || maxLoadFactor >= 1.0) || (minLoadFactor >= maxLoadFactor) .

Method Detail

put

public boolean put(int key,
                   int value)

Associates the given key with the given value. Replaces any old (key,someOtherValue) association, if existing.

Overrides:

put in class OpenIntIntHashMap

Parameters:

key - the key the value shall be associated with.

value - the value to be associated.

Returns:

true if the receiver did not already contain such a key; false if the receiver did already contain such a key - the new value has now replaced the formerly associated value.

rehash

protected void rehash(int newCapacity)

Rehashes the contents of the receiver into a new table with a smaller or larger capacity. This method is called automatically when the number of keys in the receiver exceeds the high water mark or falls below the low water mark.

Overrides:

rehash in class OpenIntIntHashMap