com.sosnoski.util
Class PrimitiveHashBase

java.lang.Object
  |
  +--com.sosnoski.util.PrimitiveHashBase

Direct Known Subclasses:

PrimitiveKeyBase, PrimitiveSetBase

public abstract class PrimitiveHashBase

extends java.lang.Object

Base class for type-specific hash map and hash set classes using keys of primitive types. This base class implementation is based on a design using parallel arrays for "slot in use" flags and the actual key values, with type-specific subclasses implementing the key value hashing and comparisons. Subclasses may use additional parallel arrays beyond these two, and the internal operation is designed to allow for this case.

Hash classes based on this class are unsynchronized in order to provide the best possible performance for typical usage scenarios, so explicit synchronization must be implemented by the subclass or the application in cases where they are to be modified in a multithreaded environment.

This implementation uses the standard naive hash technique of adding a fixed offset to the computed position in the table when a collision occurs, so that several checks may potentially be necessary in order to determine if a particular key value is present in the table (since if the slot calculated by the hash function is occupied by a different entry it's still necessary to check the offset slot for a match, and then the offset slot from that, until an empty slot is found).

Each time the number of entries present in the table grows above the specified fraction full the table is expanded to twice its prior size plus one (to ensure the size is always an odd number). The collision offset is set to half the table size rounded down, ensuring that it will cycle through all slots of the table before returning to the original slot.

Subclasses need to implement the abstract methods defined by this class for working with the key array, as well as the actual data access methods.

Version:

1.0

Author:

Dennis M. Sosnoski

See Also:

ObjectHashBase

Field Summary

protected static double	DEFAULT_FILL Default fill fraction allowed before growing table.
protected static int	KEY_MULTIPLIER Hash value multiplier to scramble bits before calculating slot.
protected int	m_entryCount Number of entries present in table.
protected int	m_entryLimit Entries allowed before growing table.
protected double	m_fillFraction Fill fraction allowed for table.
protected boolean[]	m_flagTable Array of slot occupied flags.
protected int	m_hitOffset Offset added (modulo table size) to slot number on collision.
protected static int	MINIMUM_SIZE Minimum size used for table.

Constructor Summary

PrimitiveHashBase(int count, double fill, java.lang.Class ktype)
Constructor with full specification.

PrimitiveHashBase(PrimitiveHashBase base)
Copy (clone) constructor.

Method Summary

void	clear() Set the table to the empty state.
void	ensureCapacity(int min) Ensure that the table has the capacity for at least the specified number of keys.
protected int	freeSlot(int slot) Find free slot number for entry.
protected abstract java.lang.Object	getKeyArray() Get the backing array of keys.
protected void	growCapacity(int min) Increase table capacity.
protected abstract void	reallocate(int size) Resize the base arrays after a size change.
protected abstract void	setKeyArray(java.lang.Object array) Set the backing array of keys.
int	size() Get number of items in table.
protected int	stepSlot(int slot) Step the slot number for an entry.

Methods inherited from class java.lang.Object

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

Field Detail

DEFAULT_FILL

protected static final double DEFAULT_FILL

Default fill fraction allowed before growing table.

MINIMUM_SIZE

protected static final int MINIMUM_SIZE

Minimum size used for table.

KEY_MULTIPLIER

protected static final int KEY_MULTIPLIER

Hash value multiplier to scramble bits before calculating slot.

m_fillFraction

protected double m_fillFraction

Fill fraction allowed for table.

m_entryCount

protected int m_entryCount

Number of entries present in table.

m_entryLimit

protected int m_entryLimit

Entries allowed before growing table.

m_hitOffset

protected int m_hitOffset

Offset added (modulo table size) to slot number on collision.

m_flagTable

protected boolean[] m_flagTable

Array of slot occupied flags.

Constructor Detail

PrimitiveHashBase

public PrimitiveHashBase(int count,
                         double fill,
                         java.lang.Class ktype)

Constructor with full specification.

Parameters:

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

fill - fraction full allowed for table before growing

ktype - type of primitives used for keys

PrimitiveHashBase

public PrimitiveHashBase(PrimitiveHashBase base)

Copy (clone) constructor.

Parameters:

base - instance being copied

Method Detail

size

public final int size()

Get number of items in table.

Returns:

item count present

getKeyArray

protected abstract java.lang.Object getKeyArray()

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

Returns:

backing key array object

setKeyArray

protected abstract void setKeyArray(java.lang.Object array)

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

Parameters:

array - backing key array object

reallocate

protected abstract void reallocate(int size)

Resize the base arrays after a size change. This is a separate abstract method so that derived classes can implement the handling appropriate for their data structures (which may include more than just the arrays of flags and key values).

Parameters:

size - new size for base arrays

growCapacity

protected void growCapacity(int min)

Increase table capacity. This method is called when we actually need to increase the table size.

Parameters:

min - minimum new table capacity

ensureCapacity

public final void ensureCapacity(int min)

Ensure that the table has the capacity for at least the specified number of keys.

Parameters:

min - minimum capacity to be guaranteed

clear

public void clear()

Set the table to the empty state. This method may need to be overridden in cases where other information associated with the keys also needs to be cleared.

stepSlot

protected final int stepSlot(int slot)

Step the slot number for an entry. Adds the collision offset (modulo the table size) to the slot number.

Parameters:

slot - slot number to be stepped

Returns:

stepped slot number

freeSlot

protected final int freeSlot(int slot)

Find free slot number for entry. Starts at the slot based directly on the hashed key value. If this slot is already occupied, it adds the collision offset (modulo the table size) to the slot number and checks that slot, repeating until an unused slot is found.

Parameters:

slot - initial slot computed from key

Returns:

slot at which entry was added