Problem $8$: Implementing a hash table using separate chaining

$35$ points; individual$-$only

In lecture, we discussed the following interface for a hash table ADT:

We also examined one implementation of this interface that uses open addressing $($the

OpenHashTable class that we've included in the ps$8$ folder$).$

In this problem, you will complete another implementation of this interface $-$ one that uses

separate chaining instead of open addressing. Its class will be called ChainedHashTable.

We have given you a skeleton for this class in the ps$8$ folder. It includes two private fields:

one called numKeys for the number of keys in the hash table

one called table that holds a reference to the array that you will use for the hash table.

However, rather than having each element of the array store a single entry as we do in

open addressing, each element of the array must serve as a bucket or chain of

entries.

We have given you a private inner class called Node for the nodes in each chain. Each

element of the table array must hold a reference to the first node in its linked list of nodes,

and you will need to create and manipulate these nodes within your hash table methods.

Each Node object has fields that allow it to store:

a single key

the collection of values associated with that key, using an instance of our LLQueue class

a reference to the next node in the linked list $($if any$).$

We have also given you:

a copy the h$1()$ method from our OpenHashTable class, which you must use as the hash

function of your implementation $($Note: Because separate chaining allows all entries

whose keys are hashed to a given position in the table to stay in that position, you will

not need to perform any probing. As a result, you won't need the second hash function

h$2()$ from OpenHashTable.$)$

a toString$()$ method that will allow you to see the current contents of the table. It

returns a string of the form

table$[0],$ table$[1],...,$ table$[$size $-1]]$

where each position of the table is represented by either:

the key or keys in that position's chain of entries, separated by semi$-$colons and

surrounded by curly braces.