Foundations — Load factor — when to resize, rehashing cost

This page assumes you have seen none of the notation on the parent note. We build every symbol, one at a time, each resting on the previous. If you can count and share sweets among friends, you can follow every line.

0. The picture we keep returning to

Before any symbol, hold this image: a row of buckets (think laundry baskets in a corridor), and a pile of keys (think named socks) that must each be dropped into exactly one basket by a rule.

Everything below is a label for something in this picture.

1. $n$ — the number of keys stored

If you insert one more key, $n$ goes up by one. If you delete one, $n$ goes down by one. Nothing subtle — but every later formula uses this letter, so we name it first.

2. $m$ — the number of buckets (slots)

3. The division bar and $\alpha =n/m$ — the load factor

We have a count of stuff ($n$) and a count of space ($m$). The natural question "how crowded?" is answered by dividing one by the other.

Why the topic needs $\alpha$: it is the single dial the whole page turns. Small $\alpha$ = fast + wasteful; large $\alpha$ = cramped + slow. Resizing is nothing but keeping this one number in a safe range.

4. The hash function $h(k)$ and $\mathrm{mod}$

How does a key know which bucket to enter? A hash function decides.

But $h(k)$ might print a number bigger than the number of baskets you own. We fix that with the modulo operation.

5. A collision

6. $O(\cdot )$ — Big-O, the "how does cost grow" notation

The parent note keeps writing $O(1)$, $O(\alpha )$, $O(n)$, $O(n^2)$. This is not multiplication — it is a way of describing how work scales.

7. Expected value $\mathbb{E}[\cdot ]$ and "average"

The parent writes $\mathbb{E}[\text{cost}]$. This just means average, weighted by how likely each case is.

8. The geometric series $1+\alpha +{\alpha }^2+\cdots$

The parent derives two results from the same mathematical fact: adding up a shrinking chain of powers.

9. Summation sign $\sum$

10. Amortized cost

How the foundations feed the topic

Trace any arrow: no box is used before the boxes feeding it were defined above. That is the whole promise of this page.

Equipment checklist

Cover the right side; say your answer aloud before revealing.

Ready? Then head back to the parent topic (or its English version) and every symbol will already be an old friend. See also Hashing and Dynamic Arrays for where doubling first appears.