CSC241 Hash Table

This lab is a multi-file project on hash tables in which collision resolution is implemented with linked lists and separate chaining. You have been given a skeleton for HshTbl.java. In addition, you also have at your disposal a fully functional implementation for a sorted linked list in the form of SrtdLnkLst.jar . This list has an insSort method so that it builds the list in a sorted fashion and a bSearch method so that it can use a binary search to look for records in this list. This gives you a tremendous performance enhancement over a linear linked list. You are to supplement the hash table functionality with the following functions:

• createFromFile - This function accepts a String representing the input file name. It reads the file one record at a time and then performs an insertion into the hash table. It returns an int representing the number of records inserted into the table; a failure status from BaseLnkLst.java, otherwise. The key SSNs associated with each read record are hashed in order to determine in which linked list of the table they belong. The method hash is provided for you in the skeleton HshTbl.java. It takes as input a final Data and returns the int representing the index into the LnkLst array that is contained in the HshTbl class.
• delRec - Deletes the entry associated with a particular key. If the operation is successful, the function returns an int representing the number of elements remaining ONLY in the linked list that contained the key; otherwise, some appropriately defined failure constant is returned. This method's argument is a final Data containing the key SSN of the record to be deleted.
• ins - performs the actual insertion into that list. It accepts as input the final Data to be inserted. It returns an int representing the number of nodes ONLY in the LnkLst in which the data was inserted; a failure status from BaseLnkLst.java, otherwise. This method is based on the insSort method of the SrtdLnkLst class.
• length - This returns the total number of records held in the hash table. The output is an int that is set to the failure status from BaseLnkLst.java if the method encounters a problem.
• search - Searches the hash table for a specific key. search must search through the linked list associated with the hash value of the search key in order to find the record connected with that key. This method is based on the bSearch method of the SrtdLnkLst class. The argument is the key that is passed as a final Data. If the record associated with the search key is found, then an int is returned representing the index in the SrtdLnkLst[]in which the search key was found. For example, if the search finds the key in SrtdLnkLst[n], then n is returned. If the search fails, then the failure status from BaseLnkLst.java is returned.

Write a driver that continuously re-prompts the user for an input file name. The file will be binary and contains the usual randomized information. This driver is so similar to those of the previous labs that it will take you no time at all to modify it for this assignment.

After the file name has been successfully acquired, invoke the createFromFile to read the file and build the hash table.

Upon returning and only if the status is successful, the driver will continuously re-prompt the user to enter a search SSN. This is used to create a Data instance that becomes a final Data argument to the search method. This method searches for the record associated with the key. If the record is/isn't found, a typical report is written. The driver should re-prompt the user to see s/he would like to search for another record. If the user does not want to search for another record, the driver then re-prompts the users to see if s/he wants to start again with another file. Your output should appear as follows:

Enter the file you want read - Lab.txt

c:\Lab.txt could not be opened.

Do you wish to continue with another file (Y/N)? - y

Enter the file you want read - unsortedData.bin

Preparing to read unsortedData.bin

unsortedData.bin has 1000000 records.

Enter the search SSN (no separators please) - abcdefghi

SSN abc-de-fghi was not found.

Do you wish to continue with another SSN (Y/N)? - y

Enter the search SSN (no separators please) - C5f*y"WT>

Searching for SSN C5f-*y-"WT>

The key was found in record # 176.
The search required 1 ms to complete.

SSN = C5f-*y-"WT>
fName = <$5D|\W]/0kGBWHL)`d*
mName = d
lName = {|(1!iXRlr+"0R]kk9!rF&ao1,C+Uq
addr = F&sy\?^+hl35%b=E:1K"|TL,[F#Mj;J=KTU5/I,E
city = o$_WI_xhNydCT^K@zYq9
state = &U
zip = oY0]-,SCA

Do you wish to continue with another SSN (Y/N)? - n
Do you wish to continue with another file (Y/N)? – n