COMPX201/COMPX241 23A Data Structures and Algorithms Assignment #4: Hash Tables
COMPX201-241 23A (HAM) Assignment #4 Hash Tables
Due: Friday 9th of June 11:59pm In this assignment you will write a program which stores key/value pairs in a hash table. Your hash table must include a hash function that uses the “folding with strings” technique. For part one you will be required to implement the majority of the functionality of the hash table, without collision handling. In part two you will then update your solution to use separate chaining to handle collisions. Your hash table should be implemented using appropriate data structures. Part One (60%): Define Java classes to implement a hash table of string key/value pairs following the specification given below.
-
The Hash Table: Define a class called StrHashTable in a file called StrHashTable.java. This class is to implement the following methods: ○ insert(Stringk,Stringv)-addsthestringkey/valuepairk,vtothe hash table at the appropriate index. Do not handle collisions. ○ delete(Stringk)-removesakey/valuepairfromthehashtable,giventhe key k. Again, leave collisions for part two. ○ hashFunction(Stringk)-usingthe“foldingwithstrings”method,createa hash function that returns the hash code for string k. ○ rehash() - increases the size of the hash table (two-fold) when the load factor reaches 75% capacity ○ contains(Stringk)-returnstrueifstringkisinthehashtable,false otherwise. ○ get(Stringk)-returnstheiteminthehashtable,giventhekeyk. ○ isEmpty()-returnstrueifthereisnothinginthehashtable,falseotherwise. ○ size()-returnsthenumberofitemsstoredinthehashtable. ○ dump()-printsthecontentsofthehashtabletothescreensuchthatitmatches the following format: index: key, value 0: key1, value1 1: key2, value2 2: key3, value3 3: ...
- The Node: define a class called Node for the nodes in your StrHashTable. It can either be an external class in a separate file called Node.java or an inner class of StrHashTable. It should have the following: ● A member variable to hold the string key. ● A member variable to hold the string value. ● A constructor that takes a key/value pair as two string arguments and copies them into the Node’s private member variable.
- Debugging: Write a program class that creates one or more of your StrHashTable objects and ensure that all your methods work as per the specification. You might, for example, write a program that reads words from a text file and puts them in your hash table counting the number of collisions that occur. Your program will not be marked, but is for your own solution development process. You may have additional member variables and methods if they are useful to you, but they should be private.
Part Two (40%): Define a new class called StrHashTableCollisions in a separate file called StrHashTableCollisions.java that is a copy of your StrHashTable class except that each of the appropriate functions must be updated to handle collisions. To handle these collisions, your solution must use the separate chaining method as discussed in class. Ensure that you update the dump() function to print the full contents of the table. Lastly, update your debug program to check that your new class works as expected.
Assessment: Completing Part One can earn up to a C+ grade (60%), but to be eligible for an A+ you must also complete Part Two. Your solution will be marked on the basis of how well it satisfies the specification, how well-formatted and easy to read your code is, the use of JavaDocs, and whether each class and public method has at least some comment explaining what it does, what it’s for, and what any of its arguments are (i.e. documentation). Your code should compile and run as a console program from the Linux command-line (i.e. no GUI). Students are encouraged to test their code in the lab prior to submitting their solutions
Submission: Create an empty directory (i.e. folder) using your student ID number as the directory name. Place copies of your source code in this directory. If you wish to communicate with the marker any additional information then you may include a plain text README file, but nothing else (e.g. no compiled code). Upload this directory through the Moodle submission page for this assignment.
