Objective:

The objective of this assignment is to implement linear and quadratic probing.

Problem Specification:

Please download the HashingSample before start. Perform simulations to compare the observed performance of hashing with the following theoretical result: In linear probing, for a hashtable with final load factor $,$ the expected number of probes in a successful search is

$\frac{1}{2}\{1+\frac{1}{1-}\}$

and in quadratic probing is

$\frac{1}{}log(\frac{1}{1-})$

Declare a probing hash table whose size is a prime just greater than $\frac{10000}{},$ where $$ 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 key