com.sosnoski.util
Class ObjectHashBase

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

Direct Known Subclasses:

ObjectKeyBase, ObjectSetBase

public abstract class ObjectHashBase

extends java.lang.Object

Base class for type-specific hash map and hash set classes using object keys. This class uses a single array for keys with null values in unused slots. Subclasses may use additional arrays in parallel to this key array, 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.1

Author:

Dennis M. Sosnoski

Field Summary

protected static double	DEFAULT_FILL Default fill fraction allowed before growing table.
static java.lang.String	IDENTITY_COMP Standard hash with object identity comparison technique specifier.
static java.lang.String	IDENTITY_HASH Identity hash with object identity comparison technique specifier.
protected int	m_arraySize Size of array used for keys.
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 this hash table.
protected int	m_hitOffset Offset added (modulo table size) to slot number on collision.
protected boolean	m_identCompare Use identity comparison flag.
protected boolean	m_identHash Use identity hash flag.
protected static int	MINIMUM_SIZE Minimum size used for hash table.
static java.lang.String	STANDARD_HASH Standard hashing technique specifier.

Constructor Summary

ObjectHashBase(int count, double fill, java.lang.Class type, java.lang.Object tech)
Constructor with full specification.

ObjectHashBase(ObjectHashBase 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 items.
protected int	freeSlot(int slot) Find free slot number for entry.
protected abstract java.lang.Object[]	getKeyArray() Get the backing array of items.
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 items.
int	size() Get number of items in table.
protected int	standardFind(java.lang.Object key) Standard find key in table.
protected int	standardSlot(java.lang.Object key) Standard base slot computation for a key.
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

STANDARD_HASH

public static final java.lang.String STANDARD_HASH

Standard hashing technique specifier.

IDENTITY_COMP

public static final java.lang.String IDENTITY_COMP

Standard hash with object identity comparison technique specifier.

IDENTITY_HASH

public static final java.lang.String IDENTITY_HASH

Identity hash with object identity comparison technique specifier.

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 hash table.

m_identHash

protected final boolean m_identHash

Use identity hash flag.

m_identCompare

protected final boolean m_identCompare

Use identity comparison flag.

m_fillFraction

protected final double m_fillFraction

Fill fraction allowed for this hash 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_arraySize

protected int m_arraySize

Size of array used for keys.

m_hitOffset

protected int m_hitOffset

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

Constructor Detail

ObjectHashBase

public ObjectHashBase(int count,
                      double fill,
                      java.lang.Class type,
                      java.lang.Object tech)

Constructor with full specification.

Parameters:

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

fill - fraction full allowed for table before growing

type - type of keys contained in table

tech - hash technique specifier (one of STANDARD_HASH, IDENTITY_COMP, or IDENTITY_HASH)

ObjectHashBase

public ObjectHashBase(ObjectHashBase 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 items. 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 item array object

setKeyArray

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

Set the backing array of items. 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 item 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 array of 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 items.

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

standardSlot

protected final int standardSlot(java.lang.Object key)

Standard base slot computation for a key. This method may be used directly for key lookup using either the hashCode() method defined for the key objects or the System.identityHashCode() method, as selected by the hash technique constructor parameter. To implement a hash class based on some other methods of hashing and/or equality testing, define a separate method in the subclass with a different name and use that method instead. This avoids the overhead caused by overrides of a very heavily used method.

Parameters:

key - key value to be computed

Returns:

base slot for key

standardFind

protected int standardFind(java.lang.Object key)

Standard find key in table. This method may be used directly for key lookup using either the hashCode() method defined for the key objects or the System.identityHashCode() method, and either the equals() method defined for the key objects or the == operator, as selected by the hash technique constructor parameter. To implement a hash class based on some other methods of hashing and/or equality testing, define a separate method in the subclass with a different name and use that method instead. This avoids the overhead caused by overrides of a very heavily used method.

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)