Programming Project 6

Due : Wed, April 8    CSCI 271                               Spring 2009

Problem:

Study the effects of different hash table sizes on the search time.  The study will consist of creating a hash class (with a hash table, an insert function and a search function (feel free to add more main and class functions that you find necessary and/or helpful).   The size of the hash table must be easily modified.  All functions that are based on the table size must be aware of any changes to the table size.

Read 10,000 values from the file /home/win.thackerw/271/p4load.dat.  Then read values from /home/win.thackerw/271/p4search.dat and search for those values.  Use this process for table sizes of 20,000, 13,000, 11,000 and 10,500.  Time each of these runs.

Our project input:

The input will be character strings of length less than or equal to 30 characters.

Our project output:

Your program will print out the average number of probes, the number of searches that were successful and the number of searches that were unsuccessful.  A probe is when you look at a value in the array.

Additionally, you will record the times it takes for the programs to run for each of the table sizes.  You get the time by using the time function in Unix.  If your program is called p5, then instead of issuing the command p5 to run your program, you use time p5.  This will run your program and report system, cpu, and wallclock times.  The time of interest for us is cpu+system.

You should produce a table of the form:

The #Unsuccessful and #Successful columns should have the same value.  This is a check to see if your program works.

Project Options

You may use any hash function you can develop.  It should be "good".   You are to use linear probe for collision handling.  For extra credit, you may use separate chaining and report the timings for it in addition to reporting the timings for linear probe.