$1.$ Implement Hash$\_$table$1$ and Hash$\_$table$2$ in files Hash$\_$table$1.$h$/$cpp and Hash$\_$table$2.$h$/$cpp respectively.

Implement two hash table classes, Hash$\_$table$1$ and Hash$\_$table$2,$ which use open addressing for collision resolution. The two hash table classes are very similar. The requirements for the two hash table classes are given as follows:

$1.$ Both hash table classes take strings as their keys$/$elements$.$ The maximum width of the strings$/$keys is $6.$

$2.$ Both hash tables use the same hash function, which first calculates the product p of all the characters of the key and then returns the index where index$=$p$\%$hash$\_$size. The pseudo code of the hash function is given as the follows.

int hash$($const string &key$)\{$

long long t$\_$prod $=1$;

for $($int position $=0$; position $$ max$\_$key$\_$length; position$++)$

t$\_$prod $*=$ key$[$position$]$;

int value $=$ t$\_$prod $\%$ hash$\_$size;

return value;

$\}$

Note: key$[$position$]$ in the hash function refers to digits in the key as characters, not numbers. For example, $\text{'}0\text{'}$ is a char, not $0.$ Its value is the ASCII code of $\text{'}0\text{'},$ which is $48.$

$3.$ In both hash table classes, you need to implement:

a$.$ The hash function.

b$.$ A constructor that takes an integer parameter specifying the hash table size $($hash$\_$size$).$

c$.$ The retrieve$()$ method that takes a string key as the input and returns the location $($index$)$ of the key in the hash table. If the hash table does not have the key, retrieve$()$ returns $-1.$

d$.$ The insert$()$ method, which takes a string key as the input and inserts it into the hash table. If the key already exists in the table or if the table is full, the insertion operation will not be completed and $-1$ is returned. If the key is inserted, the location $($index$)$ of the key in the hash table is returned.

e$.$ Class Hash$\_$table$1$ should use linear probing for collision resolution.

f$.$ Class Hash$\_$table$2$ should use quadratic probing for collision resolution. clock$\_$t start, finish;string input $=""$;Ordered$\_$list if$($input $=="1")\{$getline$($cin$,$ input$)$;insertion$\_$file.open$($input$.$c$\_$str$())$; ol$.$clear$()$; while$($getline$($insertion$\_$file, input$))\{$ ol$.$insert$($cnt$,$ input$)$; ht$2.$insert$($input$)$; ht$4.$insert$($input$)$; $//$cout $$ input $$ endl; if$($cnt$\%10000==0)\}$ cout $$ "Invalid file name." $$ endl;

$\}$

else if$($input $=="2")\{$cout $$ "Enter a string for search:" $$ endl;int search$\_$key$\_$int$\_$val $=$ stoi$($input$)$;if $($search$\_$key$\_$int$\_$val use REPEAT$\_$FACTOR finish $=$ clock$()$;if $($code $==$ success$)$elsecout $$ endl $$ "Time: $"$ elapsed$\_$time seconds; REPEAT$\_$FACTOR used" $$ endl $$ endl;else $\{//$ do not use REPEAT$\_$FACTOR code $=$ sequential$\_$search