Description
In this assignment you are to create Java code to build a hash table using information about students as input. The
input will consist of a stream of up to 95 transactions and data records, each having the following structure:
Field Description Type Size
transaction code alphabetic 1 character
“I” = insert
“F” = find
“R” = remove/delete
alphabetic 1 character blank
surname alphabetic 15 characters
given name alphabetic 15 characters
year of birth numeric 4 digits
gender Alphabetic 1 character
major alphabetic 6 characters
The hash table to be built consists of 100 entries, with keys ranging from 1 to 100. To build the table you will have
to create a hash function to generate the keys using the information in the records. The function will generate a
record key for the data and insert it and the data into the table. While the table is larger than the number of input
records, collisions are likely and will have to be dealt with. A hash function should provide a good abstract
representation of the data and minimize collisions.
In creating and coding the program:
1. The input is a single transaction text file, with up to 95 records as described above. A test file will be made
available on Blackboard.
2. The transaction code describes what to do with the record – insert, find, or remove
3. Insert means hash the record and place it in the table
4. Find means hash the record and search the table
5. Remove means hash the record and delete the record from the table
6. Choose your own hash function. Using one presented in Weiss or elsewhere is permitted. Provide attribution if
appropriate.
7. The hash table should be implemented as a 100 element array consisting of the generated key (1 to 100) and the
associated data.
8. Collisions are to be reconciled using one of the methods discussed in class
9. As each transaction is processed, print a copy of the transaction to output, along with what was accomplished
(record inserted, found, etc.), and note whether a collision was encountered
10. Print a copy of the hash table to output at the end of execution
Measuring and Analysis Report
You are to submit a short report (1-2 pages max) that describes your hash function and how you handle collisions.
Also include how many collisions were encountered while processing the transaction stream, how many extra table
slots needed to be examined when a collision occurred, and the overall load factor of the table at various stages of
the run, including the end.
What and where to submit:
All items are to be submitted through Blackboard in a single zipped directory named “PA4-HT.zip”.
Example: PA4-jdoeHT.zip. Name the code file “ExHash” (without the quotes). Do not make your code part of a
package. The unzip must unzip to a single directory that, in turn, has your code. Include:
1. The Java code used, with a comment block that includes your name, date, “INFS-519 Assignment 4”,
appropriate code attributions (if any), and a short description of the code’s input, processing, and outputs. All
code needed to execute from the command line must be included.
2. A pdf file that includes a log or screen shot of the output.
3. A pdf file of the 1-2 page report
How the assignment will be assessed
The Java code will be visually inspected and executed from command line using a set of test transactions from a .txt
file. An example file for you to use in debugging will be provided on Blackboard. That file does not necessarily
contain all possible combinations of expressions or errors. Your program must read the input file as an argument
and open it for processing. The GTA will not edit your code to hard code a file name. Programs correctly echoing
the input and processing the transaction stream without premature termination will be given full credit.
Item Assessment Description Max Value
Java Code All code submitted 45
Code is readable, commented, attributed when necessary 5
Execution Output Code executes against the transaction file error-free, produces the
transaction echo, and displays the hash table at the end of the run.
GTA assigns partial credit for less than 100% correct output, using
his judgment.
25
Written report A 1-2 page report describing the hash function and collision
handling strategy is included. Including a few examples of hash
input and output is encouraged. The report should be brief and
readable, and address the particular points requested. GTA may
assign partial credit.
25
Total 100
Extra Credit: As with the other assignments, for the class being held the night the assignment is due (11/16), I
would like a few students to volunteer to present their code and results to the class. This would be at most a 10
minute presentation that includes (1) a code walk-through, (2) discussing results, and (3) Q&A from the class. For
this presentation, concentrate on what your particular hash function does and how it handles collisions. Show
results from running against the provided transaction file. Contact me separately if interested. Priority will be
given to those who haven’t presented before. The number of presentations is limited to five. Extra credit of +5%
will be added to your cumulative assignment score (i.e. if the collective grade for all your assignments is 85% for
the semester, this increases it to 90%).
