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
.