CS 14 - Lab

Hash Table

In this lab, you will write a program to hash 5 letter words. You will decide on your own hash function. Use seperate chaining. You must use the Standard Template Library list class for your chains.

Defining the hash table size

The size of your hash table should be specified as a defined value. If you look at hash_function.cc you will see that there is a value HASH_TABLE_SIZE that is not defined in this file. For this lab, you will be learning something new. Using a command line parameter to g++, you can define the value of constants used within your program during compilation. This is accomplished using the -D flag (usage = "-D HASH_TABLE_SIZE=10"). This example sets the hash table size to 10 for your program. This table size is extremely small so I suggest you test your program with table sizes into the thousands. So for this project, the flags to g++ in your makefile will be "-Wall -W -Werror -pedantic -g -D HASH_TABLE_SIZE=X" where X will be replaced with whatever size you want your table to be. Using this method will make it very simple for us to test your programs for different situations.

Functions you need to write:

void print ( ) - Print the hash table in the following format. Each array location will be printed on a seperate line. The line will start with the number of the array location followed by a : and followed by one tab. You will then print each word stored at that hash array location seperated by a , and a single space. After all words at that hash array location are printed, you will output a return. Here is a sample of what your output should look like
void processFile ( string filename ) - Add all of the words in the file specified as "filename" to the hash table. Here is a sample input file. Use push_back to insert each of the words into the list at the hash location that the words hashes to.
void printStats ( ) - Print the hash statistics: total number of collisions (keep track of this during insertions) and the length of the longest list.

Your main function should take the input file as a command line parameter, insert the values in the file into the hash table, print out the hash table to the screen, and finally print the stats immediately before returning from main

Hash table functionality test

After you have written these functions, use a table size of 10 and show the TA your output for this input file. Your output should look something like this.

Hash function test

Next you will need to create your own unique hash function. The hash function may be as simple or as complex as you want but if you want to do well in the extra credit competion, you will want to write a very good function that executes as fast as possible. After you create your own hash function, use a table size of 20 and show the TA your output for this input file. The TA will also look at your hash function to make sure that it is deterministic.

Extra Credit

After you have checked out for the lab (shown both outputs from above) you may compete in the extra credit competition for 50% extra credit on this lab. Use a table size of 2005 for the random input and the dictionary input. Use the time command to time how long your program takes to execute (user time is what you want to be looking at). Write your name on the board with the stats for your hash function (for both input files, write the user time, the total number of collisions and the longest list length). The stats you write on the board don't have to be your final stats for your code. You may continue to work and tune your hash function to make it better and then change your stats. During the last 5 minutes of lab, the TA will look at the stats to determine the group with the best hash function. That group will then need to verify the stats to the TA (run your program and show the stats and the running time).

Point Breakdown For Lab Assignment

You will demo your hash table in lab. The TA will look at the hash table output for the input test1.txt and a table size of 10 to get your functionality points for the lab ( sample output). You will then need to demo your unique hash function to the TA with a table size of 25 and the input test2.txt After that, spend the rest of the lab working on perfecting your hash function. Remember, to receive credit for this lab, you MUST turn the code in online as well as demo in lab, however, you will only receive points for what you demo to the TA during lab section. If you do not turn in your code online, you will lose points for your lab. All code must be turned in online for archival purposes.

2 points - Attendance is, as always, worth 20% of your lab grade.
1 point - Application takes the input file as a command line argument
1 point - Defining your hash table size during compilation
4 points - Hash table functionality test
2 points - Hash function test

Deductions -

-.5 points - Not error checking the number of command line arguments
-.5 points - Not error checking the opening of the input file
-1 point - Any memory leaks.
-1 point - If both partners turn in the code. There should only one turnin per group
-1 point - if your program seg faults at any point during execution.
-1 point - not using a makefile
-1 point - program does not compile with the standard flags: -Wall -Werror -W -pedantic
-1 point - not logically seperating your code into seperate files
-5 points - Turned into the wrong lab section.
-1 point - No name on work turned in
-5 points - Code not turned in at all. This deduction also applies to turnins that do not contain a the partners name (only the name that is not on the turnin will have 5 points deducted. The person that actually turned the code in will only have 1 point deducted if their name is not on the turnin).
-5 points - If your currently assigned partner is in lab and you do not work together.