DataStructures
Class ProbingHashTable

java.lang.Object
  |
  +--DataStructures.ProbingHashTable

All Implemented Interfaces:

LookupTable

Direct Known Subclasses:

DoubleHashingTable, QuadraticProbingTable

public abstract class ProbingHashTable

extends java.lang.Object

implements LookupTable

An abstract class implementing the LookupTable interface by means of a hash table. Collisions are resolved by probing.

This class must be extended to implement a particular probing algorithm for the findIndex method, such as double hashing or quadratic probing.

Author:

Peter Williams

See Also:

findIndex(java.lang.Object), DoubleHashingTable, QuadraticProbingTable

Inner Class Summary

protected static class

ProbingHashTable.Entry A class of objects returned by iteration over entries.

Inner classes inherited from class DataStructures.LookupTable

LookupTable.Entry

Field Summary

protected ProbingHashTable.Entry[]

table the underlying table of hash entries

Method Summary

void	add(java.lang.Object key, java.lang.Object value) Adds the specified entry to the table.
boolean	contains(java.lang.Object key) Returns true if the table contains an entry for this key.
protected abstract int	findIndex(java.lang.Object key) Abstract method returning the index in the table of a key, if present, or the index at which to insert it, if absent.
boolean	isEmpty() Tests if the table is empty.
java.util.Iterator	iterator() Iterates over the table's entries.
java.lang.Object	lookup(java.lang.Object key) Returns the value associated with the specified key.
void	remove(java.lang.Object key) Removes the entry corresponding to the key.
int	size() Returns the number of entries in the table.

Methods inherited from class java.lang.Object

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

Field Detail

table

protected ProbingHashTable.Entry[] table

the underlying table of hash entries

Method Detail

findIndex

protected abstract int findIndex(java.lang.Object key)

Abstract method returning the index in the table of a key, if present, or the index at which to insert it, if absent.

Parameters:

key - the key to search for

Returns:

the position where the search terminates

isEmpty

public final boolean isEmpty()

Description copied from interface: LookupTable

Tests if the table is empty.

Specified by:

isEmpty in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Returns:

the status of the table

size

public final int size()

Description copied from interface: LookupTable

Returns the number of entries in the table.

Specified by:

size in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Returns:

the number of entries.

contains

public final boolean contains(java.lang.Object key)

Description copied from interface: LookupTable

Returns true if the table contains an entry for this key.

Specified by:

contains in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Parameters:

key - the key to be searched for

Returns:

true if the table contains an entry for this key

add

public final void add(java.lang.Object key,
                      java.lang.Object value)

Description copied from interface: LookupTable

Adds the specified entry to the table. If the key is already present, its value is overwritten.

Specified by:

add in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Parameters:

key - the key of the entry

value - the value of the entry

remove

public final void remove(java.lang.Object key)

Description copied from interface: LookupTable

Removes the entry corresponding to the key. Does nothing if the key is not present.

Specified by:

remove in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Parameters:

key - the key of the entry to be removed

lookup

public final java.lang.Object lookup(java.lang.Object key)

Description copied from interface: LookupTable

Returns the value associated with the specified key.

Specified by:

lookup in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Parameters:

key - the key to be searched for

Returns:

the value for the key

Throws:

NoSuchElementException - if key is not present

iterator

public java.util.Iterator iterator()

Description copied from interface: LookupTable

Iterates over the table's entries. The next method of the iterator returns a (key, value) pair in the form of a LookupTable.Entry

Specified by:

iterator in interface LookupTable

Following copied from interface: DataStructures.LookupTable

Returns:

the iterator

See Also:

LookupTable.Entry