Implement Hasing (in Java) with Linear Probing and Quadratic Probing with Load Factors of 60% and 80%

Use a Hash Table of size 1019 indexed from 0..1018.

To fill the Hash Table 60% full, generate 611 different random keys in the range l"10,000 That is, you are to generate 611 random values (unique) from the range 1.. 10,000 and insert the key the Hash Table using the hash function and the probe sequence. s into To fill the Hash Table 80% full, generate 815 different random keys in the range l .. 10,000 That is, you are to generate 815 random values (unique) from the range 1. 10,000 and insert the keys into the Hash Table using the hash function and the probe sequence. Note, as you enter a value into the Hash Table you must make sure the value is not already in the Table. o, omit that value and try another one until the proper number of values are placed into the Table. RUN FOUR SEPARATE HASH PROGRAMS AS FOLLOWS: ) Generate a hash table 60% full using Linear probing (b) Generate a hash table 80% full using Linear probing ) Generate a hash table 60 % full using Quadratic probing (d) Generate a hash table 80 % full using Quadratic probing n each of the four cases above, do the following: 1. Construct the Hash Table. 2. Then for each Key 1 to 10,000, search the Hash Table and record how many probes were needed to locate the Key or how many probes were needed to determine the Key was not present. For example, with a 60% load factor you will have statistics for 611 successful searches and 9,389 unsuccessful searches 3. In each of the 4 cases above, determine the average number of probes required for a successful search and the average number of probes required for an unsuccessful search. 4. Print your results in a clear readable format. If I have trouble finding and/or reading your results you will not receive full credit for the program 5. All output values should be type double, not integer, since the fractional part is necessary Note: in all cases, use the "Division Method" as the hash function: h(key) key % 1019 Note: When counting the number of required probes, h(key) is considered the first probe Turn in a copy of your program along with your output. I reserve the right to ask for an electronic version of your program, but for now it is not require For quadratic probing, use the technique I taught in class: h(k), (h(k)+P)%b | G