CS 112 A1 - Fall 2004: Homework 6

Due Monday, December 13, 11:59 P.M. NOTE: Monday, December 13 is the last day in which homework will be accepted for credit.

Reading: Chapter 9, pages 397-418.

PROBLEM 1 (70 points):

The files you must submit for this homework are exactly: h6main.cpp, h6hash.h, h6hash.cpp, and h6.script.

In the Kruse and Ryba book on page 414-415 are tables that compare (theoretically) the performance of some hashing methods using open addressing, and separate chaining.

You are to write a program that experimentally tests this theory for two of these hashing methods, open addressing with linear probing and quadratic probing. That is, you are to write a program which implements these two hashing methods and which counts the average number of probes they use on hash tables with different load factors.

You will experiment with these hashing methods on a hash table of size 1009. You should implement the hash function below to hash into your table:

h(K) = take the last 3 digits of K, square the three digits and then take the remainder after dividing by 1009. So for example, if K=12345, then H(K) = ((345)^2)%1009

You should also use two collision resolution strategies. Each is given by a probe increment p(K). The first, a linear probe, uses p(K) = 1. The second, quadratic probing method, uses p(K) = 1,3,5,7,.... (That is, the you look in the hash table at position h(K)+(t*t) when you probe for the t^{th} time. )

The keys (K's) should be numbers between 0 and 100000. You should run your tests for each of two load factors, 50% and 80%. That means run tests where you hash 504 values and also where you hash 807 values into the table. Here are 2 files named keyfile1 and keyfile2 with these values in them. Then run a sequence of key searches on these tables, count the average number of probes these searches take, and report the results for each load factor, hashing method and probing method used.

When counting probes:

Each time a key is hashed (converted to an index in the table) and that location is checked, that counts as a probe. So each search for a key takes at least one probe.
Obviously, if the key is not in the location that it hashes to, one of the probing techniques must be used, which will make the number of probes for that key > 1.

We will provide the two sets of values to searched for. They are in files searchfile1 and searchfile2.

Your implementations are expected to show what you have learned about data structures. In particular, you should implement a hash table as a data structure. The operations on the table should include creating a table, storing a key, and finding a key. For this problem, the data in the hash will just be the keys.

Finally, you should write one main program (h6main.cpp), which inserts all the values, and performs all the searches. This main program should contain definitions for the hash function and 2 probe inceement functions that are to be used. The program should produce a table, something like on page 414-415 of the text, for the results of the 4 runs (2 load factors x 2 probe decrements). For each test run you should give the number of keys searched for, the number of keys that you searched for and found, the total number of probes done in the search, and the average number of probes per search.

After you have run your program, write a short paragraph explaining your results. That is, either that the experiment verified the theory in the cases you tried, or that it didn't and give possible reasons why it didn't.

In the script you submit (h6.script), display all source code (with cat), show a compilation, a run of your program AND display the paragraph explanation you wrote (in that order).