CS 245 Lecture 22 – Hashtables
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);
void add(K key, V value);
}
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
public void add(K key,
V value) {
values[key] = value;
}
public static void main(String[] args) {
Fastmap<Integer, String> ageToName = new Fastmap<Integer, String>();
ageToName.add(5, "Lewis");
ageToName.add(5, "Devin");
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
The smell of Dad’s shop
Oil dry takes me back home
The smell of Dad’s shop