com.mhhe.clrs2e
Class ChainedHashTable

java.lang.Object
  |
  +--com.mhhe.clrs2e.ChainedHashTable

All Implemented Interfaces:

Dictionary

public class ChainedHashTable

extends java.lang.Object

implements Dictionary

Implements a hash table with chaining, as described on page 226 of Introduction to Algorithms, Second edition. Elements inserted must implement the Comparable interface. Hash keys are based on the Java hashCode method applied to objects and then run through the multiplication method on pages 231-232.

Field Summary

private com.mhhe.clrs2e.MultiplicationMethod	hasher The class for the hash function used.
private com.mhhe.clrs2e.SentinelDLLDictionary[]	table The hash table is an array of linked lists.

Constructor Summary

ChainedHashTable()
Creates a new chained hash table with 16 entries.

ChainedHashTable(int m)
Creates a new chained hash table of a given size.

Method Summary

void	delete(java.lang.Object handle) Removes an element from a chained hash table.
private void	initChainedHashTable(int m) Initializes a chained hash table of a given size.
java.lang.Object	insert(java.lang.Comparable o) Inserts an element into a chained hash table.
java.lang.Object	search(java.lang.Comparable k) Searches a chained hash table for an element with a given key.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

table

private com.mhhe.clrs2e.SentinelDLLDictionary[] table

The hash table is an array of linked lists. They are doubly linked in order to make deletion fast.

hasher

private com.mhhe.clrs2e.MultiplicationMethod hasher

The class for the hash function used.

Constructor Detail

ChainedHashTable

public ChainedHashTable()

Creates a new chained hash table with 16 entries.

ChainedHashTable

public ChainedHashTable(int m)

Creates a new chained hash table of a given size.

Parameters:

m - The size of the chained hash table.

Method Detail

initChainedHashTable

private void initChainedHashTable(int m)

Initializes a chained hash table of a given size.

Parameters:

m - The size of the chained hash table.

insert

public java.lang.Object insert(java.lang.Comparable o)

Inserts an element into a chained hash table.

Specified by:

insert in interface Dictionary

Parameters:

o - The element to insert.

Returns:

A handle to the inserted element.

delete

public void delete(java.lang.Object handle)

Removes an element from a chained hash table.

Specified by:

delete in interface Dictionary

Parameters:

handle - A handle to the element to remove.

search

public java.lang.Object search(java.lang.Comparable k)

Searches a chained hash table 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.