quamj.qps.rm
Class RRHashtable

java.lang.Object
  |
  +--quamj.qps.rm.RRHashtable

public class RRHashtable

extends java.lang.Object

Hashtable using part of the n_s_id of the ResourceReservation as keys, with no extra objects created. This uses the standard hash technique of adding a standard 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 a 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.

Field Summary

protected static double	DEFAULT_FILL Default fill fraction allowed before growing table.
protected int	entryCount Number of entries present in table.
protected int	entryLimit Entries allowed before growing table.
protected double	fillFraction Fill fraction allowed for this hash table.
protected ResourceReservation[]	hashTable Array of table slots.
protected int	hitOffset Offset added (modulo table size) to slot number on collision.
protected static int	KEY_MULTIPLIER Hash value multiplier to scramble bits before calculating slot.
protected static int	MINIMUM_SIZE Minimum size used for hash table.

Constructor Summary

RRHashtable()
Default constructor.

RRHashtable(int count)
Constructor with only size supplied.

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

RRHashtable(ResourceReservation[] from)

Method Summary

protected int	assignSlot(ResourceReservation entry) Find slot number for entry.
void	clear() Remove all entries from the table.
protected void	expandTable() Expand the table.
ResourceReservation	get(N_S_ID_TYPE key) Find an entry in the table.
void	put(ResourceReservation entry) Add an entry to the table.
void	remove(N_S_ID_TYPE key) Remove an entry from the table.
int	size() Get number of items in table.
ResourceReservation[]	toArray() Construct an array containing all elements of the table.

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.

See Also:

Constant Field Values

MINIMUM_SIZE

protected static final int MINIMUM_SIZE

Minimum size used for hash table.

See Also:

Constant Field Values

KEY_MULTIPLIER

protected static final int KEY_MULTIPLIER

Hash value multiplier to scramble bits before calculating slot.

See Also:

Constant Field Values

fillFraction

protected double fillFraction

Fill fraction allowed for this hash table.

entryCount

protected int entryCount

Number of entries present in table.

entryLimit

protected int entryLimit

Entries allowed before growing table.

hitOffset

protected int hitOffset

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

hashTable

protected ResourceReservation[] hashTable

Array of table slots.

Constructor Detail

RRHashtable

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

RRHashtable

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

RRHashtable

public RRHashtable()

Default constructor.

RRHashtable

public RRHashtable(ResourceReservation[] from)

Method Detail

size

public int size()

Get number of items in table.

Returns:

item count present

assignSlot

protected int assignSlot(ResourceReservation entry)

Find slot number for entry. Starts at the slot found by 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 or the same key is found leading to overwritting of this element

Parameters:

entry - entry to be added to table

Returns:

slot at which entry was added

expandTable

protected void expandTable()

Expand the table. Increases the table size to twice the previous size plus one, reinserting each entry from the smaller table into the new one.

put

public void put(ResourceReservation entry)

Add an entry to the table. Note that multiple entries with the same key are not kept, instead are overwritten

Parameters:

entry - entry to be added to table

get

public ResourceReservation get(N_S_ID_TYPE key)

Find an entry in the table.

Parameters:

key - for entry to be returned

Returns:

entry for key, or null if none

remove

public void remove(N_S_ID_TYPE key)

Remove an entry from the table.

Parameters:

key - for entry to be removed

clear

public void clear()

Remove all entries from the table. keep all other parameters as they are

toArray

public ResourceReservation[] toArray()

Construct an array containing all elements of the table. note that if there are no elements, array[0] is returned.

Returns:

the array of the appropriate type