This project will be about building a hash table. You will read words, separated by whitespace, from a given file into your program. As you read the words, you should insert each word into a hash table. The word itself is the key value, and each entry in the hash table also needs to store a list of the line numbers where the word appears. When inserting a word that already appears in the hash table, simply add the current line number to the list for the word. You will also count the number of collisions that occur while inserting words into the hash table. Every probe to a cell that contains a word other than the one being inserted or searched should count as an additional collision, so that inserting a word may have multiple collisions. Probes to empty cells or cells already containing the word do not count as collisions.

Once you have read all of the words, you should output the total number of words read, the number of distinct words, and the total number of collisions that occurred in the hash table.

Finally, you will read words from the query file and report the line numbers where the word occurs, and the number of collisions while searching for the word in the table.

Requirements

Please carefully read the following requirements:

You must supply a makefile that builds an executable named project3

You must use C++ streams for all I/O

You must format your output as shown in the example below.

You must do your own work, you must not share code.

You must submit your project in a zipfile as specified under submission

There will be four command line arguments to your program.

The name of the input file

The name of the query file

The size of the hash table

The collision resolution strategy, lp for linear probing, qp for quadratic probing, and dh for double hashing. If the strategy is double hashing, the double hash function will be of the form h2(x) = a (x % a), and the integer parameter a will be the fifth command line argument.

You should use the djb2 hash function. (http://www.cse.yorku.ca/~oz/hash.html)