All Packages Class Hierarchy This Package Previous Next Index
Class DataStructures.ProbingHashTable
java.lang.Object

+DataStructures.ProbingHashTable
 public abstract class ProbingHashTable
 extends Object
 implements HashTable
Probing table implementation of hash tables.
This is an abstract class that must be extended to
implement a particular probing algorithm, such as
quadratic probing.
Note that all "matching" is based on the equals method.

array
 The array of elements.

ProbingHashTable()
 Construct the hash table.

find(Hashable)
 Find an item in the hash table.

findPos(Hashable)
 Abstract method that performs collision resolution.

hash(String, int)
 A hash routine for String objects.

insert(Hashable)
 Insert into the hash table.

makeEmpty()
 Make the hash table logically empty.

remove(Hashable)
 Remove from the hash table.
array
protected HashEntry[] array
 The array of elements.
ProbingHashTable
public ProbingHashTable()
 Construct the hash table.
findPos
protected abstract int findPos(Hashable x)
 Abstract method that performs collision resolution.
Each class must override this method only.
 Parameters:
 x  the item to search for.
 Returns:
 the position where the search terminates.
insert
public final void insert(Hashable x)
 Insert into the hash table. If the item is
already present, then replace it with the new item.
 Parameters:
 x  the item to insert.
remove
public final void remove(Hashable x) throws ItemNotFound
 Remove from the hash table.
 Parameters:
 x  the item to remove.
 Throws:
ItemNotFound
 if no item
that matches x can be found in the hash table.
find
public final Hashable find(Hashable x) throws ItemNotFound
 Find an item in the hash table.
 Parameters:
 x  the item to search for.
 Returns:
 the matching item.
 Throws:
ItemNotFound
 if no item
that matches x can be found in the hash table.
makeEmpty
public final void makeEmpty()
 Make the hash table logically empty.
hash
public static final int hash(String key,
int tableSize)
 A hash routine for String objects.
 Parameters:
 key  the String to hash.
 tableSize  the size of the hash table.
 Returns:
 the hash value.
All Packages Class Hierarchy This Package Previous Next Index