The code should follow the instructions and output exactly. I will leave feedback. Thanks. The goal of this assignment is to work with hash functions and understand the performance of the Division hashing method using open addressing techniques discussed in the slides.

Implement all required functions and the main function in one file, named hashFunctions.java.

Write one simple program $($in file hashFunctions.java$)$ that uses a fixed set of $50$ unique keys stored inan array as follows $($lmportant; hard$-$code the array content in your test program and make sure you have same exact key values below in the exact given order$)$:

$```$

int$[]$ keys $=\{1234,8234,7867,1009,5438,4312,3420,9487,5418,5299,$

$5078,8239,1208,5098,5195,5329,4543,3344,7698,5412,$

$5567,5672,7934,1254,6091,8732,3095,1975,3843,5589,$

$5439,8907,4097,3096,4310,5298,9156,3895,6673,7871,$

$5787,9289,4553,7822,8755,3398,6774,8289,7665,5523\}$;

$```$

Design and integrate the following menu to allow the user to select a hash function to be invoked on the set of keys given above. Keep the menu simple and exactly as shown below:

$```$

MAIN MENU

$1-$ Run HF$1($Division method with Linear Probing$)$

$2-$ Run HF$2($Division method with Quadratic Probing$)$

$3-$ Run HF$3($Division method with Double Hashing$)$

$4-$ Run HF$4($Student Designed HF$)$

$5-$ Exit Program

Enter option number:

$```$

Always re$-$display the menu after an option $($other than option $4)$ is fully exercised. Printout blank lines before and after the menu to make it easy to look at the output.

The output of an option is a display of the hash table as illustrated below $($see sample runs$).$

The hash functions are defined below.

To keep the implementation simple and uniform across all submissions, define the hash table $($call it

Table$)($of size $50$ entries$)$ as a $2$D array $(50$ rows and $2$ columns$)($int$[][]$ Table $=$ new

int $[50][2]$ The first column stores the keys while the second column stores number of probes used

to resolve collision if a collided key.

After calling the hash function from the menu, the output of the program should display the hash table

followed by the sum of all probe values in the table. Declare a separate function in your class, say

sumProbes $(),$ to perform this calculation and return the sum of all probes in the table $($second column

of the table$).$

Note that the total number of probes a hashing function generates indicates the performance level of

the function $-$ The smaller the sum of probes the better the hash function.

HF$1(10$ points$)$:

Declare a separate function HF$1(...)$ that implements the Division method discussed in the slides with

Linear Probing for collision resolution.

For validation, the correct implementation gives total of $214\_$ probes for the given set of keys with all

keys allocated in the table. No un$-$hashed keys.

HE$2(10$ points$)$:

Declare a separate function HF$2(...)$ that implements the Division method discussed in the slides with

Quadratic Probing for collision resolution.

For validation, the correct implementation gives total of $112$ probes for the given set of keys with all

keys allocated in the table. No un$-$hashed keys.

HF$3(15$ points$)$:

Declare a separate function HF$3(...)$ that implements the Division method discussed in the slides with

Double Hashing for collision resolution. For the second hashing function, use the following function

and increment $($see example in the slides$)$:

$\{$:$[$H$2"($key$)="30"-$ key $\backslash \%25$; $"],["$ Increment is $($key $\backslash \%50)+"$j$"*$ H$2($key$)$ for $"$j$=1","2","3","4",$"dots$]$:$\}$

Note: It is possible that HF$3$ will not be able to find an empty index$/$location in the hash table for a give

key, especially when very few empty entries remain in the hash table. In this case and to avoid

entering into an infinite loop, limit number of attempts to locate a key in the hash table to no more than

$50$ tries. After $50$ tries, printout a message like this example: "Unable to hash key $43654$ to

the table". Note that this phenomenon happens due to not applying Load Factoring to our table.

For validation, the correct implementation gives total of $103$ probes for the given set of keys with no

more than $2$ keys "unable to store in the table".

HF$4(65$ points$)$:

Declare a separate method HF$4()$ that implements a hash function of your own design. The sky is

your limit$.$ You can come up with your own hash function or take and improve one of the above three

functions by either using a different hashing method $($other than Division method$)$ or a different

collision resolution method. Aim to come up with a function that beats the above three function $($i$.$e$.,$

your function generates smallest number of probes for the given set of keys$).$

Note: See the note in HF$3$ and apply it to your HF$4$ if necessary.

The performance of HF$4$ depends on the hashing method and the collision resolution technique you

implement. However, aim to get a low total number of probes. In some implementation $($like mid$-$

square method$)$ you may get under $60$ probes total.

In your code, please add a block of comments explaining your implementation of HF$4.$