Discussion 9 handout

Group members (names & NetIDs)



Download the dis09 project code and open it as a project in IntelliJ as you would an assignment.

The file “HashDict.java” starts by declaring an Entry class, which stores a single key and its associated value. Note that the value of an Entry can be changed.

Next, review the fields of HashDict itself. Its state includes an array of “buckets”, each of which is represented as a linked list. Remember that the elements of arrays of objects default to null. Inside each bucket is 0 or more Entry objects.

Object diagram

Suppose we put the following key–value pairs into an instance of HashDict<String, Integer>:

Assume that buckets has a length of 4 and that modular hashing is used to derive an index from the hash code. Draw an object diagram for the dictionary instance. You may represent a LinkedList<T> as an object with a head field of type Node<T>, which has fields for data (a T) and next (a Node<T>).

Implementing operations


Study the partial implementation of get(). What should be done for each Entry in the bucket that the requested key belongs in?

Complete the TODO accordingly


Note that the implementation of put() has a similar structure to get(), but the method has different responsibilities in each case. Complete the first three TODOs by answering the question posed by each one.

Tip: try to avoid doing too much work in “special cases” if it is possible for that work to be handled in the general case. Bugs tend to hide in special cases.

What should happen when the bucket the key belongs in is null?

What should be done for each entry in the bucket that the key belongs in?

What should be done if we did not return in the above loop?


Run the HashDictTest test suite. You should pass all of the tests except the one checking the load factor limit. Notice how the tests are organized into a hierarchy of requirements that the class’s operations should fulfill. This is called “specification-style testing”, and it helps guide coverage while making failures easier to diagnose.


In order to maintain good performance as the dictionary grows, the hash table must be dynamically resized. Implement the resize() method according to its specifications.

Next, return to put() and make use of this method to enforce the load factor invariant documented in the class description. When enforcing the load factor invariant, how much bigger should the new table be to ensure an amortized O(1) resizing cost?

Ensure that the entire test suite now passes.


Handling the case where a bucket is null complicates the implementation of every operation in the class. Alternatively, we could have constructed a new empty list for every element whenever a new bucket array is allocated. Are there any drawbacks to this alternative approach?


  1. Open the assignment page for “Discussion activity 9” in CMSX
  2. [Recorder] Find the “Group Management” section and invite each group member
  3. [Others] Refresh the page and accept your invitation
  4. [Recorder] Take a picture of your work and save as either a JPEG or a PDF file named “discussion_responses”. After all invitations have been accepted, upload your picture along with your code as your group’s submission.
    • Recommended scanning apps: Microsoft Office Lens, Adobe Scan, Genius Scan, Evernote Scannable

Ensure that your group is formed and your work submitted before the Friday evening deadline.

Tips and reminders