Java Hash Exercise

This is an in-class exercise on hash functions that created at Northeastern University. Its purpose is to:

• illustrate how user-written hash functions affect hash set performance
• challenge students to think about what makes a good hash function for a given corpus

It can be used with Gradescope or GitHub Classroom, and we are working on a Pawtograder version.

Classroom use

The recommended usage is:

1. Going over the implementation of HashSet.java with students, showing them how the hashCode() function is used.
2. Discussing the contract for hashCode(), which requires equals() objects to have equal hash codes. Point out that this is a legal implementation but that it will lead to maximal collisions, reducing the set table's performance to that of a linked list:

@Override
public int hashCode(){
    return 42;
}

3. Providing students with MyString.java and challenge them to write a better hash function without calling any existing implementations of hashCode(). (It is up to you whether to provide any examples of good hash functions or allow them access to online resources.)
4. Having students submit their files to a Gradescope assignment you create for immediate feedback on the number of collisions their function causes on a hidden (or visible) corpus.
5. Sharing the implementations that perform the best, either in that class session or the next one.

Creating the Gradescope assignment

Follow video instructions to create a Gradescope assignment, which can be summarized as follows:

1. Download autograder.zip from the latest release or build the zip file by cloning this repository and running ./make_gradescope_autograder.sh.
2. Create a Programming Assignment on Gradescope, enabling a leaderboard.
3. Configure the autograder, which includes:
   1. Selecting the latest Ubuntu image.
   2. Selecting JDK 17.
   3. Uploading autograder.zip.
   4. Clicking on Update Autograder.
   5. Uploading a test submission from a sample-submissions subdirectory.

Creating the GitHub Classroom assignment

See README-GITHUB-CLASSROOM.md.

Customizations

Here are ideas for customizing the assignment:

1. Replacing the corpus, such as using the names of your students or a list of courses offered at your university.
2. De-generifying HashSet to simplify the code.
3. Replace MyString with a class students have used for another assignment.

Recommended Reading

Anyone interested in hash functions, especially for Java, should read Item 11: Always override hashCode when you override equals in Effective Java (3rd edition) by Joshua Bloch (Pearson, 2018).

The Java 1 String.hashCode() implementation is an interesting historical relic that has the curious property of O(1) runtime.