teaching machines

CS 245 Lecture 16 – Hashing

March 25, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• hashing
• implementing a hashtable
• the requirements of a key

TODO

• Start and finish preassignment 2.
• Thailand is in upheaval. Sync on Bitbucket, and pull in Eclipse to get an updated SpecChecker.

Code

HashTest.java

package lecture16;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Scanner;

public class HashTest {
  public static void main(String[] args) throws FileNotFoundException {
    HashMap<String, String> statesToCapitals = new HashMap<String, String>();
    
    Scanner in = new Scanner(new File("/Users/johnch/Desktop/states.csv"));
    while (in.hasNextLine()) {
      String line = in.nextLine();
      String[] fields = line.split(",");
      
      String state = fields[0];
      String capital = fields[1];
      
      statesToCapitals.put(state, capital);
    }
    in.close();
  }
}

HashMaster.java

package lecture16;

import java.util.ArrayList;

public class HashMaster<K, V> {
  private ArrayList<KeyValuePair<K, V>>[] entries;

  public HashMaster() {
//    entries = (ArrayList<KeyValuePair<K, V>>[])
//        new String[500];
    entries = new ArrayList[500];
  }

  public void put(K key,
                  V value) {
    int hashCode = key.hashCode();
    int index = Math.abs(hashCode) % entries.length;

    // Make a new empty list if we haven't been here before.
    if (entries[index] == null) {
      entries[index] = new ArrayList<KeyValuePair<K, V>>();
    }

    // Append pair at end of list.
    entries[index].add(new KeyValuePair<K, V>(key, value));
  }

  public V get(K key) {
    int hashCode = key.hashCode();
    int index = Math.abs(hashCode) % entries.length;

    if (entries[index] != null) {
      for (KeyValuePair<K, V> entry : entries[index]) {
        if (entry.key == key) {
          return entry.value;
        }
      }
    }

    return null;
  }
  
  public boolean containsKey(K key) {
    int hashCode = key.hashCode();
    int index = Math.abs(hashCode) % entries.length;

    if (entries[index] != null) {
      for (KeyValuePair<K, V> entry : entries[index]) {
        if (entry.key == key) {
          return true;
        }
      }
    }

    return false;
  }

  private static class KeyValuePair<K, V> {
    public K key;
    public V value;

    public KeyValuePair(K key,
                        V value) {
      this.key = key;
      this.value = value;
    }
  }
}

StateQuiz.java

package lecture16;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class StateQuiz {
  public static void main(String[] args) throws FileNotFoundException {

    HashMaster<String, String> statesToCapitals = new HashMaster<String, String>();
    ArrayList<String> justTheStates = new ArrayList<String>();
    
    // statesToCapitals.add("Wisconsin", "Rhinelander");
    // System.out.println(statesToCapitals.get("Wisconsin"));
    
    Scanner in = new Scanner(new File("/Users/johnch/Desktop/states.csv"));
    while (in.hasNextLine()) {
      String line = in.nextLine();
      String[] fields = line.split(",");
      justTheStates.add(fields[0]);
      statesToCapitals.put(fields[0], fields[1]);
    }
    in.close();
    
    in = new Scanner(System.in);
    Collections.shuffle(justTheStates);
    for (int i = 0; i < justTheStates.size(); ++i) {
      String state = justTheStates.get(i);
      System.out.print("What's the capital of " + state + "? ");
      String capital = in.nextLine();
      String expectedCapital = statesToCapitals.get(state);
      if (expectedCapital.equals(capital)) {
        System.out.println("Wow! You are a founding father/mother!");
      } else {
        System.out.println("No, that's the capital of Puerto Rico.");
      }
    }
  }
}

Haiku