com.mhhe.clrs2e
Class OpenAddressingHashTable

java.lang.Object
  |
  +--com.mhhe.clrs2e.OpenAddressingHashTable
All Implemented Interfaces:
Dictionary
Direct Known Subclasses:
DoubleHashingHashTable, LinearProbingHashTable, QuadraticProbingHashTable

public abstract class OpenAddressingHashTable
extends java.lang.Object
implements Dictionary

Abstract base class for hash tables that use open addressing, as described on pages 237-241 of Introduction to Algorithms, Second edition. Handles returned by the insert and search methods are simply indices into the hash table.


Field Summary
private  java.lang.String DELETED
          Indicator that a slot used to hold an object but that object has been deleted from the hash table.
protected  int m
          How many slots are in the hash table.
private  java.lang.Comparable[] table
          The hash table.
 
Constructor Summary
OpenAddressingHashTable()
          Creates a new open-addressed hash table with 16 entries.
OpenAddressingHashTable(int m)
          Creates a new open-addressed hash table of a given size.
 
Method Summary
 void delete(java.lang.Object handle)
          Removes an element.
protected abstract  int hash(java.lang.Object o, int i)
          Computes a hash function for an open-addressing hash table, dependent on an object and a probe number.
private  void initOpenAddressingHashTable(int m)
          Initializes an open-addressed hash table of a given size.
 java.lang.Object insert(java.lang.Comparable o)
          Inserts an element that implements Comparable.
 java.lang.Object search(java.lang.Comparable k)
          Searches for an element with a given key.
 java.lang.String toString()
          Returns the String representation of this hash table, with one entry per line.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

DELETED

private final java.lang.String DELETED
Indicator that a slot used to hold an object but that object has been deleted from the hash table.


table

private java.lang.Comparable[] table
The hash table.


m

protected int m
How many slots are in the hash table.

Constructor Detail

OpenAddressingHashTable

public OpenAddressingHashTable()
Creates a new open-addressed hash table with 16 entries.


OpenAddressingHashTable

public OpenAddressingHashTable(int m)
Creates a new open-addressed hash table of a given size.

Parameters:
m - The size of the open-addressed hash table.
Method Detail

initOpenAddressingHashTable

private void initOpenAddressingHashTable(int m)
Initializes an open-addressed hash table of a given size.

Parameters:
m - The size of the open-addressed hash table.

hash

protected abstract int hash(java.lang.Object o,
                            int i)
Computes a hash function for an open-addressing hash table, dependent on an object and a probe number. This method is defined by subclasses to implement different forms of open addressing.

The probe sequence must be a permutation of <0, 1, 2, ..., m-1>, so that every slot in the hash table is probed once in the first m probes.

Parameters:
o - The object. If the object implements DynamicSetElement, the hash value is of its key.
i - The probe number.
Returns:
An index into the open-addressed hash table.

insert

public java.lang.Object insert(java.lang.Comparable o)
Inserts an element that implements Comparable.

Specified by:
insert in interface Dictionary
Parameters:
o - The element to insert.
Returns:
A handle to the inserted element. The handle is the index in the hash table at which the element was inserted.
Throws:
HashTableOverflow - if the hash table is full.

delete

public void delete(java.lang.Object handle)
Removes an element.

Specified by:
delete in interface Dictionary
Parameters:
handle - A handle to the element to remove. The handle is just the index of the element to remove.
Throws:
java.lang.ClassCastException - if handle does not reference an Integer.
java.lang.ArrayIndexOutOfBoundsException - if the integer value of handle is not in the range 0 to m-1.

search

public java.lang.Object search(java.lang.Comparable k)
Searches for an element with a given key.

Specified by:
search in interface Dictionary
Parameters:
k - The key being searched for.
Returns:
A handle to the object found, or null if there is no match.

toString

public java.lang.String toString()
Returns the String representation of this hash table, with one entry per line.

Overrides:
toString in class java.lang.Object