CS14 Program 5

Assigned: November 29^th, 2001

Due: December 9^th, 2001 10pm

Topics

· Hash tables

· Performance comparison

The Class

Write a Hash Table class for storing integers in a closed hash table. The basic operaions of this class are insert and search. The class should enable the user to use one of three collision resolution schemes – linear, quadratic and double hashing. You will need to have two arrays in the class – one for storing the data and one for keeping track of whether a cell is occupied.

The size of the table is determined by the user. This means that the tables will have to be dynamically allocated in a constructor (supplied as parameter) or in a class method.

The class should have three different insert and search methods, one each for each of the schemes. The insert methods should return the number of probes necessary to successfully insert the item. The number of probes is as follows: if the item hashes to an empty cell, the number of probes is 1. If the cell is occupied, the number of probes necessary is the number of cells looked at before the item is stored, including the cell where it is ultimately stored.

The basic hash function is

H(key) = key % tablesize.

The second hash function (for use in double hashing) is

H2(key) = tablesize/2 – (key % (tablesize/15))

(you may safely assume tablesize is much bigger than 15).

The Program

Write a program that reads data from a file and inserts it into three different hash table objects, once with each collision resolution scheme. The program should keep track of the number of probes needed for each insert, and output the average number of probes/insert for each table.

The Data

The data is read from a file. The first line of the file is a number that is the table size. This is followed by the data to be inserted into the table. Data files are available in ~deganit/cs14/data/hash (this is a directory, not a web page) and also here.

To Do

· Write the class as described above.

· Write the program as described above.

· Run your program five times, once on each of the six data files.

· Summarize the results in a 5 x3 table in a file called README.

· Add a short paragraph explaining whether these results are consistent with what you expected from the collision resolution schemes.

What to turn in

· hash.h

· hash.cc

· main.cc

· makefile

· README

Extra Credit

Implement deletion for one or more of the schemes. This will involve modification to the insert and search methods as well.