cpsc331.collections

Class OpenHashFunctionDouble<E>

java.lang.Object

cpsc331.collections.OpenHashFunctionDouble<E>

All Implemented Interfaces:

OpenHashFunction<E>

public class OpenHashFunctionDouble<E>
extends java.lang.Object
implements OpenHashFunction<E>

Provides an implementation of an OpenHashFunction — that is, a class providing a hash function for a has table with open addressing — using double hashing, and by using Java’s hashCode function to provide the first has function needed, along with the use of this function together with a randomly generated constant to provide the second

This implementation is designed to guarantee termination of algorithms when the table size is a sufficiently large power of two. It is not correct because it may cause an IndexOutOfBoundException if the table size is odd instead of even.

Constructor Summary

Constructors

Constructor and Description
OpenHashFunctionDouble(int tableSize) Provides a hash function for hash table with open addressing, for a given table size.

Method Summary

Modifier and Type	Method and Description
int	hashValue(E e, int i) Reports the hash value for a given value and probe index

Methods inherited from class java.lang.Object

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

Constructor Detail

OpenHashFunctionDouble

public OpenHashFunctionDouble(int tableSize)
                       throws java.lang.IllegalArgumentException

Provides a hash function for hash table with open addressing, for a given table size.

Parameters:

tableSize - the size of the hash table being supported

Throws:

java.lang.IllegalArgumentException - if the input table size is not psitive

Precondition: An integer T is given as input.
Postcondition: It T is positive then an OpehHashFunction that can be used with a hash table of size T is created. An IllegalArgumentException is thrown otherwise.

Method Detail

hashValue

public int hashValue(E e,
                     int i)

Description copied from interface: OpenHashFunction

Reports the hash value for a given value and probe index

Specified by:

hashValue in interface OpenHashFunction<E>

Parameters:

e - the element whose has value is to be provided

i - the index of probe for which a has value is being returned

Returns:

the hash value for this element

Precondition: An element e of type E and an integer i, between one and the size of the hash table being supported, have been given as input.
Postcondition: The hash value for e and i — an integer between zero and one less than the size of the hash table being supported — has been returned as output.