DataStructures
Class DoubleHashingTable

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

All Implemented Interfaces:

LookupTable

public class DoubleHashingTable

extends ProbingHashTable

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

Tables may be constructed as follows:

      LookupTable t = new DoubleHashingTable();
      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 = 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

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

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

DoubleHashingTable(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

DoubleHashingTable

public DoubleHashingTable(int capacity,
                          double loadFactor)

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

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

DoubleHashingTable

public DoubleHashingTable(int capacity)

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

Parameters:

capacity - the initial capacity of the table

DoubleHashingTable

public DoubleHashingTable()

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