In this assignment you will explore the mysteries of hashing. The following six hashing approaches:

1. linear probing
2. quadratic probing
3. chaining
4. double hashing
5. ordered table

will be used to investigate the average number of probes required for successful and unsuccessful searches.

Input:

For all cases use a hash table of size M = 997, a prime number. You need to assess the quality of each in success and in failure for different loads \lambda = L/M. In order to load a hash table with L values, you need 2*L distinct keys. Use the first L to load the hash table, use them again in a different random order to compute the average successful search cost, and finally use the other L(not in the table) to compute the average unsuccessful search cost. Use the random permutation generator you already have to generate these integer vectors of length 2*L (and to repermute the first L); input to the permutation algorithm should consist of 2*L distinct values, each much larger than M. You may use the files R-list1.bin, R-list2.bin, S-lista.bin and S-listd.bin.

Hashing

Two hashing functions will be examined. h1(K) = K MOD M The Double Hashing method in which h1 is as above, and h2(K) = max(1,K DIV M) MOD M)

Results:

All the combinations (successful and unsuccessful) require 6 sub-experiments in all. For each of the 12, report on table loads covering at least \lambda = 0.1, 0.5 and 0.95. Comment on the relation between your results and the theoretical and empirical formulas given in the text.
Discuss your results in a two-page report.

How To Submit

You have to upload your solution files duly zipped on 202.141.81.74 latest by due date and time,however assignments will also be checked by the TAs during lab hours.

Please follow the instructions for uploading, mentioned on the site, while you are uploading the files.