com.mhhe.clrs2e
Class QuadraticProbingHashTable

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

All Implemented Interfaces:

Dictionary

public class QuadraticProbingHashTable

extends OpenAddressingHashTable

Implements a hash table with quadratic probing as described on pages 239-240 of Introduction to Algorithms, Second edition.

Field Summary

private double	c1 Constant used for quadratic probing.
private double	c2 Constant used for quadratic probing.

Fields inherited from class com.mhhe.clrs2e.OpenAddressingHashTable

m

Constructor Summary

QuadraticProbingHashTable()
Creates a new open-addressed hash table with quadratic probing with 16 entries.

QuadraticProbingHashTable(int size, double c1, double c2)
Creates a new open-addressed hash table with quadratic probing of a given size.

Method Summary

protected int

hash(java.lang.Object o, int i) Computes a hash function for an open-addressing hash table, uslng quadratic probing.

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

c1

private double c1

Constant used for quadratic probing.

c2

private double c2

Constant used for quadratic probing.

Constructor Detail

QuadraticProbingHashTable

public QuadraticProbingHashTable()

Creates a new open-addressed hash table with quadratic probing with 16 entries. The constants are set to c1 = 0.5 and c2 = 0.5.

QuadraticProbingHashTable

public QuadraticProbingHashTable(int size,
                                 double c1,
                                 double c2)

Creates a new open-addressed hash table with quadratic probing of a given size.

Parameters:

c1 - One of the constants used for probing.

c2 - The other constant used for probing.

Method Detail

hash

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

Computes a hash function for an open-addressing hash table, uslng quadratic probing.

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.