Programming Question

Your task for this question is to implement a hash table using an open addressing scheme.

This programming question is scaffolded. You are provided with $6$ files:

$$ HashTable.java $-$ This class is mostly empty. You are responsible for filling in the insert,

search and delete functions. The constructor which takes in a ProbeSequence which

dictates what hash function is used, and the probe sequence for this hash function.

$$ Record.java $-$ This class is the type of object that is stored in the hash table. This class

should be extended in order to store other data in the hash table.

$$ Student.java $-$ This class extends the Record class.

$$ ProbeSequence.java $-$ contains a function int probe$($int i$,$ int key, int m$).$

Any class that implements this interface must provide such a function which given a key,

an index in the probe sequence and a table size m$,$ returns the hash table index to probe.

$$ MyLinearProbeSequence.java $-$ This implements the ProbeSequence interface and

provides a probe sequence using the multiplication method for the hash function and

linear probing for the probe sequence.

$$ HashTableTest.java $-$ This class shows how to use and test the HashTable class.

Begin by implementing the insert and search functions. The hash table should use a dynamic array such that when an element is inserted and the hash table is already full, the array size is doubled.

Keep in mind that these functions must support arbitrary hash functions and probe

sequences. However, if the probe sequence does not cover all entries in the table, the behaviour is undefined $($i$.$e$.$ don't worry about it$).$

Note: Assume throughout this question that duplicate keys are not allowed