「CS61B」Note(3) Lab9 Tree Maps vs. Hash Maps
The requirements of this lab is at this link.
BSTMap
In this lab, the first task is to create BSTMap, a BST-based implementation of the Map61B interface, which represents a basic map.
get, put and size
Implementing get, put, and size is not hard, as the BST code from optional Algorithms textbook is very useful which I can follow to bilud up my own. And each function uses a helper function to implement recursion (e.g. putHelper to put).
/** Returns the value mapped to by KEY in the subtree rooted in P.
* or null if this map contains no mapping for the key.
*/
private V getHelper(K key, Node p) {
if (key == null) throw new IllegalArgumentException("calls get() with a null key");
if (p == null) {
return null;
}
int cmp = key.compareTo(p.key);
if (cmp == 0) {
return p.value;
}
else if (cmp < 0){
return getHelper(key, p.left);
} else {
return getHelper(key, p.right);
}
}
/** Returns the value to which the specified key is mapped, or null if this
* map contains no mapping for the key.
*/
@Override
public V get(K key) {
return getHelper(key, root);
}
/** Returns a BSTMap rooted in p with (KEY, VALUE) added as a key-value mapping.
* Or if p is null, it returns a one node BSTMap containing (KEY, VALUE).
*/
private Node putHelper(K key, V value, Node p) {
if (p == null) {
size += 1;
return new Node(key, value);
}
int cmp = key.compareTo(p.key);
if (cmp < 0) {
p.left = putHelper(key, value, p.left);
}
else if (cmp > 0) {
p.right = putHelper(key, value, p.right);
}
else {
p.value = value;
}
return p;
}
/** Inserts the key KEY
* If it is already present, updates value to be VALUE.
*/
@Override
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("calls put() with a null key");
root = putHelper(key, value, root);
}
/* Returns the number of key-value mappings in this map. */
@Override
public int size() {
return size;
}
Other methods including remove, keySet, and iterator are optional for this lab, and much harder than those above. I spent hours on the solutions. Firstly, write some helping methods that might be useful.
// Check if the map is empty.
public boolean isEmpty() {
return size() == 0;
}
// Return the minimum key of the map.
public K min() {
return min(root).key;
}
private Node min(Node x) {
if (x.left == null) return x;
else return min(x.left);
}
// Return the maximum key of the map.
public K max() {
return max(root).key;
}
private Node max(Node x) {
if (x.right == null) return x;
else return min(x.right);
}
keySet
keySet()Returns a Set view of the keys contained in this map. I don’t think there is a need to implement Set interface by myself, so I simply used TreeSet to implement it in my code.
@Override
public Set<K> keySet() {
if (isEmpty()) return new TreeSet<K>();
Set<K> set = new TreeSet<K>();
keys(root, set);
return set;
}
private void keys(Node x, Set<K> set) {
if (x == null) return;
set.add(x.key);
keys(x.left, set);
keys(x.right, set);
}
I wrote a long and complex version of keySet()according to the textbook at first, then I improved it a little bit and make it shorter to the version above.
@Override
public Set<K> keySet() {
if (isEmpty()) return new TreeSet<K>();
return keys(min(), max());
}
public Set<K> keys(K lo, K hi) {
Set<K> set = new TreeSet<K>();
keys(root, set, lo, hi);
return set;
}
private void keys(Node x, Set<K> set, K lo, K hi) {
if (x == null) return;
int cmplo = lo.compareTo(x.key);
int cmphi = hi.compareTo(x.key);
if (cmplo < 0) keys(x.left, set, lo, hi);
if (cmplo <= 0 && cmphi >= 0) set.add(x.key);
if (cmphi > 0) keys(x.right, set, lo, hi);
}
Remove
/** Removes KEY from the tree if present
* returns VALUE removed,
* null on failed removal.
*/
@Override
public V remove(K key) {
if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
V value = get(key);
if (value != null) root = remove(root, key);
return value;
}
private Node remove(Node x, K key) {
if (x == null) return null;
int cmp = key.compareTo(x.key);
if (cmp < 0) x.left = remove(x.left, key);
else if (cmp > 0) x.right = remove(x.right, key);
else {
size -= 1;
if (x.right == null) return x.left;
if (x.left == null) return x.right;
Node t = x;
x = min(t.right);
x.right = removeMin(t.right);
x.left = t.left;
}
return x;
}
private void removeMin(){
root = removeMin(root);
}
private Node removeMin(Node x){
if (x == null) return null;
if (x.left == null) {
return x.right;
}
x.left = removeMin(x.left);
return x;
}
/** Removes the key-value entry for the specified key only if it is
* currently mapped to the specified value. Returns the VALUE removed,
* null on failed removal.
**/
@Override
public V remove(K key, V value) {
if (get(key) == value) return remove(key);
return null;
}
iterator
I simply used the iterator of keySet as which of BSTMap, it can do keys iteration. If you want to make the values of the map iterable, just use get(K key) in the iterator you build.
@Override
public Iterator<K> iterator() {
return keySet().iterator();
}
MyHashMap
Using MyHashMap to implement the Map61B interface.
get, put and size
/**
* Computes the hash function of the given key. Consists of
* computing the hashcode, followed by modding by the number of buckets.
* To handle negative numbers properly, uses floorMod instead of %.
*/
private int hash(K key) {
if (key == null) {
return 0;
}
int numBuckets = buckets.length;
return Math.floorMod(key.hashCode(), numBuckets);
}
/* Returns the value to which the specified key is mapped, or null if this
* map contains no mapping for the key.
*/
@Override
public V get(K key) {
if (buckets[hash(key)].containsKey(key)) {
return buckets[hash(key)].get(key);
}
return null;
}
/* Associates the specified value with the specified key in this map. */
@Override
public void put(K key, V value) {
if (!buckets[hash(key)].containsKey(key)) {
size += 1;
}
buckets[hash(key)].put(key, value);
if (loadFactor() > MAX_LF) {
resize(2);
}
}
/* Returns the number of key-value mappings in this map. */
@Override
public int size() {
return size;
}
resize
It requires to resize the array of buckets anytime the load factor exceeds MAX_LF. The original loadFactor() returns an int. I don’t konw the reason, but I changed it to double so that MAX_LF = 0.75 makes sense.
private double loadFactor() {
return size * 1.0 / buckets.length;
}
I need to create a temp MyHashMap which is of the new size to save the key-values in old map, then replace the old MyHashMap. A overloaded constructor MyHashMap(int setSize) is required because wo need to build up the temp MyHashMap with certain bucket size and use it in the resize function.
public MyHashMap(int setSize) {
buckets = new ArrayMap[setSize];
this.clear();
}
private void resize(double rate) {
MyHashMap<K, V> temp = new MyHashMap<K, V>((int) (buckets.length * rate));
for (ArrayMap<K, V> ks : buckets) {
for (K key : ks) {
temp.put(key, get(key));
}
}
this.buckets = temp.buckets;
this.size = temp.size;
}
keySet and remove
I resize the array of buckets when the load factor is below MIN_LF, which I set to 0.25.
/* Returns a Set view of the keys contained in this map. */
@Override
public Set<K> keySet() {
Set<K> set = new TreeSet<K>();
for (ArrayMap<K, V> ks : buckets) {
for (K key : ks) {
set.add(key);
}
}
return set;
}
/* Removes the mapping for the specified key from this map if exists.
* Not required for this lab. If you don't implement this, throw an
* UnsupportedOperationException. */
@Override
public V remove(K key) {
if (get(key) != null) {
size -= 1;
V removedValue = buckets[hash(key)].remove(key);
if (loadFactor() < MIN_LF) {
resize(0.5);
}
return removedValue;
}
return null;
}
/* Removes the entry for the specified key only if it is currently mapped to
* the specified value. Not required for this lab. If you don't implement this,
* throw an UnsupportedOperationException.*/
@Override
public V remove(K key, V value) {
if (get(key) == value) {
return remove(key);
}
return null;
}
@Override
public Iterator<K> iterator() {
return keySet().iterator();
}
