Optimize Judiciously

4.2 Hashing
"More computing sins are committed in the name of efficiency (without
necessarily achieving it) than for any other single reason - including
blind stupidity." - William A. Wulf

"We should forget about small efficiencies, say about 97% of the time:
premature optimization is the root of all evil." - Donald E. Knuth

"We follow two rules in the matter of optimization:

Rule 1: Don't do it.
Rule 2 (for experts only). Don't do it yet - that is, not until you have
a perfectly clear and unoptimized solution."
- M. A. Jackson

Reference: Effective Java by Joshua Bloch.

Robert Sedgewick and Kevin Wayne • Copyright © 2005 • http://www.Princeton.EDU/~cos226 2

Hashing: Basic Plan. Choosing a Good Hash Function

Save items in a key-indexed table. Index is a function of the key. Goal: scramble the keys.
! Efficiently computable.
Hash function. Method for computing table index from key. ! Each table position equally likely for each key.
thoroughly researched problem
Collision resolution strategy. Algorithm and data structure to handle
two keys that hash to the same index. Ex: Social Security numbers.
! Bad: first three digits. 573 = California, 574 = Alaska

Classic space-time tradeoff. ! Better: last three digits. assigned in chronological order within a
given geographic region
! No space limitation: trivial hash function with key as address.
! No time limitation: trivial collision resolution = sequential search. Ex: date of birth.
! Limitations on both time and space: hashing (the real world). ! Bad: birth year.
! Better: birthday.

Ex: phone numbers.

! Bad: first three digits.
! Better: last three digits.

3 4
 Hash Function: String Keys hashCode

Java string library hash functions. Hash code. For any references x and y:
!Repeated calls to x.hashCode() must return the same value
public int hashCode() { provided no information used in equals comparison has changed.
int hash = 0; s = "call"; !If x.equals(y) then x and y must have the same hash code.
for (int i = 0; i < length(); i++) h = s.hashCode();
hash = (31 * hash) + s[i]; hash = h % M; "consistent with equals"
return hash; 3045982
} ith character of s
7121 8191
Default implementation: memory address of x.
Customized implementations: String, URL, Integer, Date.

! Equivalent to h = 31L-1s0 + . . . + 312sL-3 + 31sL-2 + sL-1.

! Horner's method to hash string of length L: O(L).

Q. Can we reliably use (h % M) as index for table of size M?

A. No. Instead, use (h & 0x7fffffff) % M.

5 6

Implementing HashCode: US Phone Numbers Collisions

Phone numbers: (609) 867-5309. Collision = two keys hashing to same value.
area code exchange extension
! Essentially unavoidable.
! Birthday problem: how many people will have to enter a room until
two have the same birthday? 23
! With M hash values, expect a collision after sqrt(! ! M) insertions.
public final class PhoneNumber {
private final int area, exch, ext;
public PhoneNumber(int area, int exch, int ext) { Conclusion: can't avoid collisions unless
this.area = area;
this.exch = exch; you have a ridiculous amount of memory.
this.ext = ext;
} Challenge: efficiently cope with collisions.
public boolean equals(Object y) { // as before }

public int hashCode() {

return 10007 * (area + 1009 * exch) + ext;
}
}

7 8
 Collision Resolution: Two Approaches. Separate Chaining

Separate chaining. st[0] jocularly seriously Separate chaining: array of M linked lists.
! M much smaller than N. st[1] listen ! Hash: map key to integer i between 0 and M-1.
! " N / M keys per table position. st[2] null ! Insert: put at front of ith chain (if not already there).
! Put keys that collide in a list. st[3] suburban untravelled considerating ! Search: only need to search ith chain.
! Need to search lists. ! Running time: proportional to length of chain.
st[8190] browsing

M = 8191, N = 15000

key hash

Open addressing. st[0] jocularly st[0] jocularly seriously call 7121

!M much larger than N. st[1] seriously

st[1]
me 3480
listen
!Plenty of empty table slots. st[2] listen
ishmael 5017

!When a new key collides, find next st[3] suburban st[2] null seriously 0

empty slot and put it there. st[4]

untravelled 3
null
st[3] suburban untravelled considerating
!Complex collision patterns. suburban 3
st[5] null
. . . .

st[30001] browsing st[8190] browsing M = 8191

M = 30001, N = 15000
9 10

Symbol Table: Separate Chaining Symbol Table: Separate Chaining Implementation (cont)

public class ListHashST<Key, Value> {

private int M = 8191; public void put(Key key, Value val) {
private Node[] st = new Node[M]; int i = hash(key);
for (Node x = st[i]; x != null; x = x.next) {
private static class Node { if (key.equals(x.key)) {
Object key; x.val = val;
no generic array creation in Java
Object val; return; check if key already present
Node next; }
Node(Object key, Object val, Node next) { } insert at front of chain
this.key = key; st[i] = new Node(k, val, st[i]);
this.val = val; }
this.next = next;
}
public Value get(Key key) {
}
int i = hash(k);
for (Node x = st[i]; x != null; x = x.next)
private int hash(Key key) { if (key.equals(x.key))
return (key.hashCode() & 0x7fffffff) % M; return (Value) x.val;
} hex
between 0 and M-1
return null;
}

11 12
 Separate Chaining Performance Symbol Table: Implementations Cost Summary

Separate chaining performance.

! Search cost is proportional to length of chain.
! Trivial: average length = N / M. Worst Case Average Case
! Worst case: all keys hash to same chain. Implementation Search Insert Delete Search Insert Delete
Sorted array log N N N log N N/2 N/2
Theorem. Let # = N / M > 1 be average length of list. For any t > 1,
Unsorted list N N N N/2 N N/2
probability that list length > t # is exponentially small in t.
Separate chaining N N N 1* 1* 1*
depends on hash map being random map
* assumes hash function is random
Parameters.
! M too large $ too many empty chains.
! M too small $ chains too long.
! Typical choice: # = N / M " 10 $ constant-time search/insert. Advantages: fast insertion, fast search.
Disadvantage: hash table has fixed size.
fix: use repeated doubling, and rehash all keys

13 14

Linear Probing Symbol Table: Linear Probing Implementation

Linear probing: array of size M. typically twice as many slots as elements public class ArrayHashST<Key, Val> {
! Hash: map key to integer i between 0 and M-1. private int M = 30001;
private Key[] keys = (Key[]) new Object[M]; no generic array
! Insert: put in slot i if free, if not try i+1, i+2, etc. private Val[] vals = (Val[]) new Object[M]; creation in Java
! Search: search slot i, if occupied but no match, try i+1, i+2, etc.
private int hash(Key key) { // as before }

Cluster. public void put(Key key, Val val) {

int i;
! Contiguous block of items. for (i = hash(key); keys[i] != null; i = (i+1) % M)
! Search through cluster using elementary algorithm for arrays. if (keys[i].equals(key)) break;
keys[i] = key;
vals[i] = val;
}

public Val get(Key key) {

int i;
for (i = hash(key); keys[i] != null; i = (i+1) % M)
if (keys[i].equals(key)) break;
return vals[i];
}
}
ASEARCHINGXMP

15 16
 Linear Probing Performance Symbol Table: Implementations Cost Summary

Linear probing performance.

Insert and search cost depend on length of cluster.
Worst Case Average Case
!

! Trivial: average length of cluster = # = N / M. but elements more likely to

hash to big clusters
! Worst case: all keys hash to same cluster. Implementation Search Insert Delete Search Insert Delete
Sorted array log N N N log N N/2 N/2
Unsorted list N N N N/2 N N/2
Theorem. [Knuth 1962] Let # = N / M < 1 be average length of list. Separate chaining N N N 1* 1* 1*
Linear probing N N N 1* 1* 1*
depends on hash map being * assumes hash function is random
random map

Parameters.
! M too large $ too many empty array entries. Advantages: fast insertion, fast search.
! M too small $ clusters coalesce. Disadvantage: hash table has fixed size.
! Typical choice: M " 2N $ constant-time search/insert. fix: use repeated doubling, and rehash all keys

17 18

Double Hashing Double Hashing Performance

Double hashing. Avoid clustering by using second hash to compute skip Linear probing performance.
for search. ! Insert and search cost depend on length of cluster.
! Trivial: average length of cluster = # = N / M.
Hash. Map key to integer i between 0 and M-1. ! Worst case: all keys hash to same cluster.
Second hash. Map key to nonzero skip value k.
Theorem. [Guibas-Szemeredi] Let # = N / M < 1 be average length of list.
Ex: k = 1 + (v mod 97).
depends on hash map being
hashCode random map

Parameters.
! M too large $ too many empty array entries.
! M too small $ clusters coalesce.
Result. Skip values give different search paths for keys that collide. ! Typical choice: M " 2N $ constant-time search/insert.

Best practices. Make k and M relatively prime. Disadvantage: delete cumbersome to implement.

19 20
 Hashing Tradeoffs Hash Table: Java Library

Separate chaining vs. linear probing/double hashing. Java has built-in libraries for symbol tables.
! Space for links vs. empty table slots. ! HashMap = linear probing hash table implementation.
! Small table + linked allocation vs. big coherent array.
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args) {
Linear probing vs. double hashing. HashMap<String, String> st = new HashMap <String, String>();
st.put("www.cs.princeton.edu", "128.112.136.11");
st.put("www.princeton.edu", "128.112.128.15");
load factor # System.out.println(st.get("www.cs.princeton.edu"));
}
50% 66% 75% 90% }

linear search 1.5 2.0 3.0 5.5

probing insert 2.5 5.0 8.5 55.5
Duplicate policy.
search 1.4 1.6 1.8 2.6
double ! Java HashMap allows null values.
hashing insert 1.5 2.0 3.0 5.5
! Our implementations forbid null values.

21 22

Symbol Table: Using HashMap Designing a Good Hash Function

Symbol table. Implement our interface using HashMap. Java 1.1 string library hash function.
! For long strings: only examines 8 evenly spaced characters.
! Saves time in performing arithmetic.
! Great potential for bad collision patterns.
import java.util.HashMap;
import java.util.Iterator;

public class ST<Key, Value> implements Iterable<Key> { public int hashCode() {

private HashMap<Key, Value> st = new HashMap<Key, Value>(); int hash = 0;
if (length() < 16) {
public void put(Key key, Value val) { for (int i = 0; i < length(); i++)
if (val == null) st.remove(key); hash = (37 * hash) + s[i];
else st.put(key, val);
}
}
public Value get(Key key) { return st.get(key); } else {
public Value remove(Key key) { return st.remove(key); } int skip = length() / 8;
public boolean contains(Key key) { return st.containsKey(key); } for (int i = 0; i < length(); i += skip)
public int size() contains(Key ke{ return st.size(); } hash = (37 * hash) + s[i];
public Iterator<Key> iterator() { return st.keySet().iterator(); } }
} return hash;
} String.java

23 24
 Algorithmic Complexity Attacks Algorithmic Complexity Attacks

Is the random hash map assumption important in practice? Q. How easy is it to break Java's hashCode with String keys?
! Obvious situations: aircraft control, nuclear reactors. A. Almost trivial: string hashCode is part of Java 1.5 API.
! Surprising situations: denial-of-service attacks. ! Ex: hashCode of "BB" equals hashCode of "Aa".
! Can now create 2N strings of length 2N that all hash to same value!
malicious adversary learns your ad hoc hash function
(e.g., by reading Java API) and causes a big pile-up in
single address that grinds performance to a halt AaAaAaAa BBAaAaAa
AaAaAaBB BBAaAaBB
AaAaBBAa BBAaBBAa
AaAaBBBB BBAaBBBB
Real-world exploits. [Crosby-Wallach 2003] AaBBAaAa BBBBAaAa
AaBBAaBB BBBBAaBB
! Bro server: send carefully chosen packets to DOS the server, using AaBBBBAa BBBBBBAa
less bandwidth than a dial-up modem AaBBBBBB BBBBBBBB
! Perl 5.8.0: insert carefully chosen strings into associative array. Possible to fix?
! Linux 2.4.20 kernel: save files with carefully chosen names. ! Security by obscurity. [not recommended]
Reference: http://www.cs.rice.edu/~scrosby/hash
! Cryptographically secure hash functions.
! Universal hashing.

25 26