teaching machines

CS 245 Lecture 17 – Hashing Implications

March 27, 2014 by Chris Johnson. Filed under cs245, lectures, spring 2014.

Agenda

• what ?s
• what does this do?
• requirements of a key
• hashes in other languages
• think about this

TODO

• Trivia time! Why must a hashmap’s array sometimes be of a length that’s a prime number? What is the name of the hashmap class that Apple includes in their standard library for Objective-C? Who invented the hash table? Three answers for an extra credit 1/4 sheet.

What Does This Do?

public class Point2D {
  private int x, y;

  public Point2D(int x, int y) {
    this.x = x;
    this.y = y;
  }

  public static void main(String[] args) {
    Hashtable<Point2D, String> pointsToNames = new Hashtable<Point2D, String>();

    Point2D p1 = new Point2D(54, 96);
    pointsToNames.put(p1, "Treasure");

    Point2D p2 = new Point2D(54, 96);

    System.out.println(pointsToNames.get(p1));
    System.out.println(pointsToNames.get(p2));
  }
}

How Other Languages Think About Hashes

• Arrays are hashes: http://us2.php.net/manual/en/language.types.array.php
• Objects are hashes: http://www.quirksmode.org/js/associative.html

Think About This

Code

Point2D.java

package lecture17;

import java.util.Hashtable;

public class Point2D {
  private int x, y;

  public Point2D(int x, int y) {
    this.x = x;
    this.y = y;
  }
  
  @Override
  public int hashCode() {
    return x + y;
  }
  
  @Override
  public boolean equals(Object that) {
    if (this == that) {
      return true;
    } else if (that == null) {
      return false;
    } else if (!(that instanceof Point2D)) {
      return false;
    } else {
      Point2D thatPoint = (Point2D) that;
      return x == thatPoint.x && y == thatPoint.y;
    }
  }

  public static void main(String[] args) {
    Hashtable<Point2D, String> pointsToNames = new Hashtable<Point2D, String>();

    Point2D p1 = new Point2D(54, 96);
    pointsToNames.put(p1, "Treasure");

    Point2D p2 = new Point2D(54, 96);

    System.out.println(pointsToNames.get(p1));
    System.out.println(pointsToNames.get(p2));
  }
}

Acronyms.java

package lecture17;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Scanner;

public class Acronyms {
  public static void main(String[] args) throws FileNotFoundException {
    HashMaster<String, String> lingoToEnglish = new HashMaster<String, String>();
//    HashMap<String, String> lingoToEnglish = new HashMap<String, String>();

    Scanner in = new Scanner(new File("/Users/johnch/Desktop/lingo.csv"));
    while (in.hasNextLine()) {
      String line = in.nextLine();
      String[] fields = line.split(",", 2);
      lingoToEnglish.put(fields[0], fields[1]);
    }
    in.close();
    
    in = new Scanner(System.in);
    System.out.print("Enter term: ");
    String term = in.nextLine();
    if (lingoToEnglish.containsKey(term)) {
      System.out.println(lingoToEnglish.get(term));
    } else {
      System.out.println("Not invented yet...");
    }
  }
}

HashMaster.java

package lecture17;

import java.util.ArrayList;

public class HashMaster<K, V> {
  private ArrayList<KeyValuePair<K, V>>[] entries;

  public HashMaster() {
    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>>();
    }
    
    // TODO: Handle overwrites.

    // 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.equals(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.equals(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;
    }
  }
}

OurrayListGeneric.java

package lecture17;

public class OurrayListGeneric<T> {
  private T[] items;
  private int itemCount;

  public OurrayListGeneric(int initialCapacity) {
    items = (T[]) new Object[initialCapacity];
    itemCount = 0;
  }

  public OurrayListGeneric() {
    this(10);
  }

  public int size() {
    return itemCount;
  }

  public T get(int i) {
    if (i < 0 || i >= itemCount) {
      throw new IndexOutOfBoundsException("Hey, foobag! " + i + " isn't welcome here.");
    }
    return items[i];
  }

  public void add(T s) {
    // Are we full?
    if (itemCount == items.length) {
      T[] moreItems = (T[]) new Object[2 * items.length];
      for (int i = 0; i < items.length; ++i) {
        moreItems[i] = items[i];
      }
      items = moreItems;
    }

    items[itemCount] = s;
    ++itemCount;
  }

  public void remove(int i) {
    --itemCount;
    for (int j = i; j < itemCount; ++j) {
      items[j] = items[j + 1];
    }
    items[itemCount] = null;
  }

  public int indexOf(T s) {
    for (int i = 0; i < itemCount; ++i) {
      if (items[i].equals(s)) {
        return i;
      }
    }
    return -1;
    // throw new NoSuchElementException();
  }

  public void remove(T s) {
    int i = indexOf(s);
    if (i >= 0) {
      remove(i);
    }
  }

  public String toString() {
    String s = "[";

    if (size() > 0) {
      s += items[0];
      for (int i = 1; i < size(); ++i) {
        s += ", " + items[i];
      }
    }

    return s + "]";
  }
  
  public Iterator getIterator() {
    return new Iterator();
  }
  
  public class Iterator<T> {
    private int i;
    
    public Iterator() {
      i = 0;
    }
    
    public boolean hasNext() {
      return i < size();
    }
    
    public T next() {
      return get(i);
    }
  }

  public static void main(String[] args) {
    OurrayListGeneric<String> l = new OurrayListGeneric<String>(1);
    l.add("Mercury");
    l.add("Venus");
    l.add("Earth");
    l.add("Mars");
    l.add("Jupiter");
    l.add("Saturn");
    l.add("Uranus");
    l.add("Neptune");
    
    for (int i = 0; i < l.size(); ++i) {
      System.out.println(l.get(i));
    }
    
//    for (String planet : l) {
//      
//    }
    
    Iterator<String> i = l.getIterator();
    while (i.hasNext()) {
      String planet = i.next();
      System.out.println(planet);
    }
  }
}

Haiku