teaching machines

CS 245 Lecture 22 – Hashtables

November 19, 2013 by . Filed under cs245, fall 2013, lectures.

Agenda

• what ?s
• turning keys into integers
• turning integers into indices
• handling collisions of indices
• chaining vs. linear probing
• finding word frequencies in Project Gutenberg

TODO

• Read chapter 14 through section 14.2. 1/4 sheet. Lab exercise will be easier if you read this before then.

Code

Map.java

package lecture22;

public interface Map<K, V> {
V get(K key);
}

Fastmap.java

package lecture22;

public class Fastmap<K, V> implements Map<K, V> {
private V[] values;

public Fastmap() {
values = (V[]) new Object[100];
}

@Override
public V get(K key) {
return values[key];
}

@Override
V value) {
values[key] = value;
}

public static void main(String[] args) {
Fastmap<Integer, String> ageToName = new Fastmap<Integer, String>();

System.out.println(ageToName.get(5));
}
}

CountedWord.java

package lecture22;

public class CountedWord implements Comparable<CountedWord> {
private String word;
private int count;

public CountedWord(String word) {
this.word = word;
count = 0;
}

public String getWord() {
return word;
}

public int getCount() {
return count;
}

public void tick() {
++count;
}

public String toString() {
return String.format("%30s %10d", word, count);
}

public int compareTo(CountedWord other) {
return -other.getCount() + getCount();
}
}

FrequentWordFinder.java

package lecture22;

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

public class FrequentWordFinder {
public static void main(String[] args) throws FileNotFoundException {
Scanner in = new Scanner(new File("/Users/johnch/Desktop/foodwar.txt"));
Hashtable<String, CountedWord> wordsToFrequencies = new Hashtable<String, CountedWord>();

while (in.hasNext()) {
String word = in.next().replaceAll("\\W", "").toLowerCase();

// do we already have an entry?
CountedWord countedWord = wordsToFrequencies.get(word);
if (countedWord == null) {
countedWord = new CountedWord(word);
wordsToFrequencies.put(word, countedWord);
}
countedWord.tick();
}

in.close();

ArrayList<CountedWord> words = new ArrayList<CountedWord>(wordsToFrequencies.values());
Collections.sort(words);
for (int i = 0; i < words.size(); ++i) {
System.out.println(words.get(i));
}
}
}

Haiku

Memories have keys
Oil dry takes me back home