com.sosnoski.util.hashset
Class DoubleHashSet

java.lang.Object
  |
  +--com.sosnoski.util.PrimitiveHashBase
        |
        +--com.sosnoski.util.hashset.PrimitiveSetBase
              |
              +--com.sosnoski.util.hashset.DoubleHashSet

public class DoubleHashSet

extends PrimitiveSetBase

Hash set using primitive double values. This implementation is unsynchronized in order to provide the best possible performance for typical usage scenarios, so explicit synchronization must be implemented by a wrapper class or directly by the application in cases where instances are modified in a multithreaded environment. See the base classes for other details of the hash set implementation.

Note that the hashing function implemented in this class has not been tested extensively and may be unsuitable for use with some patterns of data values. To change the hashing function, modify the computeSlot() method.

Version:

1.0

Author:

Dennis M. Sosnoski

Field Summary

protected double[]

m_keyTable Array of key table slots.

Fields inherited from class com.sosnoski.util.PrimitiveHashBase

DEFAULT_FILL, KEY_MULTIPLIER, m_entryCount, m_entryLimit, m_fillFraction, m_flagTable, m_hitOffset, MINIMUM_SIZE

Constructor Summary

DoubleHashSet()
Default constructor.

DoubleHashSet(DoubleHashSet base)
Copy (clone) constructor.

DoubleHashSet(int count)
Constructor with only size supplied.

DoubleHashSet(int count, double fill)
Constructor with full specification.

Method Summary

boolean	add(double key) Add a key to the table.
protected int	assignSlot(double key) Assign slot for key.
java.lang.Object	clone() Construct a copy of the table.
protected int	computeSlot(double key) Compute the base slot for a key.
boolean	contains(double key) Check if a key is present in the set.
protected java.lang.Object	getKeyArray() Get the backing array of keys.
protected int	internalFind(double key) Internal find key in table.
protected boolean	reinsert(int slot) Reinsert a key into the hash set.
boolean	remove(double key) Remove a key from the table.
protected void	restructure(boolean[] flags, java.lang.Object karray) Restructure the table.
protected void	setKeyArray(java.lang.Object array) Set the backing array of keys.

Methods inherited from class com.sosnoski.util.hashset.PrimitiveSetBase

reallocate

Methods inherited from class com.sosnoski.util.PrimitiveHashBase

clear, ensureCapacity, freeSlot, growCapacity, size, stepSlot

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

m_keyTable

protected double[] m_keyTable

Array of key table slots.

Constructor Detail

DoubleHashSet

public DoubleHashSet(int count,
                     double fill)

Constructor with full specification.

Parameters:

count - number of values to assume in initial sizing of table

fill - fraction full allowed for table before growing

DoubleHashSet

public DoubleHashSet(int count)

Constructor with only size supplied. Uses default value for fill fraction.

Parameters:

count - number of values to assume in initial sizing of table

DoubleHashSet

public DoubleHashSet()

Default constructor.

DoubleHashSet

public DoubleHashSet(DoubleHashSet base)

Copy (clone) constructor.

Parameters:

base - instance being copied

Method Detail

getKeyArray

protected java.lang.Object getKeyArray()

Get the backing array of keys. This implementation of an abstract method is used by the type-agnostic base class code to access the array used for type-specific storage by the child class.

Overrides:

getKeyArray in class PrimitiveHashBase

Returns:

backing key array object

setKeyArray

protected void setKeyArray(java.lang.Object array)

Set the backing array of keys. This implementation of an abstract method is used by the type-agnostic base class code to set the array used for type-specific storage by the child class.

Overrides:

setKeyArray in class PrimitiveHashBase

Parameters:

array - backing key array object

reinsert

protected final boolean reinsert(int slot)

Reinsert a key into the hash set. This method is designed for internal use when the table is being modified, and does not adjust the count present or check the table capacity.

Parameters:

slot - position of key to be reinserted into hash set

Returns:

true if the slot number used by the key has has changed, false if not

restructure

protected void restructure(boolean[] flags,
                           java.lang.Object karray)

Restructure the table. This implementation of an abstract method is used when the table is increasing or decreasing in size, and works directly with the old table representation arrays. It inserts keys from the old array directly into the table without adjusting the count present or checking the table size.

Overrides:

restructure in class PrimitiveSetBase

Parameters:

flags - array of flags for array slots used

karray - array of keys

computeSlot

protected final int computeSlot(double key)

Compute the base slot for a key.

Parameters:

key - key value to be computed

Returns:

base slot for key

assignSlot

protected int assignSlot(double key)

Assign slot for key. Starts at the slot found by the hashed key value. If this slot is already occupied, it steps the slot number and checks the resulting slot, repeating until an unused slot is found. This method does not check for duplicate keys, so it should only be used for internal reordering of the tables.

Parameters:

key - key to be added to table

Returns:

slot at which key was added

add

public boolean add(double key)

Add a key to the table.

Parameters:

key - key to be added to table

Returns:

true if key added to set, false if already present in set

internalFind

protected final int internalFind(double key)

Internal find key in table.

Parameters:

key - to be found in table

Returns:

index of matching key, or -index-1 of slot to be used for inserting key in table if not already present (always negative)

contains

public boolean contains(double key)

Check if a key is present in the set.

Parameters:

key - key to be found

Returns:

true if key found in table, false if not

remove

public boolean remove(double key)

Remove a key from the table.

Parameters:

key - key to be removed from table

Returns:

true if key successfully removed from set, false if key not found in set

clone

public java.lang.Object clone()

Construct a copy of the table.

Overrides:

clone in class java.lang.Object

Returns:

copy of table