CSCI 203 Project #6

Hashing Experiments

Purpose: This project will give you experience implementing a hash table and a feel for its efficiency.

Description: You are to implement a hash table. You may use any hashing algorithm you wish, and you may size your table appropriately, as long as it has at least 128 locations in it. You should use linear open addressing to handle overflows, that is, use linear probing if something hashes to a cell that is already full. Your table should be initialized to contain –1’s to indicate that all the cells are empty. You are to generate as many random numbers (>=0) as there are places in your hash table, and insert them one at a time into the table. At regular intervals (at least eight times during the table filling process), you should print out the average number of cells checked when performing each insert for that last group of inserts, and also for all the previous inserts.

As we discussed in class, one option you might choose is to use a table size of 128 elements, and use the mid-squares hashing function, ((x*x)>>12)&0x7f. You could generate insertion averages every 16 insertions, and insert random numbers in the range 0 to 65535.

After you have filled the table, you are to look the numbers up one by one, starting with the first table entry and going to the last one. For each number, you should send it through the hash function and then look for it starting at that index, using linear probing. Again, you should keep a count of the number of lookups it took to find each element, and print averages at regular intervals (again, at least 8 times during the lookup process).

Turn-in: You should turn in a zipped file containing your source file(s), and the output generated by your program. As usual, include a README file that describes any special or unique features of your program, as well as instructions as to how to compile and run it.

Hints: This should be the easiest program yet, but don’t put it off til the last minute because it still is a fair amount of work! Also, this is the one that I most frequently get something other than what was asked for, so if you have any questions, ask!

Sample output:

Here is some sample output from a single run:

16 inserts took 17 probes for an average of 1.063 probes/number.

16 inserts took 18 probes for an average of 1.125 probes/number.

16 inserts took 22 probes for an average of 1.375 probes/number.

16 inserts took 34 probes for an average of 2.125 probes/number.

16 inserts took 36 probes for an average of 2.25 probes/number.

16 inserts took 85 probes for an average of 5.313 probes/number.

16 inserts took 386 probes for an average of 24.13 probes/number.

16 inserts took 934 probes for an average of 58.38 probes/number.

128 numbers took 1532 probes for an average of 11.97 probes/number.

16 lookups took 233 probes for an average of 14.56 probes/number.

16 lookups took 401 probes for an average of 25.06 probes/number.

16 lookups took 43 probes for an average of 2.688 probes/number.

16 lookups took 42 probes for an average of 2.625 probes/number.

16 lookups took 130 probes for an average of 8.125 probes/number.

16 lookups took 80 probes for an average of 5 probes/number.

16 lookups took 95 probes for an average of 5.938 probes/number.

16 lookups took 508 probes for an average of 31.75 probes/number.

128 numbers took 1532 probes for an average of 11.97 probes/number.

Press any key to continue . . .