DataStructures
Class ProbingHashTable<K,V>

java.lang.Object
  DataStructures.ProbingHashTable<K,V>

Type Parameters:

K - the type of objects serving as keys

V - the type of objects serving as values

All Implemented Interfaces:

LookupTable<K,V>, java.lang.Iterable<LookupTable.Entry<K,V>>

Direct Known Subclasses:

DoubleHashingTable, QuadraticProbingTable

public abstract class ProbingHashTable<K,V>
extends java.lang.Object
implements LookupTable<K,V>

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

This class must be extended to implement a particular probing algorithm.

Author:

Peter Williams

See Also:

DoubleHashingTable, QuadraticProbingTable

Method Summary

void	add(K key, V value) Adds the specified entry to the table.
boolean	contains(K key) Returns true if the table contains an entry for this key.
boolean	isEmpty() Tests if the table is empty.
java.util.Iterator<LookupTable.Entry<K,V>>	iterator() Returns an iteration over the entries in this lookup table.
V	lookup(K key) Returns the value associated with the specified key.
void	remove(K 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

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

Method Detail

isEmpty

public final boolean isEmpty()

Description copied from interface: LookupTable

Tests if the table is empty.

Specified by:

isEmpty in interface LookupTable<K,V>

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<K,V>

Returns:

the number of entries.

contains

public final boolean contains(K key)

Description copied from interface: LookupTable

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

Specified by:

contains in interface LookupTable<K,V>

Parameters:

key - the key to be searched for

Returns:

true if the table contains an entry for this key

add

public final void add(K key,
                      V 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<K,V>

Parameters:

key - the key of the entry

value - the value of the entry

remove

public final void remove(K 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<K,V>

Parameters:

key - the key of the entry to be removed

lookup

public final V lookup(K key)

Description copied from interface: LookupTable

Returns the value associated with the specified key.

Specified by:

lookup in interface LookupTable<K,V>

Parameters:

key - the key to be searched for

Returns:

the value for the key

iterator

public java.util.Iterator<LookupTable.Entry<K,V>> iterator()

Description copied from interface: LookupTable

Returns an iteration over the entries in this lookup table. The next method of the iterator returns a (key, value) pair in the form of a LookupTable.Entry<K,V>

Specified by:

iterator in interface LookupTable<K,V>

Specified by:

iterator in interface java.lang.Iterable<LookupTable.Entry<K,V>>

Returns:

an iteration over the entries in this lookup table

See Also:

LookupTable.Entry