C++ code only

Description:

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:

Youmust 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.

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)

Examples

1)

more hashtest1.txt This is a sample input file It is ten words

more hashq1.txt sample

is ten this a void five make g++ hash.cpp -o project3

./project3 hashtest1.txt hashq1.txt 13 qp

The number of words found in the file was 10 The number of unique words found in the file was 9

The number of collisions was 5

sample appears on lines [1]

The search had 0 collisions

is appears on lines [1,2]

The search had 0 collisions

ten appears on lines [2]

The search had 0 collisions

this appears on lines []

The search had 1 collisions

a appears on lines [1] The search had 0 collisions

void appears on lines []

The search had 1 collisions

five appears on lines []

The search had 6 collisions

2)

./project3 hashtest1.txt hashq1.txt 13 lp

The number of words found in the file was 10 The number of unique words found in the file was 9 The number of collisions was 3

sample appears on lines [1]

The search had 0 collisions

is appears on lines [1,2]

The search had 0 collisions

ten appears on lines [2]

The search had 0 collisions

this appears on lines []

The search had 1 collisions

a appears on lines [1] The search had 0 collisions

void appears on lines []

The search had 1 collisions

five appears on lines []

The search had 3 collisions

3)

./project3 hashtest1.txt hashq1.txt 13 dh 3

The number of words found in the file was 10 The number of unique words found in the file was 9

The number of collisions was 6

...