solution

Write a program that implements a hash table using any of the methods described in Chapter 18 or the class videos or slides. You are free to use any hash function and any method you choose to handle hash collisions. Since you will be looking up entries based on the title, make your hash key use something from the title string — for example, the first character? the last character? (either of these will do some kind of hashing, but neither are a good choice). A few ways of handling collisions: you could chain them with a linked list on each “bucket”, or use open addressing with linear probing.

Requirements

The program should ask for a movie or show title, and output the information about that entry: the type, title, director, country and year.

• Loop until an exit is requested (by entering a blank name, -1, etc.).
• Use a case-sensitive search (assume queries are for the exact case in the file, no need to do any case checking/converting).
• Your program only needs to implement the “add” and “lookup” functionality, not deletes or rehashing/resizing of the table.
• If the title is not found, output “Not found in the table” or similar.
• This time, do not use any STL or any third-party libraries (for example, a Map) to implement the hash — it must be a hash of your own creation.
• The program must be able to retrieve any of the entries available in the file.
• Each entry should be hashed (some key generated, based in something about the record) i.e. do not read the data into linear array or some other fixed structure for your lookups.
• To test the performance of your hash function, your program should output the number of comparisons for each successful or failed lookup.

See if you can bring down the number of comparisons from your first attempt. A little Google searching will yield some string-optimized hash functions. There is no “right” answer, but hash functions that perform very poorly (close to a linear search) will lose points.

Assuming your table size is 2089 (the value in the starter file) successful queries should generally be below 10. If your numbers are consistently higher, try using a different hash function. Be sure to test both the unsuccessful and successful query cases.

Example Output

Read 5347 entries.
Enter a movie or show title (

Input File (CSV file):

https://docs.google.com/spreadsheets/d/1Ef3wdfyXvs8bsxD_BlzCLe6DTab-4RDlAbZX2fRM_Qk/edit?usp=sharing

It contains approximately 5300 lines of data. Here are the details:

• Each line contains info about a single TV show or movie.
• There is no header line (data starts on line 1).
• Each line has 5 comma-separated fields describing the TV show or movie, in this order:
  • type – contains the string “Movie” or “TV Show”
  • title – the full title
  • director – name of the director
  • country – the countries of release
  • year – the year of release
• You can assume the title field of each entry is unique in the file (this will be important for your hash function), but this may not be true of the other fields. All of the fields may include spaces and punctuation.

Starter file:

#include

}
// Reads a single entry, filling in the
// fields (title, etc.) passed by the caller.
void readSingleEntry(const string &str,
netflix_entry *newEnt) {
istringstream istr(str);
string fields[NFIELDS];
string tmp;
int i = 0;
// Read each field separated by a comma
while (getline(istr, tmp, DELIMITER) && i < NFIELDS) {
fields[i++] = tmp;
}
// Make a new Netflix entry based on the
// fields just read from the file.
newEnt->type = fields[0];
newEnt->title = fields[1];
newEnt->director = fields[2];
newEnt->country = fields[3];
newEnt->year = atoi(fields[4].c_str()); // Convert the string to an int
}
// Insert a new entry into the hash table
void entryInsert(netflix_entry *newEnt) {
//
// Complete this function.
//
// Accepts a new entry ‘newEnt’ and finds the correct hash bucket
// based on its hash key. Adds the entry to a bucket.
//
}
// This function accepts a string title and a reference
// to an empty entry.
//
// Upon return,
// – ‘foundEnt’ will be filled-in with what was found.
// – The function will return ‘true’ if something was found, ‘false’ otherwise.
// – The ‘ncmp’ parameter tracks the number of comparisons required
//
bool entryFind(const string &title, netflix_entry &foundEnt, int &ncmp) {
unsigned int key = getHashKey(title);
//
// Complete this function.
// (These are example parameters)
//
// Accepts a key, a reference to a found entry, and reference to
// number of comparisons. Fill-in the values of the ‘foundEnt’ with
// the values from the entry found in the hash table.
//
}
//
// Sample main().

//
int main() {
ifstream inFile(DATAFILE);
string inputLine, inputStr;
int linesRead = 0;
if (!inFile.good()) {
cerr << “Cannot open the input file!” << endl;
exit(-1);
}
// Read in each entry
while (getline(inFile, inputLine)) {
// Keep a counter of read lines.
linesRead++;
// Dynamically allocate a new entry
netflix_entry *entp = new netflix_entry;
// Read the next line from the file, passing a pointer
// to the newly allocated entry.
readSingleEntry(inputLine, entp);
// Now we have a complete entry, find where it goes
// in the hash table and add it.
entryInsert(entp);
// Extra debugging statement: uncomment this to
// see how many lines are being read from the file
// in real-time.
//
// if (linesRead % 25 == 0)
// cerr << “Inserted ” << linesRead << ” entries”
// << endl;
}
// Handle errors and/or summarize the read
if (linesRead == 0) {
cerr << “Nothing was read from the file!” << endl;
return (-1);
} else {
cout << “Read ” << linesRead << ” entries.” << endl;
cout << fixed << setprecision(2) << endl;
}
// (example) Forever loop until the user requests an exit
for (;;) {
//
// Your input loop goes here.
//
// If the user enters a blank line, use ‘break’.
// to exit the loop.
//
}
// And we’re done!
cout << “Exiting…” << endl;

return (0);
}