Implement the dictionary ADT of Section 4.4 by means of a hash table with linear probing as the collision resolution policy. You might wish to begin with the code of Figure 9.7.

Using empirical simulation, determine the cost of insert and delete as α grows (i.e., reconstruct the dashed lines of Figure 9.8).

Then, repeat the experiment using quadratic probing and pseudorandom probing. What can you say about the relative performance of these three collision resolution policies?

Transcribed Image Text:

/** Dictionary implemented using hashing. */ class HashDictionary