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.

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

o 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