Problems

Implement the put and get methods for a hash map.

import java.util.*;

class Tut07HashMap {
    
    // // Little class to store a key-value pair.
    // EXAMPLE: KeyValuePair keyValuePair = new KeyValuePair("Bulbasaur", 1);
    static class KeyValuePair {
        String key;
        Integer value;
        KeyValuePair(String key, int value) {
            this.key = key;
            this.value = value;
        }
        public String toString() {
            return key + "=" + value;
        }
    }
    
    // // The private array of buckets inside the hash map.
    private ArrayList<KeyValuePair>[] buckets;
    
    // // Constructor
    // NOTE: This looks scary for complicated Java reasons.
    @SuppressWarnings("unchecked")
    Tut07HashMap() {
        // Create a new buckets array 
        buckets = (ArrayList<KeyValuePair>[]) new ArrayList[7];
        // Iterate through the array and create a new (empty) bucket in each slot  
        for (int i = 0; i < buckets.length; ++i) {
            buckets[i] = new ArrayList<>();
        }
    }
    
    public String toString() {
        return Arrays.toString(buckets);
    }
    
    // Put (add, insert) a new key-value pair into the map.
    // NOTE: Can also be used to update a key's value.
    // NOTE: be sure to compare strings using stringA.equals(stringB),
    //       NOT the == operator
    void put(String key, Integer value) {
        // TODO
    }
    
    // Get (lookup) a key's value in the map.
    // NOTE: Return null if map doesn't contain key.
    Integer get(String key) {
        // TODO
        return null;
    }
    
    public static void main(String[] arguments) {
        Tut07HashMap numberFromName = new Tut07HashMap();
        numberFromName.put("Bulbasaur",  1);
        numberFromName.put("Ivysaur",    2);
        numberFromName.put("Venusaur",   3);
        numberFromName.put("Charmander", 4);
        numberFromName.put("Charmeleon", 5);
        numberFromName.put("Charizard", 42);
        numberFromName.put("Charizard",  6); // NOTE: Overwrites 42 with 6.
        
        // [Venusaur=3, Charizard=6], [], [Charmander=4], [Ivysaur=2], [], [Bulbasaur=1], [Charmeleon=5](/james-bern/CS136/wiki/Venusaur=3,-Charizard=6],-[],-[Charmander=4],-[Ivysaur=2],-[],-[Bulbasaur=1],-[Charmeleon=5)
        System.out.println(numberFromName);
        
        // 1, 2, 3, 4, 5, 6, null
        System.out.print(numberFromName.get("Bulbasaur")  + ", ");
        System.out.print(numberFromName.get("Ivysaur")    + ", ");
        System.out.print(numberFromName.get("Venusaur")   + ", ");
        System.out.print(numberFromName.get("Charmander") + ", ");
        System.out.print(numberFromName.get("Charmeleon") + ", ");
        System.out.print(numberFromName.get("Charizard")  + ", ");
        System.out.println(numberFromName.get("Imakuni?'s Doduo")); // NOTE: Returns null.
    }
} 

Custom hash functions.

Use your own custom hash function instead of the build in object.hashCode() and compare how many collisions you get. Can you design a really good hash function for this problem? Can you design a really bad one?

resize()

Once a hash map gets too full, it stops being as fast. This is because we waste a bunch of time looking through array lists. Load factor is the technical term for how full a hash map is. Add a method called resize() that doubles the number of buckets. Automatically call this function inside of put(...) if the load factor is high enough (NOTE: you may want to add an instance variable int size; that tells you how many elements are currently stored in the hash map).

• 🚨 This question is trickier than it sounds! You will need to rehash all the elements, because a key's bucket index Math.floorMod(key.hashCode(), buckets.length) is a function of the number of buckets!