com.mhhe.clrs2e
Class DoubleHashingHashTable

java.lang.Object
  |
  +--com.mhhe.clrs2e.OpenAddressingHashTable
        |
        +--com.mhhe.clrs2e.DoubleHashingHashTable

All Implemented Interfaces:

Dictionary

public class DoubleHashingHashTable

extends OpenAddressingHashTable

Implements a hash table with double hashing as described on pages 240-241 of Introduction to Algorithms, Second edition. The auxiliary hash function h2 always returns an odd value, which works well if the table size is a power of 2. Make a subclass of this class and override h2 to use a different auxiliary hash function.

Field Summary

protected com.mhhe.clrs2e.MultiplicationMethod

hasher The class for the auxiliary hash function h2.

Fields inherited from class com.mhhe.clrs2e.OpenAddressingHashTable

m

Constructor Summary

DoubleHashingHashTable()
Creates a new open-addressed hash table with double hashing with 16 entries.

DoubleHashingHashTable(int size)
Creates a new open-addressed hash table with double hashing of a given size.

Method Summary

protected int	h2(java.lang.Object o) An auxiliary hash function.
protected int	hash(java.lang.Object o, int i) Computes a hash function for an open-addressing hash table, uslng double hashing.

Methods inherited from class com.mhhe.clrs2e.OpenAddressingHashTable

delete, insert, search, toString

Methods inherited from class java.lang.Object

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

Field Detail

hasher

protected com.mhhe.clrs2e.MultiplicationMethod hasher

The class for the auxiliary hash function h2.

Constructor Detail

DoubleHashingHashTable

public DoubleHashingHashTable()

Creates a new open-addressed hash table with double hashing with 16 entries.

DoubleHashingHashTable

public DoubleHashingHashTable(int size)

Creates a new open-addressed hash table with double hashing of a given size.

Method Detail

h2

protected int h2(java.lang.Object o)

An auxiliary hash function. In this implementation, it returns an odd number, so that it is relatively prime to the size of the hash table, if the hash-table size is a power of 2. If the hash-table size is not a power of 2, override this implementation.

Parameters:

o - An object. If the object implements DynamicSetElement, the hash value is of its key.

Returns:

An integer, which is odd in this implementation. In any case, the value returned should be nonzero but need not be a valid index into the hash table.

hash

protected int hash(java.lang.Object o,
                   int i)

Computes a hash function for an open-addressing hash table, uslng double hashing.

Specified by:

hash in class OpenAddressingHashTable

Parameters:

o - An 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.