CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 9 (In Person): Hash Tables

Your goal this week is to implement two hash tables: one using chaining, and one using linear probing. Then, we'll use your hash tables to quickly count the number of unique words in a very long novel.

Task 0: Starter Code

Chaining.java will contain the code for a hash table with chaining, and LinearProbing.java will contain the code for a hash table with linear probing. All code you write in this lab will be in these files. You have already been given the constructor for both hash tables, as well as code to get the slot for a key based on its hashCode().

Entry.java has a simple Entry class, with a key and a value. Note that the .equals() method calls .equals() on the keys (not the values) of the entries.

AbstractMap.java is an abstract class that implements some basic functionality common to both of our hash tables. It has instance variables for the number of entries in the table numEntries and the number of slots numSlots, and stores a constant for the maximum allowed load factor. The method getSlot(Object key) gets the canonical slot for a key, and resizeIfNecessary() checks if the load factor is greater than the bound, and resizes the array if so.

UniqueWords.java counts the number of unique words in a file using each of your hash tables. You need to give it the name of a text file as a command line argument. We have given you a sample file to count the words in: proust.txt.

Task 1: containsKey() for Chaining

Implement the containsKey() method in Chaining.java. Your method should use the getSlot() method (in AbstractMap.java) to find the slot for the given key, then look in the linked list for the slot. Some reminders/hints:

• If there is no linked list in the slot, you can return false immediately.
• If there is a linked list in the slot, you'll want to search through the linked list to find the entry with a matching key. (Since the .equals() method of Entry compares the keys, you can accomplish this by creating a new Entry and using contains(). Since containsKey() accepts an Object, this temporary Entry should probably have keys and values of type Object. Alternatively, you can iterate through the list manually using an iterator or for-each loop—any of these methods are acceptable.)

Task 2: put() for Chaining

Implement the put() method in Chaining.java. Your method should use the getSlot() method (provided for you in AbstractMap.java) to find the slot for the given key, then update the linked list. Some reminders/hints:

• If the slot does not already have a linked list (the slot is null) you should make a linked list for the slot before adding the new Entry.
• Remember that if the key already exists, you should update the value rather than adding a new Entry to the list; you should return the old value in this case. As in Task 1, you'll need to search through the list (either by creating a new Entry or using an iterator or for each loop) to check for this case.
• After adding a new entry, be sure to update the number of entries in the table, and call resizeIfNecessary() (given in AbstractMap.java) to resize the table if necessary. (Skip this step if you updated a value instead.)

Task 3: remove() for Chaining

Implement the remove() method in Chaining.java. This method is similar to containsKey(). Your method should use getSlot() to find the slot for the given key, then look in the linked list and remove the element. Some reminders/hints:

• If there is no linked list in the slot, remove() fails and you can immediately return null.
• We want to return the value associated with the removed key before deleting it: be sure to keep track of the value before calling remove.
• The easiest way to both find the appropriate value, and remove the item, is probably to first get the index of the key we're looking for using the LinkedList indexOf() method. Using the index, we can both get the entry (and its value), and then remove it.
• Remember to decrement the number of elements if the remove was successful.

Testing Chaining.java

Compile and run Chaining.java; make sure that the output matches expectations. (Each test has its expected output included; the whole table is also printed for reference.)

Task 4: Finding the Slot for LinearProbing

Our put() and containsKey() methods both, as a first step, find the canonical slot for the key and scan forward until finding an entry with matching key, or until finding an empty slot.

Fill in the helper method findKeyOrEmpty() to perform this scan. Don't forget to wrap around when you hit the end of the array. (You can use modulo or an if statement to wrap around.)

Task 5: put() for LinearProbing

Implement the put() method in LinearProbing.java. To begin, use findKeyOrEmpty() to find either an entry with a matching key or a null slot.

Depending on if you found a matching key or a null slot, you'll either want to update an existing entry (returning the old value), or create a new entry (incrementing the number of entries and resizing if necessary).

Task 6: containsKey() for LinearProbing

Implement the containsKey() method in LinearProbing.java. You should again begin with findKeyOrEmpty(). How can you use the result to immediately know if the key is present? (This method can be quite short.)

Testing LinearProbing.java

Compile and run LinearProbing.java; make sure that the output matches expectations. (Each test has its expected output included; the whole table is also printed for reference.)

Counting Words

UniqueWords.java contains code to count all of the words in a file using both of your hash tables.

We have given you a text file, proust.txt, which contains the famously-long novel "In Search of Lost Time" by Proust (in French). Run java UniqueWords proust.txt to find the number of unique words in the novel. The code should run quite quickly; the output for both tables should be 45329.

Submit

Submit your code to Gradescope (Lab 09) and ensure it passes all autograder tests (these are similar to the tests in the main methods). You should upload Chaining.java and LinearProbing.java. The autograder should give fairly useful output for any failed tests. Please let me know if there are any autograder issues.

Then, add, commit, and push your code files using git. Enter each of the following commands into your terminal.

git add Chaining.java LinearProbing.java
git commit -m "finished with lab 9"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab09, then each code file, and make sure that you can see the modifications you made. If you can see the changes, you're all set!