Answered step by step
Verified Expert Solution
Question
1 Approved Answer
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
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 readall of the words, you should outputthe total numberofwords 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 mustsupply 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 . Youmust submit your project in a zipfile as specified under submission . There will be four command line arguments to your program 1. The name of the input file 2. The name of the query file 3. The size of the hash table 4. The collision resolution strategy, Ip 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 96 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)
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started