Please download the HashingSample before start. Perform simulations to compare thepp

observed performance of hashing with the following theoretical result: In linear probing, for

a hashtable with final load factor $\backslash$lambda $,$ the expected number of probes in a successful search is

$1$

$2$

n

$1+$

$1$

$1\backslash$lambda

o

$(1)$

and in quadratic probing is

$1$

$\backslash$lambda

log $1$

$1\backslash$lambda

$(2)$

Declare a probing hash table whose size is a prime just greater than $10000/\backslash$lambda $,$ where $\backslash$lambda is

the load factor, lying between $0\mathrm{.}1$ and $0\mathrm{.}9,$ obtained as input from the user. Thus the test for

a final load factor of $0\mathrm{.}4$ would declare a table of size approximately $25,000($adjusted to be a

prime just greater than this value$).$

Insert $10,000$ randomly generated integers into the table and count the average number

of probes used. This is the average cost of a successful search. Implement both linear and

quadratic probing $($prompt the user for the probe type$).$ Compare both linear and quadratic

probing with the theoretical results above.

Use h$($key$)=$ key mod n$,$ where n is the tablesize, as the hashing function.

Here is a sample execution of the program:

Enter load factor $($lambda$)$ between $0\mathrm{.}1$ and $0\mathrm{.}9$: $0\mathrm{.}4$

Enter probe type $(1$ for linear, $2$ for quadratic$)$: $1$

Actual $($average$)$ cost: $1\mathrm{.}3289$

Expected cost $($from the equation$)$: $1\mathrm{.}3333$

$=====================$

Enter load factor $($lambda$)$ between $0\mathrm{.}1$ and $0\mathrm{.}9$: $0\mathrm{.}4$

Enter probe type $(1$ for linear, $2$ for quadratic$)$: $2$

Actual $($average$)$ cost: $1\mathrm{.}3137$

Expected cost $($from the equation$)$: $1\mathrm{.}3333$

$================$