COP 3538 – Data Structures with OOP
Project 5 Summer 2013
Due: Tuesday, June 26th, midnight
Please note that this assignment is shorter and will require a bit less effort.
Hash Tables
Using NetBeans 7.1, you are to write a Java program using OOP principles to accommodate the following functionality
Assignment #5
Objectives:
Provide student with exercises in hashing (randomizing) and collision processing
Provide student with experience in inserting, deleting, and changing node contents in a hash table
Functionality:
Given a sequential file, ECountries.Trees.txt on my web page, you are to build a hash table based on Country name.
Task 1: Build Hash Table: You are to build the hash table in the order of appearance of the records in this input data file. Note this file is a comma-delimited sequential file. Use the hashing of strings algorithm (see book and lecture notes part 2) for the algorithm as your hashing function. You are to use separate chaining as your collision algorithm (see also textbook and my lecture notes). Each entry in the hash table is a Country object containing the European country and its capital. Do not include the capital’s population. Your linked list needs to be sorted on country name. For uniformity in computing your key, use tolower() so that all characters in your input key (country name) are lower case and then subtract 97 from each character; add the resulting numbers and mod the total by 23 (see ahead).
Task2: Display Hash Table: Once the hash table is built from the input constrained by the hashing and collision algorithms cited above, you are to display the hash table and its links. Your format – always include nice headers, etc. – should appear in tabular format:
Hash table index (integer) in the left most column starting with zero followed by five spaces, followed by the Country name only. Both columns are to line up under a header that includes: index Country Name. Any items linked to this home address are to appear lined up and nicely spaced to the right of this first entry, aligned on the left spaces in between any succeeding collision at that hash table address. Synonyms are to include Country only. If a specific hash table entry has no occupants, then, say, the index 16 is still to appear in your output format, but it will have no entries to its right. You may print a series of asterisks in the attribute to indicate null.
The size of the hash table is to be 23. Thus output detail data must have 22 detail lines.
Task 3: Update the Hash Table: Using the ECountriesTreesUpdate.txt, you are to update your hash table. Inserts should be simple and use the same hashing and collision algorithms that were used to build the table. A è Add and D è Delete.
Deletions: These are to be flagged with a delete byte. Items are to be logically deleted and not physically deleted.
Adds: Add the additional Countries to the hash table.
Task 4: Display Updated Hash Table: Using the format described above, you are to display the updated hash table and its links. For those records that are logically deleted, but still physically present, you are to display the Country name followed by an asterisk, as in: Spain*.
Task 5: Error Transactions: Your program is not to include dupes or other error conditions. So, if, in processing the update transactions, you encounter a dupe add or if you are unable to find a corresponding delete transaction, you are after updating and printing the updated hash table, an error listing. Provide a header, such as Error List
and follow this with a/the list in order of occurrence of erroneous transactions with the tag: dupe add or not found tag as appropriate. You are to write these erroneous transactions to a temporary sequential file, close the file after task 3 is over, open this file, and display the Error List. (I realize Israel is not in Europe)
You have PLENTY of time if you start right away and work slowly and methodically. Don’t get caught by some surprise late in the game.
Deliverable: Zipped folder MUST include copies of the input and supporting files.
You are to zip all files in your P5 folder as expected and Send them to be via Blackboard using our standard naming conventions.
Grade Sheet for Program 5
Name: ______
Grade: ______
Code and Program Structure: ------20 points
This is your choice. Choose wisely. Document your architectural design with UML
Outputs: ------40 points
Must be absolutely wonderful. Output specifications will be rigidly enforced. You know the drill by now. J