Lab 9: Tree Maps vs. Hash Maps

In this lab, you’ll create BSTMap, a BST-based implementation of the Map61B interface, which represents a basic map. Then, you’ll create MyHashMap, another implementation of the Map61B interface, which instead represents a Hash Map rather than a Tree Map. This lab is pretty long, so it’s unlikely you’ll finish in the allotted time. Don’t worry, though, the autograder is friendly, and you shouldn’t stress about completing every last part, though doing so is great midterm practice.

# 1: BSTMap

The skeleton provides a BSTMap that implements the Map61B interface using a BST (Binary Search Tree) as its core data structure in a file named BSTMap.java. We provide instance variables, a constructor, and a clear method. Your goal is to implement get, put, and size. Other methods such as remove, keySet, and iterator are optional for this lab, and by default should throw an UnsupportedOperationException unless you choose to implement them.

For get and put, you may find it useful to use the putHelper and getHelper helper methods we’ve provided you in the skeleton. We recommend that you work on methods in the order they appear int he file.

Note that the BSTMap class is declared such that the generic keys extend Comparable<K>, so you should use the compareTo method found in the Comparable interface to compare keys.

The following resources might prove useful:

• BST code from our optional textbook.
• Pages 396-405 from our optional Algorithms textbook.
• ULLMap.java (provided), a working unordered linked list based Map61B implementation.
• Lecture 21 slides.
• BST code from pages 109 and 111 of Data Structures Into Java, from our course references page.

You can test your implementation using the TestBSTMap class in the lab9tester package. If you fail tests, we recommend creating a very short main method and using the visualizer, e.g.

public static void main(String[] args) {
BSTMap<String, Integer> bstmap = new BSTMap<>();
bstmap.put("hello", 5);
bstmap.put("cat", 10);
bstmap.put("fish", 22);
bstmap.put("zebra", 90);
}


# 2: MyHashMap

The skeleton provides a MyHashMap that implements the Map61B interface in a file named MyHashMap.java. Your implementation is required to implement get, put, and size. Other methods such as remove, keySet, and iterator are optional for this lab, and by default should throw an UnsupportedOperationException unless you choose to implement them. We’ve provided instance variables for you.

We provide the following constructors:

public MyHashMap();
public MyHashMap(int initialSize);


We also provide the clear method and a private hash method that computes the hash function of a key.

Unlike lecture (where each bucket was represented as a naked recursive linked list), each bucket in this lab is implemented as an ArrayMap, similar to what we developed in lecture 13. Because our bucket class is so powerful, your get and put methods will be very short (our get method is only 2 lines, and our put method isn’t many more).

While using such a sophisticated bucket class seems like cheating, it’s not. Delegating work to a helper class is a very important way to manage complexity, and there’s really no reason that the MyHashMap class should be doing things like manually scanning through buckets – that’s the bucket’s job!

Start by implementing get, put, and size with no resizing. After you’ve made figured these out, modify put so that it resizes. You should resize the array of buckets anytime the load factor exceeds MAX_LF, and you should resize multiplicatively (e.g. doubling the number of buckets) rather than arithmetically (e.g. adding 100 new buckets).

You can test your implementation using the TestMyHashMap class in the lab9tester package.

You may find the following resources useful:

• Chapter 3.4 of our optional Algorithms textbook.
• HashTable code code from our optional textbook.
• ULLMap.java (provided), a working unordered linked list based Map61B implementation.
• Lecture 23 slides.
• Hash table code from pages 136 and 137 of Data Structures Into Java, from our course references page.

# 3: TA Overview

At the end of lab, your TA will go over our solutions for BSTMap and MyHashMap.