## CSci 2101 Problem set 6: hash tables

### Due Friday, May 5 at 11:59pm (by e-mail)

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)

• abstract class `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);
``````
The method will be called in the `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).

• class `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.

• class `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.

• class `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:

• Add a collision counter (a private variable) in each of the three hash tables classes. Add a `getCollisionCounter` method that returns the counter.
• Add a line of code in `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).
• Write a simulation class (with main) that generates M random pairs of keys and values (both Integer) such that the key is in the range from 0 to 10000 (where M <= N). After a pair is generated, it is added to each of the three tables.
• After all the elements have been added, print out (and record) the values of collision counters.
• If one of the tables does not allow you to add an element, record that information. Your program should stop at that point.
• Run these tests with the following load factors M/N: 50%, 75%, 90%, 100%. Write down your results and observations about the tables' behavior.

#### How to submit

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.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.