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