Chapter map

Where this sits in CS 300. Until now, lookup costs $O(n)$ (linear search) or $O(\log n)$ (binary search, balanced trees). Chapter 5 introduces hashing, the technique that takes lookup on average down to $O(1)$ . The catch is everywhere: bad hash functions, full tables, adversarial inputs, and resizing. Mastering hash tables is mastering the tradeoffs that make $O(1)$ possible.

What you add to your toolkit here:

Hash function as a deterministic $key \to index$ map, with the requirements (fast, well-distributed, deterministic).
Collision resolution: chaining (buckets are linked lists) vs. open addressing (linear / quadratic probing, double hashing).
Load factor $\alpha = n / \text{capacity}$ : the single number that predicts whether your table is fast or sad.
Resizing (rehashing) as the mechanism that keeps amortized $O(1)$ honest.
Direct hashing — the degenerate case where keys are indices. Works when the key space is dense and small.
Cryptographic hashing — same mathematical object, entirely different requirements (collision resistance, preimage resistance, slowness). Don’t confuse the two.

Mastery checklist — you should be able to, without references:

Define a hash function and state the three desiderata (fast, deterministic, uniform).
Given a key stream, draw the resulting table under chaining AND under linear probing, starting from capacity 7.
State the expected cost of insert/find/remove under chaining and under open addressing, and say what happens as $\alpha$ approaches 1.
Compute the mid-square or multiplication-method hash of a concrete key by hand.
Explain primary clustering (linear probing) and secondary clustering (quadratic probing) and how double hashing escapes both.
Describe the rehash procedure: when it triggers, what the new capacity is, and why you can’t just copy the old table — you must rehash every element.
Say why std::unordered_map uses chaining (not open addressing) and what that buys vs. costs.
Distinguish cryptographic and data-structure hashing, and name one attack (e.g., hash flooding) that bridges them.

Looking ahead. Hash tables will show up in graph algorithms as “visited” sets (opt. ch. 10), in DP as memoization tables, and as the default map container in every production C++ codebase (std::unordered_map). Chapter 6 (BSTs) gives you the ordered alternative — slower on average, but with guarantees hash tables lack.

5.1 Hash Tables: The Big Idea

Every data structure you’ve seen so far has been one of two shapes: a list (search costs $O(n)$ ) or a sorted array (search costs $O(\log n)$ ). A hash table does something radically different. Instead of searching for a key, it computes where the key should live. Search, insert, and remove become $O(1)$ on average --- constant time, regardless of how many items are stored.

Hash tables implement the Set ADT

Recall the Sequence-vs-Set framing from : every container belongs to one of two interface families. Sequence keeps items at caller-chosen positions ( $i = 0, 1, \ldots, n-1$ ); Set keeps items at positions chosen by the data structure itself, looked up by an intrinsic key. ch. 4 built Sequence implementations (lists, stacks, queues, deques). This chapter and ch. 6 build Set implementations.

A hash table is a Set: the operations are find(k), insert(x), delete(k) --- never “insert at position $i$ ” or “the third item.” In C++:

std::unordered_set<K> --- the bare Set: “is key $k$ present?”
std::unordered_map<K,V> --- a dictionary (Set without the ordered ops, in OCW terminology): “what value is associated with key $k$ ?”

ch. 5 covers the chained and open-addressed implementations of the Set interface. covers the special case where keys are small integers and the hash function is the identity --- the trivial Set implementation. ch. 6 covers BSTs, the alternative Set implementation that gives up O(1) lookup in exchange for ordered operations (find_min, find_next(k)).

The core trick

Suppose you have an array of size 10 and you want to store the key 25. Where does it go?

index = 25 % 10 = 5

Store it at array[5]. To look it up later: compute the same index, read that slot. No search. No comparison loop. The work of “finding” has been replaced by a calculation that locates the element directly.

Three lines, $O(1)$ in both operations. This is the entire idea. Everything else in this chapter --- hash functions, collisions, chaining, probing, load factor --- is about making this trick actually work in practice when keys don’t divide up so neatly.

Why not just use a giant array?

If keys are small integers, you already can. An array of size $2^{32}$ indexed directly by int keys works --- but that’s 16 GB of memory to hold possibly a handful of values. Hash tables compress a large potential key space into a small array, trading perfect placement for practical memory use.

::: center Approach Lookup Space

Direct array (key = index) $O(1)$ $O(K)$ where K = key range Sorted array + binary search $O(\log n)$ $O(n)$ Linked list $O(n)$ $O(n)$ Hash table $O(1)^*$ $O(n)$ :::

$^*$ average case; worst case can degrade, see later sections.

The hash table gets you array-speed lookup at list-space cost. That combination is so valuable that hash tables are the backbone of almost every real-world fast key-value store: JavaScript objects, Python dicts, Java HashMap, Redis, DNS caches, database indexes (sometimes), compiler symbol tables, the list goes on.

Vocabulary

::: center Term Meaning

Key The value used to look up an item Value The data associated with the key (often absent --- just a set) Bucket A slot in the underlying array Hash function key $\to$ bucket index Collision Two keys that hash to the same bucket Load factor $n$ items / $m$ buckets --- a density measure :::

5.2 Chaining

Chaining is the first collision-resolution strategy. The idea is almost embarrassingly simple: if two keys want the same bucket, don’t pick a winner --- let both live there, in a list.

The mental model

Picture the hash table as an array of list heads instead of an array of values. Each slot is either nullptr (empty) or points to a chain of nodes that all hashed to that index.

::: center Bucket Chain

0 nullptr 1 21 $\to$ 31 $\to$ 51 2 nullptr 3 13 4 24 $\to$ 74 :::

Every chain only contains keys that hashed to that index, so the search step only compares against “nearby” items --- ideally just one or two, not the entire table.

Algorithms

Each of the three operations becomes: (1) hash the key to find the bucket, (2) do the list-level operation on that bucket’s chain.

Chained hash table operations

template <typename T>
class ChainedHashTable {
    struct Node { T data; Node* next; };
    std::vector<Node*> table;
    size_t n_ = 0;

    size_t hash(const Key& k) const {
        return std::hash<Key>{}(k) % table.size();
    }

public:
    explicit ChainedHashTable(size_t m) : table(m, nullptr) {}

    bool contains(const Key& k) const {
        for (Node* p = table[hash(k)]; p; p = p->next)
            if (p->data.key == k) return true;
        return false;
    }

    void insert(const T& item) {
        size_t b = hash(item.key);
        for (Node* p = table[b]; p; p = p->next)
            if (p->data.key == item.key) { p->data = item; return; }
        table[b] = new Node{item, table[b]};  // prepend
        ++n_;
    }

    bool remove(const Key& k) {
        size_t b = hash(k);
        Node** cur = &table[b];
        while (*cur) {
            if ((*cur)->data.key == k) {
                Node* dead = *cur;
                *cur = dead->next;
                delete dead;
                --n_;
                return true;
            }
            cur = &(*cur)->next;
        }
        return false;
    }
};

Two implementation notes: insert checks for duplicates first because most hash-table APIs are “unique-key” (insert acts as upsert), and remove uses the Node** trick from chapter 4 so the same code handles head and interior removal without a special case.

Cost

::: center Operation Average Worst Notes

insert $O(1 + \alpha)$ $O(n)$ Chain walk to check duplicate contains $O(1 + \alpha)$ $O(n)$ Chain walk to compare keys remove $O(1 + \alpha)$ $O(n)$ Chain walk to locate node :::

$\alpha = n/m$ = load factor = average chain length. When $\alpha$ is a small constant (say, $\leq 1$ ), every operation is effectively $O(1)$ . When $\alpha$ grows, operations slow linearly. Section 5.6 discusses how to keep $\alpha$ bounded by resizing.

Pros and cons

::: center

Pro Never fills up --- you can keep inserting past the table size, chains just grow longer. Pro Removal is easy --- just unsplice a list node. Pro High load factors tolerable (still works at $\alpha > 1$ ). Con Extra memory per item (one next pointer per node). Con Cache-unfriendly --- chain walks follow pointers all over the heap, same as plain linked lists. Con Extra allocation on every insert (one new Node).

:::

Why $O(1+\alpha)$? The simple uniform hashing assumption

The cost claim “find takes $O(1+\alpha)$ on average” isn’t a slogan; it’s a theorem (CLRS Ch 11.2, Theorems 11.1—11.2). The proof rests on one assumption:

Simple uniform hashing. Any given key is equally likely to hash to any of the $m$ slots, independently of where any other key has hashed.

Under this assumption, the expected length of bucket $T[h(k)]$ is $E[n_{h(k)}] = n/m = \alpha$ . So an unsuccessful search examines $\alpha$ elements on average, plus $O(1)$ to compute the hash and index --- total $\Theta(1 + \alpha)$ . A symmetric argument (with slightly more bookkeeping for the “which list is searched” probability) gives the same $\Theta(1 + \alpha)$ bound for successful search.

Two consequences worth internalizing:

If you keep $\alpha$ bounded by a constant (which is what resizing in does), the $1 + \alpha$ term is $O(1)$ . This is the entire reason hash tables average $O(1)$ .
The open-addressing variants in — all use the same simple-uniform-hashing assumption. Their per-strategy cost formulas (linear’s $\frac{1}{2}(1 + 1/(1-\alpha))$ , double-hashing’s tighter bounds) come from analyzing different probe sequences under that same assumption.

The assumption is strong --- real hash functions don’t perfectly satisfy it on all inputs. shows what hash functions try to do to approximate it; (universal hashing subsection) shows how to make a probabilistic guarantee without the assumption at all.

5.3 Linear Probing

Linear probing is the first flavor of open addressing --- the “stay inside the array” approach to collisions. When the computed bucket is occupied, walk forward through the array one slot at a time until you find an empty one. That’s it. Simple to describe, surprisingly subtle to get right.

Why it’s interesting

Chaining (5.2) allocates a new node per item. Linear probing does not --- every item lives in the fixed array itself.

::: center Aspect Chaining Linear probing

Extra memory per item 1 pointer 0 Allocations on insert 1 new Node 0 Cache behavior Poor (heap jumps) Excellent (contiguous) Can overflow? Never Yes (array full $\Rightarrow$ insert fails) Removal Unsplice list node Tombstone (see below) :::

For small-to-medium tables, linear probing typically wins on real hardware: no allocation, no pointer chasing, and the CPU prefetches the next probe slot because it’s literally the next cache line. This is why many high-performance hash tables (Google’s dense_hash_map, Robin Hood hashing, Swiss tables) are built on open addressing rather than chaining.

Insert

Linear-probe insert

bool insert(int key) {
    size_t start = hash(key) % N;
    for (size_t i = 0; i < N; ++i) {
        size_t b = (start + i) % N;
        if (table[b].state != OCCUPIED) {
            table[b] = { key, OCCUPIED };
            return true;
        }
        if (table[b].key == key) return false; // duplicate
    }
    return false;  // table full
}

The % N wrap makes the probe sequence circular --- if you hit the end of the array, you keep going from index 0.

The tombstone problem

Removal on an open-addressed table is not just “mark the bucket empty.” Consider:

Insert 25 (bucket 5).
Insert 35 (bucket 5 occupied, probe to 6).
Remove 25 --- mark bucket 5 empty.
Search for 35 --- check bucket 5, find it empty, stop searching. Returns “not found.” But 35 is there, in bucket 6.

To fix this, open-addressed tables distinguish two kinds of empty:

::: center State Meaning

EMPTY_SINCE_START Never held an item; search can stop here OCCUPIED Currently holds an item EMPTY_AFTER_REMOVAL (tombstone) Was occupied; search continues past :::

The tombstone preserves the “I was here” information that the probe sequence needs. Insertions treat tombstones as empty (can reuse the slot). Searches treat tombstones as occupied (keep probing past).

Linear-probe search

int* find(int key) {
    size_t start = hash(key) % N;
    for (size_t i = 0; i < N; ++i) {
        size_t b = (start + i) % N;
        if (table[b].state == EMPTY_SINCE_START) return nullptr;
        if (table[b].state == OCCUPIED && table[b].key == key)
            return &table[b].key;
        // tombstone: keep looking
    }
    return nullptr;
}

The three termination conditions matter: (1) found a match, return it; (2) hit a never-occupied slot, definitely not present; (3) probed every bucket, not present.

Cost and load factor

Linear probing’s cost depends dramatically on how full the table is. Let $\alpha = n/m$ (load factor).

::: center Load factor $\alpha$ Avg probes (successful) Feel

0.5 $\approx 1.5$ Fast 0.75 $\approx 2.5$ Still OK 0.9 $\approx 5.5$ Getting sluggish 0.95 $\approx 10.5$ Noticeable 0.99 $\approx 50$ Disaster :::

These numbers aren’t linear in $\alpha$ --- they grow like $\frac{1}{1 - \alpha}$ (Knuth’s analysis). That’s why open- addressed tables typically enforce a much lower max load factor than chained ones: 0.5—0.75 is common for linear probing versus 1.0+ for chaining.

5.4 Quadratic Probing

Linear probing’s flaw, remember, is primary clustering: once a run of occupied buckets forms, any key that hashes into that run lengthens it, snowballing the problem. Quadratic probing sidesteps clustering by using a probe sequence whose gaps grow with each step.

The probe pattern

With $c_1 = 0, c_2 = 1$ (the simplest common choice), the probe sequence from a starting bucket $h$ visits:

::: center $i$ Offset $i^2$ Bucket

0 0 $h$ 1 1 $h+1$ 2 4 $h+4$ 3 9 $h+9$ 4 16 $h+16$ :::

The gaps grow: 1, 3, 5, 7, 9, …The probe sequence jumps past nearby occupied slots quickly, so even if there’s a cluster starting near $h$ , it gets skipped over rather than extended.

Quadratic-probe insert

bool insert(int key) {
    size_t h = hash(key);
    for (size_t i = 0; i < N; ++i) {
        size_t b = (h + c1 * i + c2 * i * i) % N;
        if (table[b].state != OCCUPIED) {
            table[b] = { key, OCCUPIED };
            return true;
        }
        if (table[b].key == key) return false; // duplicate
    }
    return false;  // full or unreachable
}

Everything else (tombstones, search, remove) carries over from linear probing. The only change is the probe-step formula.

Primary clustering: solved. Secondary clustering: new problem

Quadratic probing eliminates primary clustering (adjacent keys no longer share probe paths). But two keys that hash to the same starting bucket will still follow the exact same probe sequence --- that’s secondary clustering. Less severe than primary, but not gone.

::: center Strategy Primary clustering Secondary clustering

Linear probing Yes Yes Quadratic probing No Yes Double hashing (5.5) No No :::

Choosing constants

$c_1 = 0, c_2 = 1$ gives you $h + i^2$ , which has the guarantee above. $c_1 = 1, c_2 = 1$ gives $h + i + i^2$ , which is the form used in the textbook pseudocode; it still works but the theoretical guarantees depend on specific $N$ values. When in doubt, prefer the simpler $h + i^2$ version with prime table sizes.

Cost

::: center Load factor $\alpha$ Avg probes (successful) Notes

0.5 $\approx 1.4$ Slightly better than linear at 0.5 0.75 $\approx 2.0$ Noticeably better 0.9 $\approx 3.2$ Much better than linear’s 5.5 :::

At high load factors, quadratic probing substantially outperforms linear probing. At low load factors, the difference is minor and linear’s cache-friendliness can win on wall-clock time.

5.5 Double Hashing

Linear and quadratic probing both suffer secondary clustering: any two keys that hash to the same starting bucket follow the same probe sequence. Double hashing fixes this by making the probe step size also depend on the key --- so two keys starting at the same bucket diverge immediately.

The idea, geometrically

Think of each key as having its own “rhythm” for walking through the table. Linear probing: everyone steps by 1. Quadratic: everyone’s step pattern is $1, 4, 9, \ldots$ . Double hashing: each key’s step depends on the key itself.

Two keys can collide on their starting bucket and still separate instantly because their $h_2$ values differ. That’s the whole trick.

Example

Let $m = 11$ , $h_1(k) = k \bmod 11$ , $h_2(k) = 5 - (k \bmod 5)$ .

::: center Key $k$ $h_1(k)$ $h_2(k)$ Probe sequence

55 0 5 0, 5, 10, 4, 9, 3, … 66 0 4 0, 4, 8, 1, 5, … :::

Both keys start at bucket 0, but after the first collision they walk in entirely different directions. That’s why double hashing approximates “uniform hashing” --- the theoretical ideal where every key’s probe sequence is a random permutation of buckets.

Implementation

Double-hashing insert

bool insert(int key) {
    size_t h1 = hash1(key) % N;
    size_t h2 = hash2(key);   // must be nonzero, coprime to N
    for (size_t i = 0; i < N; ++i) {
        size_t b = (h1 + i * h2) % N;
        if (table[b].state != OCCUPIED) {
            table[b] = { key, OCCUPIED };
            return true;
        }
        if (table[b].key == key) return false; // duplicate
    }
    return false;  // table full
}

Search and remove use the same probe formula with the usual tombstone rules. The only new concern is choosing $h_2$ correctly.

The h_2 requirement: never zero, always coprime to m

If $h_2(k) = 0$ , the probe sequence stays stuck at $h_1(k)$ forever --- infinite loop. Always enforce $h_2(k) \neq 0$ .

If $h_2(k)$ shares a factor with $m$ (table size), the probe sequence visits only a subset of buckets --- you can fail to insert even with empty buckets available. The standard fix: make $m$ a prime and design $h_2$ to always return a value in $[1, m-1]$ . A common construction:

$h_2(k) = p - (k \bmod p), \text{ where } p < m \text{ is prime}$

This guarantees $1 \leq h_2(k) \leq p < m$ , and since $m$ is prime, $\gcd(h_2(k), m) = 1$ always.

Cost

::: center Load factor $\alpha$ Avg probes (successful) Notes

0.5 $\approx 1.4$ Matches quadratic 0.75 $\approx 1.8$ Better than quadratic 0.9 $\approx 2.6$ Significantly better 0.95 $\approx 3.2$ Holds up where others collapse :::

The cost formula is $\frac{1}{\alpha} \ln \frac{1}{1-\alpha}$ — essentially the theoretical best achievable by any open- addressing scheme. Double hashing’s probe distribution is statistically close to uniform random, which is what the analysis assumes.

::: center Strategy Primary clusters? Secondary clusters? Cache-friendly?

Chaining --- --- No Linear probing Yes Yes Yes Quadratic probing No Yes Somewhat Double hashing No No No :::

5.6 Hash Table Resizing

Every cost analysis so far has assumed the load factor stays bounded. But the user keeps inserting, and $n$ keeps growing. Without intervention, $\alpha = n/m$ climbs past 0.5, 0.75, 0.9, and eventually the table fills up. Resizing is how hash tables bound their load factor at runtime.

The algorithm

Decide a new size $m'$ . Commonly $m' \approx 2m$ , rounded up to the next prime.
Allocate a fresh array of size $m'$ , all slots empty.
For each non-empty bucket in the old table, re-compute $h(key) \bmod m'$ (note: not $\bmod m$ ) and insert into the new table.
Free the old array. Swap the pointer.

Resize

void resize(size_t newCap) {
    std::vector<Slot> oldTable = std::move(table);
    table.assign(newCap, Slot{});   // all EMPTY_SINCE_START
    n_ = 0;
    for (const Slot& s : oldTable) {
        if (s.state == OCCUPIED) insert(s.key);
    }
}

The old bucket indices are meaningless for the new table. Every item must be re-hashed from scratch. This is why the operation is $O(n)$ rather than “just copy the array.”

When to resize

Three common triggers:

::: center Trigger When Typical threshold

Load factor $\alpha \geq t$ 0.5—0.75 (open addr); 1.0+ (chaining) Chain length (chaining) longest chain $\geq k$ 4—8 Probe count (open addr) probes $\geq k$ $N/3$ or similar :::

Load factor is the standard trigger because it’s cheap to check (just compare n_ / m to the threshold after each insert). The other triggers are more responsive to pathological cases --- a few really-bad buckets can justify resizing even if $\alpha$ looks okay.

Growth factor: why doubling?

Suppose you grow by adding a fixed amount ( $m' = m + c$ ) each time. Inserting $n$ items triggers $n/c$ resizes, each $O(n)$ on average, so total work is $O(n^2 / c) = O(n^2)$ . Back to amortized $O(n)$ per insert on average --- a disaster.

With $m' = 2m$ (doubling), you resize $O(\log n)$ times over the life of the table. Each resize $i$ rehashes roughly $2^i$ items. Total rehash work: $1 + 2 + 4 + \ldots + n \approx 2n = O(n)$ . Amortized $O(1)$ per insert.

Why prime sizes?

If table size $m$ has small factors, keys that share those factors will cluster. Example: $m = 10$ and keys are even. Every even key hashes to an even bucket; half the table is wasted.

Prime sizes avoid this: $\gcd(\text{key}, m) = 1$ for most keys, so the modulo spreads them uniformly regardless of key structure. Doubling to the next prime ( $m = 11 \to 23 \to 47 \to 97$ ) is a common implementation choice.

Shrink?

Most implementations never shrink automatically. Why:

Shrinking and regrowing in a tight loop of inserts and removes would thrash.
The memory “wasted” by a half-empty table is usually cheap compared to the cost of a resize.
If the user really wants to reclaim memory, they can call rehash(n) or move into a fresh table explicitly.

std::unordered_map has rehash(n) and reserve(n) but no auto-shrink. std::vector has shrink_to_fit() but it’s still a manual request.

5.7 Common Hash Functions

Every hash table so far has assumed a hash function that “maps keys to buckets uniformly.” This section finally makes that concrete: what does a good hash function look like, and what can go wrong?

Modulo: the simplest, surprisingly subtle

$h(k) = k \bmod m$ is the textbook default.

When does it fail? When the keys share a factor with $m$ . If keys are always even and $m$ is even, odd buckets are never used. If $m = 10$ and keys are 10, 20, 30, 40, every one hashes to bucket 0. This is exactly why prime table sizes are recommended: $\gcd(\text{key}, m)$ is almost always 1, so the modulo spreads the keys out regardless of structure.

Mid-square

Square the key, extract the middle bits. The idea: squaring mixes every bit of the key into the middle of the result, so the middle bits depend on the entire key.

Mid-square hash (binary)

size_t hashMidSquare(uint32_t key, size_t m) {
    uint64_t sq   = uint64_t(key) * key;
    size_t   r    = 10;                   // bits to extract
    size_t   drop = (64 - r) / 2;
    uint64_t mid  = (sq >> drop) & ((1ULL << r) - 1);
    return mid % m;
}

Mid-square is a historical curiosity now --- multiplicative hashing (below) dominates for integer keys --- but it’s a useful illustration of the general technique: mix the bits, then take a slice.

Multiplicative hashing for strings

For string keys, you can’t just take a single character and modulo. You need a function that combines every character into a single hash.

The idea: iteratively fold each character into a running hash by multiplying and adding. The multiplier (33) and seed (5381) are chosen so that small changes in the input produce large changes in the hash --- an informal avalanche property.

Variants:

djb2 XOR: h = h * 33 ^ c --- marginally better distribution
sdbm: h = c + (h << 6) + (h << 16) - h --- good for text
FNV-1a: iterative XOR-then-multiply --- widely used
CityHash, FarmHash, xxHash: modern, SIMD-accelerated, extremely fast

What makes a hash function “good”?

::: center Property Meaning

Determinism Same input $\Rightarrow$ same output, always Uniform distribution Each bucket receives roughly $n/m$ keys Avalanche Flipping one input bit flips about half the output bits Cheap A single arithmetic operation plus modulo, ideally Non-trivial Doesn’t fall into obvious traps (e.g., identity function) :::

“Cryptographic strength” is usually not required. SHA-256 is a good hash function for ensuring data integrity, but terrible for hash tables (thousands of cycles per call). Hash table hash functions need speed over security.

C++: std::hash

C++ provides std::hash<T> for the standard types: ints, pointers, strings, and enums. You can specialize it for your own types by defining std::hash<YourType> in the std namespace, or supply a custom hasher as a template parameter to the unordered container.

Custom hasher

struct Point { int x, y; };

struct PointHash {
    size_t operator()(const Point& p) const noexcept {
        // combine two hashes --- the standard "boost::hash_combine" pattern
        size_t h1 = std::hash<int>{}(p.x);
        size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 + 0x9e3779b9 + (h1 << 6) + (h1 >> 2));
    }
};

std::unordered_set<Point, PointHash> points;

The magic number 0x9e3779b9 is $\frac{2^{32}}{\phi}$ ( $\phi$ = golden ratio) --- a widely-used bit-mixing constant that gives good distribution across field combinations. Boost’s hash_combine uses this; many custom hashers copy the idiom.

Universal hashing: the principled defense against adversarial input

The hash randomization notebox above is a practical sketch; the underlying theory is universal hashing, due to Carter and Wegman (1979). It is the standard answer to “what if my hash function’s worst-case input shows up?” --- a question every fixed hash function leaves dangling.

The motivation is the gap between average-case and worst-case for any single hash function. Pick any fixed $h$ and an adversary can find $n$ keys that all hash to the same bucket, giving $\Theta(n)$ chains. Universal hashing escapes this by randomizing the function itself at the start of execution: the adversary picks the keys, but the program picks the hash function independently and after the keys are chosen, so worst-case inputs no longer exist for any particular run.

The $h_{a,b}$ family from CLRS Ch 11.3.3

// Universal hash family h_{a,b}(k) = ((a*k + b) mod p) mod m
// where p > u (universe size) is a fixed prime, and a, b are
// chosen at random at startup with a in [1, p-1], b in [0, p-1].

struct UniversalHash {
    uint64_t a, b;
    uint64_t p;            // prime > universe size
    size_t   m;            // table size

    UniversalHash(size_t table_size, uint64_t prime) : p(prime), m(table_size) {
        std::mt19937_64 rng(std::random_device{}());
        a = 1 + rng() % (p - 1);   // a in [1, p-1], nonzero
        b =     rng() %  p;        // b in [0, p-1]
    }

    size_t operator()(uint64_t k) const {
        return ((a * k + b) % p) % m;
    }
};

Why universal hashing implies short chains

The expected chain length at $h(k)$ is now bounded by $1 + \alpha$ regardless of the keys. Sketch (CLRS Theorem 11.3, OCW lec4): for each pair $k, l$ of distinct keys, define indicator $X_{kl} = \mathbf{1}[h(k) = h(l)]$ . By the universality condition, $E[X_{kl}] = \Pr[h(k)=h(l)] \leq 1/m$ . The number of keys colliding with $k$ is $Y_k = \sum_{l \neq k} X_{kl}$ , so by linearity of expectation, $E[Y_k] \;=\; \sum_{l \neq k} E[X_{kl}] \;\leq\; \sum_{l \neq k} \tfrac{1}{m} \;\leq\; \tfrac{n-1}{m} \;\leq\; \alpha.$ The expected length of the bucket containing $k$ is $E[Y_k] + 1 \leq 1 + \alpha$ . The same bound as simple uniform hashing, but now it follows from the algorithm’s randomness, not from an assumption about the input.

5.8 Direct Hashing

Direct hashing is the degenerate case: use the key itself as the bucket index. No modulo, no mixing, no collisions. Whenever it’s feasible, it’s the fastest possible hash table. Unfortunately, it’s rarely feasible.

When it works

Direct hashing requires every potential key to have a reserved slot. If your keys are integers in $[0, K)$ , you need a table of size $K$ .

Direct-access table

// Suitable only when keys are small non-negative integers.
constexpr size_t K = 10000;
std::optional<Item> table[K];

void insert(const Item& it)   { table[it.key] = it; }
void remove(int key)          { table[key].reset(); }
Item* find(int key) {
    return table[key] ? &*table[key] : nullptr;
}

Three lines per operation, all $O(1)$ worst case --- not average. No hash function to compute, no collision handling, no resizing.

The two killer limitations

::: center Limit Consequence

Keys must be small non-negative integers Can’t directly handle strings, negative numbers, or large key spaces Table size = max key + 1 A key space of $2^{32}$ needs a 4-billion-slot array (16 GB if each slot is 4 bytes, more if you store anything bigger) :::

If the key space is dense --- say, student IDs 0—9999 and you have 8000 active students --- direct hashing is perfect: a 10,000-slot array, 80% utilized, all operations $O(1)$ with zero overhead.

If the key space is sparse --- say, US social security numbers (9 digits, $10^9$ possible values) but your table has a few thousand people --- direct hashing wastes 99.9999% of the array. You need a regular hash table.

Where direct hashing actually shows up

Don’t dismiss it as purely theoretical. Small-keyspace direct access tables are genuinely common:

ASCII character lookup tables (256 slots) --- tokenizer tables, character-class tests (isalnum, isspace)
Byte-to-hex conversion (256 slots holding two-character strings)
Color palettes in graphics (indexed color: the “hash” is just the palette index)
File descriptor tables in OS kernels (fd is already an array index)
CPU register mapping in compilers (register number $\to$ allocation info)
Symbol tables in assemblers when symbol IDs are sequential

Every one of these uses direct indexing by design because the key space is small and dense.

Comparison

::: center Strategy Worst case Collisions? Space

Direct hashing $O(1)$ None $O(K)$ (key range) Chaining $O(n)$ Handled $O(n + m)$ Open addressing $O(n)$ Handled $O(m)$ :::

Direct hashing trades space for time: you pay for a slot for every possible key, but you get the best possible access time. Regular hash tables reverse the deal: save memory, accept occasional collision handling.

5.9 Hashing for Cryptography

Hashing has a second life outside data structures: as a cryptographic primitive. Cryptographic hash functions share the “deterministic function from input to fixed-size output” shape with hash-table functions, but their design goals --- and their cost --- are radically different.

What “infeasible” means

A good cryptographic hash with an $n$ -bit output requires approximately $2^n$ work to find a pre-image and $2^{n/2}$ work to find a collision (the birthday bound). For $n = 256$ , that is $\approx 10^{77}$ operations --- more than the age of the universe on all the computers ever built.

Compare this to a hash-table hash function like djb2. djb2 is fast (a few nanoseconds per byte) but trivially easy to reverse or collide on demand. It’s not secure; it was never designed to be.

::: center Goal Hash-table hash Cryptographic hash

Speed $\leq$ 1 ns/byte 1—10 ns/byte (SHA-256) Output size 32—64 bits 128—512 bits Reversibility Often easy Infeasible Collisions Acceptable (handled) Infeasible to produce Use cases Lookups Integrity, signatures, passwords :::

Data integrity

Download a file plus its hash. Recompute the hash locally. If they match, the file wasn’t corrupted or tampered with.

Verifying a download with SHA-256

$ sha256sum ubuntu-24.04.iso
c37f6b0e...  ubuntu-24.04.iso

# Compare against the published hash on ubuntu.com.
# Match   -> bits are correct
# Mismatch -> file is corrupt or modified

Historical timeline of algorithms:

MD5 (1991): 128-bit output. Collision attacks demonstrated in 2004; broken, do not use for security.
SHA-1 (1995): 160-bit output. Collision demonstrated in 2017 (SHAttered); deprecated.
SHA-256 / SHA-3: current standards. 256—512 bit outputs, no known attacks faster than brute force.

Password hashing

When a user signs up, don’t store their password. Store hash(password). At login, hash the submitted password and compare. If the database is stolen, attackers have hashes, not passwords --- and with a good hash, inverting them is infeasible.

Naive password hashing (don't do this)

stored = sha256(password)   // bad

Two attacks on naive password hashing:

Rainbow tables: attackers precompute hashes for billions of common passwords. If your hash is in the table, password recovered instantly.
Bulk cracking: modern GPUs compute billions of SHA-256 hashes per second. For short or weak passwords, brute force is tractable.

The two standard defenses:

::: center Defense What it does

Salt Append a random per-user value before hashing. Forces the attacker to recompute the rainbow table for every user --- no more precomputation. Slow hash Use a deliberately expensive function (bcrypt, scrypt, Argon2) that takes 100ms—1s per hash. Kills bulk cracking: a million-password attack now takes 12 CPU-days instead of a second. :::

bcrypt, scrypt, and Argon2 are the current standards. Argon2 won the Password Hashing Competition in 2015 and is the recommended default for new systems.

Where else does cryptographic hashing show up?

Digital signatures: sign the hash of the document, not the document itself. Cheaper, and works for any size.
Blockchain / content addressing: each block references the hash of the previous block. Git does the same with commits.
Merkle trees: hash-based structures that let you verify membership in a large set without downloading the whole set.
HMAC: keyed hash functions used to authenticate messages.
Commitment schemes: hash now, reveal later --- used in auctions, coin-flipping protocols, etc.

What this connects to

Forward links to later chapters

Chapter 6 (BSTs). BSTs give you a sorted alternative to hash tables. Choose BST (ordered set, range queries) vs. hash (fastest point lookup) — the tradeoff is on the exam.
Graph algorithms (opt. ch. 10). “Visited” sets in BFS / DFS are hash sets; Dijkstra’s “distance” lookup is a hash map; hashing keeps graph traversal at expected $O(V + E)$ .
Dynamic programming memoization. Top-down DP stores already-computed subproblems in a hash map. The efficiency of DP in the average case is a hash-table claim.
C++ production idiom. std::unordered_map<K, V> is chaining; std::map<K, V> is a red-black tree (ch. 6 territory). Knowing which to pick is a real decision on every CS 300 assignment from here on.
Linked lists from ch. 4 are what chaining buckets are. The node + pointer drills from ch. 4 pay off the moment you trace a chaining collision.

Companion materials. Compact notes: chapters/ch_5/notes.tex. Practice prompts (problem $\to$ pseudocode $\to$ C++): chapters/ch_5/practice.md.