CSCI H343 Data Structures Fall 2024

Lab: Hash Tables with Separate Chaining

Background and Overview

The goal for this lab is to implement a hash table that uses separate chaining. The Map interface in Map.java specifies the methods that should be provided by your HashTable class.

Student Support Code and Submission

Problem Set

Problem 1: Hash Table

The first thing you should do is complete the hash method. As you may recall, this should convert an object into an integer index into the hash table’s array. Java provides a hashCode() method for every object, which returns an integer between Integer.MIN_VALUE and Integer.MAX_VALUE, which you should use for this step.

You will also complete the following methods in the HashTable.java file, implementing the Map interface.

You will also need to implement the constructor for HashTable, in which you will need to initialize the table. The constructor should have one parameter, the initial table size:

public HashTable(int table_size);

As usual, you may create any helper methods that you find useful.

Problem 2: Testing

Write your test cases in StudentTest.java with the method named test(), which should thoroughly test the hash table.

Test and debug your own code from Problem 1 locally and then submit both your code and your test cases to Autograder for grading.

The Autograder will apply your tests to buggy implementations of the HashTable class. You receive 1 point for each bug detected. The Autograder will also apply your tests to a correct implementation to rule out false positives.