All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class DataStructures.ProbingHashTable 

java.lang.Object
   |
   +----DataStructures.ProbingHashTable
public 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.

Variable Index

o array
The array of elements.

Constructor Index

o ProbingHashTable()
Construct the hash table.

Method Index

o find(Hashable)
Find an item in the tree.
o findPos(Hashable)
Abstract method that performs collision resolution.
o hash(String, int)
A hash routine for String objects.
o insert(Hashable)
Insert into the hash table.
o makeEmpty()
Make the hash table logically empty.
o remove(Hashable)
Remove from the hash table.

Variables

o array 
  protected HashEntry array[]
The array of elements.

Constructors

o ProbingHashTable 
  public ProbingHashTable()
Construct the hash table.

Methods

o 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.
o 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.
o 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.
o find 
  public final Hashable find(Hashable x) throws ItemNotFound
Find an item in the tree.

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.
o makeEmpty 
  public final void makeEmpty()
Make the hash table logically empty.

o hash 
  public final static 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