Foundations — Chaining — linked lists in buckets, load factor, resizing

Before you can read the parent note Chaining — linked lists in buckets, load factor, resizing, every squiggle it uses has to mean something. This page builds each one from nothing. Read top to bottom; each block only uses ideas from the blocks above it.

1. A "key" $k$ and the "universe" $U$

Picture. Imagine a giant bag holding one ticket for every possible username on Earth. That whole bag is $U$; a single ticket you pull out is a $k$. The tickets you actually saved today are just a handful pulled out of it.

Why the topic needs it. The whole difficulty of hashing comes from one fact: $U$ is enormous (all possible IDs), but your storage is tiny (a small array). We need language to say "far more possible keys than boxes." That is what $U$ (and its members $k$) give us.

2. The array $T$ and its indices $0,1,\dots ,m-1$

Figure 1 (below) shows the row of $m$ cells with their indices. Notice the leftmost cell is labelled $T[0]$.

Why start at 0? Because the hash rule (next sections) will hand us a remainder, and remainders naturally start at 0. In Figure 1 the amber arrow points at cell $T[0]$, not $T[1]$.

Why the topic needs it. The magic of an array is that jumping to cell $i$ takes the same time no matter which $i$ — the computer computes an address by arithmetic and goes straight there. This "instant jump" is the reason hashing can be fast. Walking a list, by contrast, is one-step-at-a-time (see §7).

• $m$ ::: the number of buckets / array slots, a positive integer ($m\in \mathbb{N},m>0$). Read it as "how many boxes on the wall."

3. The symbol $|\cdot |$ and "much greater than" $\gg$

Picture. $|U|\gg m$ is a huge bag of tickets next to a tiny row of $m$ boxes. There is no way each ticket gets its own box.

Why the topic needs it. $|U|\gg m$ is the reason collisions are unavoidable — the seed of the whole Pigeonhole Principle argument. If you have more pigeons ($|U|$) than holes ($m$), some hole gets two pigeons. Hold that thought for §8.

4. The modulo operation $\mathrm{mod}$

Picture. Count around a clock face with $m$ hours. Start at 0 and step forward $a$ times; where you stop is $a\mathrm{mod}m$. A clock is a mod-$m$ machine.

Why the topic needs it. We introduce mod before the hash function because the hash function is built on top of it. It is what squeezes any big integer into the box range $\{0,\dots ,m-1\}$ — and it is why resizing changes where keys go: if $m$ changes from 4 to 8, then $13\mathrm{mod}4=1$ but $13\mathrm{mod}8=5$ — the same value moves boxes. That is the whole point of §"Resizing" in the parent note.

5. From arbitrary keys to integers (feeding the hash)

Picture. Two machines in a row: the first stamps every letter with a numeric barcode; the second folds that barcode onto the clock face of $m$ boxes.

Why the topic needs it. Without this stage the parent note's "$h(k)=k\mathrm{mod}m$" would only ever handle integer keys. For the rest of this page we assume keys are already integers (or already turned into $\text{code}(k)$), so we can write $h(k)=k\mathrm{mod}m$ cleanly. See Hash Functions for how $\text{code}(k)$ is built well.

6. The hash function $h$ as a map, and where collisions come from

Figure 2 (below) draws $h$ as a sorting clerk: you hand it a key, it points to exactly one mailbox. Same key → same box, always. Watch the two amber arrows in Figure 2 — two different keys getting sent to the same box.

Why the topic needs it. $h$ is the "instant jump" rule. Instead of searching, you compute $h(k)$ and land on the right box in one step. Everything else in the parent note is about what to do when two keys land in the same box.

7. Linked lists and the pointer $⇝$ (node arrow)

Figure 3 (below) shows a three-node chain. Follow the cyan node-arrows left to right: to reach the 3rd key you must hop through the 1st and 2nd first.

Picture. Paper clips linking letters into a string. To read the 3rd letter you must clip-walk from the 1st, to the 2nd, to the 3rd — one hop at a time. There is no jumping.

Why the topic needs it. In chaining, each array cell $T[i]$ is a head pointer to one of these chains — the "bucket." Because reading a list is one-hop-at-a-time, the cost of a lookup is how long that chain is. Keeping chains short = keeping lookups fast. See Linked Lists for the full data structure.

8. The Pigeonhole Principle (a picture, not a formula)

Figure 4 (below) shows 5 pigeons forced into 3 holes — one hole must take two.

Here the "pigeons" are all possible keys ($|U|$) and the "holes" are the $m$ boxes. Since $|U|\gg m$ (§3), some box is forced to receive more than one key.

Why the topic needs it. This is the proof that collisions can never be fully avoided — so we don't try. Chaining and Open Addressing are both just answers to "given collisions must happen, how do we cope?" See Pigeonhole Principle.

9. Counting symbols: $n$, expectation $E[\cdot ]$, and the load factor $\alpha$

Picture. Total letters divided by total boxes = the average height of a chain. That average height is what you'll walk through on a lookup — so $\alpha$ is a direct estimate of search cost.

Why the topic needs it. $\alpha$ is the single knob the whole parent note tunes. Small $\alpha$ → short chains → fast. Big $\alpha$ → long chains → slow. Resizing exists purely to keep $\alpha$ from growing.

10. Big-O notation $O(\cdot )$ and "amortized"

Picture. $O(1)$ is a flat line. $O(n)$ is a straight rising line. As the variable doubles, $O(1)$ stays put while $O(n)$ doubles.

Picture. A rent of $1200 paid once a month feels like $40 a day when spread across 30 days. Resizing is the once-a-month big bill; spread over many cheap inserts it averages to $O(1)$. Full treatment in Amortized Analysis; the same trick powers Dynamic Arrays.

Why the topic needs it. Without "amortized," resizing looks like an $O(m)$ disaster on some inserts. Amortized language is what lets us honestly call insert "$O(1)$."

The prerequisite map

Equipment checklist

Cover the right side and answer aloud before revealing.

Connections

• Chaining — linked lists in buckets, load factor, resizing — the topic these foundations feed.
• Hash Functions — how $\text{code}(k)$ and $h$ are actually built; whether SUHA holds.
• Linked Lists — the bucket data structure.
• Pigeonhole Principle — why collisions must happen.
• Open Addressing — the rival collision strategy.
• Amortized Analysis · Dynamic Arrays — the doubling/averaging idea behind resize.