📚 Hash Tables Study Guide

CS210 - Week 13 - Comprehensive Reference

1. Introduction to Hash Tables

What is a Map?

A map is a data structure that models a searchable collection of key-value pairs, where:

• Keys are unique - no duplicate keys allowed
• Each key maps to exactly one value
• Main operations: get(key), put(key, value), remove(key)

2. Hashing: Basic Plan

Core Idea

Save items in a key-indexed table where the index is computed as a function of the key.

The Space-Time Tradeoff

3. Hash Functions

Computing Hash Codes

For Integers

public int hashCode() { 
    return value; 
}

Simply return the integer value itself.

For Booleans

public int hashCode() {
    if (value) return 1231;
    else return 1237;
}

Use two different prime numbers for true and false.

For Doubles

public int hashCode() {
    long bits = doubleToLongBits(value);
    return (int) (bits ^ (bits >>> 32));
}

Convert to 64-bit representation and XOR the two halves.

For Strings (Horner's Method)

public int hashCode() {
    int hash = 0;
    for (int i = 0; i < length(); i++)
        hash = s[i] + (31 * hash);
    return hash;
}

hash = 99·31³ + 97·31² + 108·31 + 108
     = 108 + 31·(108 + 31·(97 + 31·99))
     = 3,045,982

Modular Hashing

Convert hash code (any 32-bit integer) to table index (0 to M-1):

private int hash(Key key) {
    return key.hashCode() % M;
}

private int hash(Key key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

Uniform Hashing Assumption

Birthday Problem & Load Balancing

• Birthday Problem: Expect two balls in same bin after ~√(πM/2) tosses
• Coupon Collector: Expect every bin has ≥1 ball after ~M ln M tosses
• Load Balancing: After M tosses, most loaded bin has Θ(log M / log log M) balls

4. Separate Chaining

How It Works

1. Hash: Map key to integer i between 0 and M-1
2. Insert: Put at front of i^th chain (if not already there)
3. Search: Search only the i^th chain

Array Index          Linked List Chain
    0         →     [A] → [B] → [E] → null
    1         →     null
    2         →     [X] → [S] → null
    3         →     null
    4         →     [L] → [P] → null
    5         →     [M] → [H] → [C] → [R] → null
            

Java Implementation

public class SeparateChainingHashST<Key, Value> {
    private int M = 97;  // number of chains
    private Node[] st = new Node[M];  // array of chains
    
    private static class Node {
        private Object key;
        private Object val;
        private Node next;
    }
    
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public Value get(Key key) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (key.equals(x.key))
                return (Value) x.val;
        return null;
    }
    
    public void put(Key key, Value val) {
        int i = hash(key);
        for (Node x = st[i]; x != null; x = x.next)
            if (keys[i].equals(key)) { 
                x.val = val; 
                return; 
            }
        st[i] = new Node(key, val, st[i]);
    }
}

Performance Analysis

Resizing Strategy

5. Linear Probing

How It Works

1. Hash: Map key to integer i between 0 and M-1
2. Insert: Put at table index i if free; if not, try i+1, i+2, etc.
3. Search: Search table index i; if occupied but no match, try i+1, i+2, etc.

Index:  0   1   2   3   4   5   6   7   8   9   10  11  12  13  14  15
       [P] [M] [ ] [ ] [A] [C] [S] [H] [L] [ ] [E] [ ] [ ] [ ] [R] [X]

Insert K: hash(K) = 5
          Position 5 occupied → try 6 → occupied → try 7 → occupied
          → try 8 → occupied → try 9 → EMPTY! Insert at 9
            

Java Implementation

public class LinearProbingHashST<Key, Value> {
    private int M = 30001;
    private Value[] vals = (Value[]) new Object[M];
    private Key[] keys = (Key[]) new Object[M];
    
    private int hash(Key key) {
        return (key.hashCode() & 0x7fffffff) % M;
    }
    
    public Value get(Key key) {
        for (int i = hash(key); keys[i] != null; i = (i+1) % M)
            if (key.equals(keys[i]))
                return vals[i];
        return null;
    }
    
    public void put(Key key, Value val) {
        int i;
        for (i = hash(key); keys[i] != null; i = (i+1) % M)
            if (keys[i].equals(key))
                break;
        keys[i] = key;
        vals[i] = val;
    }
}

Knuth's Parking Problem

Performance Analysis

Deletion in Linear Probing

Solution: After deletion, must rehash all keys in the same cluster that comes after the deleted key.

6. Performance Comparison

Separate Chaining vs Linear Probing

Complete Symbol Table Implementations Comparison

* Under uniform hashing assumption

7. Advanced Topics

Hash Function Variants

Two-Probe Hashing

Double Hashing

h(x) = h1(x) + j·h2(x)  where j = 0, 1, 2, ...

Cuckoo Hashing

Algorithmic Complexity Attacks

"Aa" and "BB" both hash to 2112
"AaAa", "AaBB", "BBAa", "BBBB" all hash to -540425984
            

One-Way Hash Functions

8. Summary & Best Practices

Best Practices

✅ DO:

• Use prime numbers or powers of 2 for table size M
• Keep load factor α between 0.5 and 0.75 for linear probing
• Keep load factor α around 1-4 for separate chaining
• Implement proper hashCode() that uses all significant fields
• Ensure equals() and hashCode() are consistent
• Resize dynamically to maintain good performance

❌ DON'T:

• Use predictable hash functions in security-critical applications
• Forget to handle the sign bit when converting hash codes to indices
• Directly delete entries in linear probing (must rehash cluster)
• Use hash tables if you need ordered operations (use BST instead)
• Assume uniform hashing without testing your hash function

When to Use What

Common Pitfalls

Quick Reference: Hash Code Implementation

// Template for user-defined types
public int hashCode() {
    int hash = 17;  // nonzero constant
    hash = 31 * hash + field1.hashCode();  // reference type
    hash = 31 * hash + ((Integer) field2).hashCode();  // primitive
    hash = 31 * hash + field3.hashCode();  // reference type
    return hash;
}