# teaching machines

## CS 245 Lecture 17 – Hashing Implications

March 27, 2014 by . 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));
}
}

### Think About This

You are keying customer data records on 5-digit ZIP codes. The backing array holds 1000 elements.

1. How many records can you store before experiencing a collision?
2. Suppose the hashCode function is return zipCode / 10. Is this good or bad? Under what conditions?
3. A colleague proposes a new hashCode function: return new Random().nextInt(). Is this good or bad? Under what conditions?
4. You need to print a log of all records. How might you iterate through all the key-value pairs?

### 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

I called, “Hey, Jenny!”
Thirty women looked at me
The rest were Sarah

I called out, “Hey, Matt!”
About thirty men looked up
The others were John