DataStructures
Class QuadraticProbingTable

java.lang.Object
  |
  +--DataStructures.ProbingHashTable
        |
        +--DataStructures.QuadraticProbingTable

All Implemented Interfaces:

LookupTable

public class QuadraticProbingTable

extends ProbingHashTable

A probing hash table implementation of a LookupTable with collisions resolved by quadratic probing.

Tables may be constructed as follows:

      LookupTable t = new QuadraticProbingTable();
      t.add("one", new Integer(1));
      t.add("two", new Integer(2));
      t.add("three", new Integer(3));
 

To retrieve a number use:

      try {
        Integer n = (Integer) t.lookup("two");
        System.out.println(n);
      } catch (NoSuchElementException e) {
        System.err.println(e);
      }
 

Keys in a table can be iterated over as follows:

   for (Iterator i = t.keys(); i.hasNext();) {
       System.out.println(i.next());
   }
 

The iterator returns a ProbingHashTable.Entry

Author:

Peter Williams

See Also:

LookupTable, ProbingHashTable

Inner classes inherited from class DataStructures.ProbingHashTable

ProbingHashTable.Entry

Inner classes inherited from class DataStructures.LookupTable

LookupTable.Entry

Fields inherited from class DataStructures.ProbingHashTable

table

Constructor Summary

QuadraticProbingTable()
Constructs the hash table with default capacity and load factor.

QuadraticProbingTable(int capacity)
Constructs the hash table with given capacity and default load factor.

QuadraticProbingTable(int capacity, double loadFactor)
Constructs the hash table with given initial capacity and load factor.

Method Summary

protected int

findIndex(java.lang.Object key) Method returning the index in ProbingHashTable.table of a key, if present, or the index at which to insert it, if absent.

Methods inherited from class DataStructures.ProbingHashTable

add, contains, isEmpty, iterator, lookup, remove, size

Methods inherited from class java.lang.Object

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

Constructor Detail

QuadraticProbingTable

public QuadraticProbingTable(int capacity,
                             double loadFactor)

Constructs the hash table with given initial capacity and load factor. The load factor must lie between 0 and 0.5.

Parameters:

capacity - the initial capacity of the table

loadFactor - the maximum loading before the table must grow

Throws:

java.lang.IllegalArgumentException - if the given load factor is out of range

QuadraticProbingTable

public QuadraticProbingTable(int capacity)

Constructs the hash table with given capacity and default load factor.

Parameters:

capacity - the initial capacity of the table

QuadraticProbingTable

public QuadraticProbingTable()

Constructs the hash table with default capacity and load factor.

Method Detail

findIndex

protected final int findIndex(java.lang.Object key)

Method returning the index in ProbingHashTable.table of a key, if present, or the index at which to insert it, if absent. Uses a version of double hashing.

Overrides:

findIndex in class ProbingHashTable

Parameters:

key - the key to search for

Returns:

the position where the search terminates