com.sosnoski.util.hashset
Class IntHashSet

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

public class IntHashSet

extends PrimitiveSetBase

Hash set using primitive int 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.

Version:

1.0

Author:

Dennis M. Sosnoski

Field Summary

protected int[]

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

IntHashSet()
Default constructor.

IntHashSet(int count)
Constructor with only size supplied.

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

IntHashSet(IntHashSet base)
Copy (clone) constructor.

Method Summary

boolean	add(int key) Add a key to the set.
protected int	assignSlot(int key) Assign slot for key.
java.lang.Object	clone() Construct a copy of the table.
protected int	computeSlot(int key) Compute the base slot for a key.
boolean	contains(int key) Check if a key is present in the table.
protected java.lang.Object	getKeyArray() Get the backing array of keys.
protected int	internalFind(int key) Internal find key in table.
protected boolean	reinsert(int slot) Reinsert a key into the hash map.
boolean	remove(int 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 int[] m_keyTable

Array of key table slots.

Constructor Detail

IntHashSet

public IntHashSet(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

IntHashSet

public IntHashSet(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

IntHashSet

public IntHashSet()

Default constructor.

IntHashSet

public IntHashSet(IntHashSet 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 map. 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 map

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(int key)

Compute the base slot for a key.

Parameters:

key - key value to be computed

Returns:

base slot for key

assignSlot

protected int assignSlot(int 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(int key)

Add a key to the set.

Parameters:

key - key to be added to set

Returns:

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

internalFind

protected final int internalFind(int 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(int key)

Check if a key is present in the table.

Parameters:

key - key to be found

Returns:

true if key found in table, false if not

remove

public boolean remove(int 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