# teaching machines

## CS 245 Lecture 16 – Hashing

### 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.
}

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>();

// 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(",");
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

I fear sharing twice
I hash story plus person
No reruns from me