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.
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
I fear sharing twice
I hash story plus person
No reruns from me
I hash story plus person
No reruns from me