1 Objective: Build a hash table that supports searching, insertion, deletion, printing, and integer hash key creation based on text or string input data. In the event of collisions, this separate chaining hash table will use a singly linked list to store duplicate keys.

2 Requirements

1. Read the input file formatted as follows. The input file will contain at least one command per line, either insert, delete, search, print, or quit. These are defined in detail below. And if appropriate, a second parameter may be required. This string would contain a name, typically, less than seven characters. This name will be the data used to generate the hash. For example, one of the input files, named 5inserts.txt contains the following: i homer i marge i nelson i gloria i duffman p

2. The specific commands are i for insert, d for delete, s for search, p for print, and q for quit.

(a) Insert The insert command uses the single character i as the command token. The command token will be followed by a single space, then the name which will be the characters used to calculate the hash key as defined below. The program will then insert the key and the data in the hash table. In the event that there is a duplicate key, the new key (and data) would be added to the appropriate slots linked list. (This commands success can be verified by using the print command.)

(b) Delete The delete command uses the single character d as the command token. The command token will be followed by a single space, then the name which will contain the characters used to calculate the hash key as defined below. The program will then delete that key and corresponding data from the hash table. In the event that the key cannot be found, the program will issue an error message and recover gracefully to continue to accept commands. (This commands success can be verified by using the print command.)

(c) Search The insert command uses the single character s as the command token. The command token will be followed by a single space, then the name which will contain the characters used to calculate the hash key as defined in the formula below. Upon successful location of the key, the corresponding key and data shall be output. In the event that the key cannot be located, the program will advise the user with a message. See the Output section for an example.

(d) Print The print command uses the single character p as the command token. This command will invoke the print function which will output all the slots in the hash table and subsequently, all the data in those slots. Given the size of the test data, the data ouput for each slot should contain the slot number, the hash key, and the data for that key. In the event that there is more than one data element in the slot, each element should be output, in the linked list order, until there is no more data in the slot. (See the Output section below for detailed formatting information.) This command is critical for verification of all the commands specified above.

(e) Quit The quit command uses the single character q as the command token. In the event the quit command is invoked, the program exits. There is no requirement for data persistence.

3. The hashing algorithm, as discussed in lecture and in the text, shall be based on Horners Rule which produces the following pseudocode 1 . h 0; for i 0 to s 1 do h (h C + ord(ci))mod n where C is a constant larger than every ord(ci). In this assignment use 27 as the value for C and the first command line parameter as the array size for the value of n. (See below.)

2.1 Functions While there are no specific design requirements (with one exception), it might be a meaningful suggestion to consider breaking this problem into several small classes. For example, a hash class and a linked list class would seem the minimal set of classes.