teaching machines

CS 245 Lecture 22 – Hashtables

November 19, 2013 by Chris Johnson. 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);
  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