Your goal is experiment with different implementations of hashtables. The starting code is here.
Implement three open addressing hash table classes. Note that most of the
code in the three tables is the same. The only difference is the collision
resolution mechanism. Therefore it makes sense to implement most of the
functionality in an abstract class that provides code for all methods except
getNextIndex method that provides the next index given
the key and the probe number. The getNextIndex
method should be declared
abstract and overwritten in the subclasses.
Also note that when putting an object into a hashtable, you need to call
its hashCode method (see
Object
API), and then apply your hashing method to it.
The class structure should be as follows:
OurHashtable<K,V> interface (given)OpenAddressHashtable<K,V> that
provides
the array of elements and implements all of the methods of the interface.
The table size is N = 101 (a prime number). The table must be implemented
as an array (not an array list since the array size is known and fixed)
of pairs KVPair<K,V>. The unfilled slots must be null. It helps
to recall that arrays
of objects are initialized to all nulls.
The class declares an abstract protected method
abstract protected int getNextIndex(K key, int probeNumber);
OpenAddressHashtable<K,V> class. If the spot is
occupied (i.e. if a collision occurs), the method will be called
again, with the next probe number, until a free spot is found.
If the method is called N times
and doesn't find an empty location in the table, throw
a HashTableFullException (write a class for it and make
it extend RuntimeException).
LinearProbingHashtable<K,V> that extends
OpenAddressHashtable<K,V> and resolves collisions according
to the linear probing (with c = 1): h(k,i) = (h(k) + i) % N,
where h(k) is the hashcode
of the key, i is the probe number, and N is the table size.
QuadraticProbingHashtable<K,V> that extends
OpenAddressHashtable<K,V> and resolves collisions according
to the quadratic probing (with c1 = c2 = 1): h(k,i) = (h(k) + i + i*i) % N,
where h(k) is the hashcode
of the key, i is the probe number, and N is the table size.DoubleHashingHashtable<K,V> that extends
OpenAddressHashtable<K,V> and resolves collisions according
to the double-hashing formula: h(k,i) = (h(k) + i * g(k)) % N,
where h(k) is the hashcode
of the key, g(k) = h(k) % 7 + 1 (1 is added to guarantee that it's never 0),
i is the probe number, and N is the table size.Test your classes well. You might want to write a method that returns the contents of the array (as an array or array list). Note that some elements are null and should be printed in the output since they indicate an empty slot.
The easiest way to test hash tables is by using Integer for
both the key and the value.
You need to compare the number of collisions when putting randomly
generated keys (and the corresponding values) into the three hash
tables. In order to measure collisions you need to add a counter
to each class
that counts the number of times the
method getNextIndex is called in that class. At the end
the counters are printed and compared.
Specifically you need to do the following:
getCollisionCounter method
that returns the counter.getNextIndex to
increment the counter every time the method is called (i.e. every
time the collision occurs). Write a test to check that the counters
work as expected (you might want to write the test first, and then the
actual code that works with the variable).Submit your Java file(s) to me by e-mail. The subject must be Problem Set N, where N is the problem set number. If working in a group, CC your group partner.