In this exercise, you are going to implement a hash table from scratch. You must not use any of

the Java collection APIs.

In this implementation of hash table, you will create a hash table of key$-$value pairs where both key and value are String objects. The hash table will be implemented using a fixed capacity array and chaining $$ if multiple key values have the same hash function value, the key$-$value pairs are put into a linked list. The basic unit of storage is a Node, consisting of a key, a value, and a reference to the next node, the same as the node used in a raw implementation of a linked list.

Download the provided Java file. There is a menu$-$driven driver program class to test. Your job is to implement the missing methods to put $($key$,$ value$)$ pairs into the table as nodes, and perform various other operations on them.

public class Lab$2$CS$3\{$

public static void main$($String$[]$ args$)\{$

MyHashTable table $=$ new MyHashTable$(5)$;

String key,value;

while $($true$)\{$

System.out.println$("$

Menu:"$)$;

System.out.println$("0.$ Populate table"$)$;

System.out.println$("1.$ Test put$($key$,$value$)")$;

System.out.println$("2.$ Test get$($key$)")$;

System.out.println$("3.$ Test containsKey$($key$)")$;

System.out.println$("4.$ Test remove$($key$)")$;

System.out.println$("5.$ Show contents of hash table."$)$;

System.out.println$("6.$ EXIT"$)$;

System.out.print$("$Enter your command: $")$;

java.util.Scanner sc$=$new java.util.Scanner$($System$.$in$)$;

int item $=$ sc$.$nextInt$()$;

switch $($item$)\{$

case $0$:

table.put$("$jan$","1")$;

table.put$("$feb$","2")$;

table.put$("$mar$","3")$;

table.put$("$apr$","4")$;

table.put$("$may$","5")$;

table.put$("$jun$","6")$;

table.put$("$jul$","7")$;

table.put$("$aug$","8")$;

table.put$("$sep$","9")$;

table.put$("$oct$","10")$;

table.put$("$nov$","11")$;

table.put$("$dec$","12")$;

break;

case $1$:

sc$=$new java.util.Scanner$($System$.$in$)$;

System.out.print$("$Enter Key : $")$;

key $=$ sc$.$next$()$;

System.out.print$("$Enter Value: $")$;

value $=$ sc$.$next$()$;

table.put$($key$,$value$)$;

break;

case $2$:

sc$=$new java.util.Scanner$($System$.$in$)$;

System.out.print$("$Enter Key : $")$;

key $=$ sc$.$next$()$;

System.out.print$("$Value for this key is $"+$table.get$($key$))$;

break;

case $3$:

sc$=$new java.util.Scanner$($System$.$in$)$;

System.out.print$("$Enter Key: $")$;

key $=$ sc$.$next$()$;

System.out.println$("$

containsKey$("+$ key $+")$ is $"+$ table.containsKey$($key$))$;

break;

case $4$:

System.out.print$("$Enter Key to remove: $")$;

sc$=$new java.util.Scanner$($System$.$in$)$;

key $=$ sc$.$next$()$;

table.remove$($key$)$;

break;

case $5$:

table.show$()$;

break;

case $6$:

return;

default:

System.out.println$("$ Illegal command."$)$;

break;

$\}$

System.out.println$("$

Hash table size is $"+$ table.size$())$;

$\}$

$\}$

$\}$

class MyHashTable$\{$

private static class Node$\{$

String key;

String value;

Node next;

public Node$($String key, String value$)\{$

this.key$=$key; this.value$=$value; next$=$null;

$\}$

public String toString$()\{$

return $"("+$key$+","+$value$+")"$;

$\}$

$\}$

private Node$[]$ nodeArray; $//$fixed size Array to hold the head of linked lists

public int count$=0$; $//$total $($key$,$ value$)$ pairs in the entire hash table

public MyHashTable$()\{$

nodeArray $=$ new Node$[4]$; $//$a very small table

$\}$

public MyHashTable$($int initialSize$)\{$

if $($initialSize $<=0)$

throw new IllegalArgumentException$("$Illegal table size"$)$;

nodeArray$=$ new Node$[$initialSize$]$;

$\}$

public void put$($String key,String value$)\{$

$//$Change this $-$Your Code here $-$

return;

$\}$

public int hash$($String key$)\{$

return key.hashCode$()\%$nodeArray.length;

$\}$

public String get$($String key$)\{$

$//$Change this $-$ YOur Code

return $""$;

$\}$

public void show$()\{$

$//$Change this $-$ Your Code

$\}$

public boolean containsKey$($String key$)\{$

$//$Your Code $-$ change this

return false;

$\}$

public void remove$($String key$)\{$

$//$Change this $-$ Your Code

return;

$\}$

public int size$()\{$

return count;

$\}$

$\}$