Write a program to hash 5 letter words. You will decide on your own hash function. Use a table size of 2003. Use separate chaining. You must use the Standard Template Library list class for your chains. Allow for the following options (the user should be able to choose from the options as many times as they want):

• Insert words from a user specified file
• Insert word
• Search for a word
• Remove a word
• Print words in table to a user specified file

You must make your program keep track of the following things:

• Keep a count of the number of collisions when doing inserts. A collision is when a word is being inserted into a non-empty list; this should add 1 to the count (regardless of how many words are already in the list). All other options should not affect this count in any way.
• Keep track of how long each list is.

Then when the program is over, print out the number of collisions, the average list length, and the longest list length.

Extra credit may be given to a few of the top hashing programs. Thus you want to choose your Hash Function wisely and try and be original.

At the top of your program, in comments, you need to describe your hash function.

When you turn in your program electronically, be sure to turn in all your C++ files (.cc and .h) and a makefile. You must have your makefile name your executable hashing. Programs will be graded under Linux. Significant points will be taken off if your program does not compile with a makefile.

Much of the grading of your program will be based on not just getting code to do the necessary functions correctly, but on your actual coding. Be sure to use good programming where possible (use of classes, functions, good parameter passing techniques, operator overloading, templates, error checking). Make your program user friendly.

You should have turned in what you have thus far on your program at least 6 hours before the due date (by 6pm). Then as you continue to work on your program, continue to turn in more current versions.