Hash Tables

By the end of this lesson you will be able to build a hash table from scratch by hand — direct addressing, chaining, and open addressing (linear, quadratic, double hashing) — explain why each hash function choice (division, multiplication, universal hashing) matters, compute the exact probe sequence a key follows, and reason about average-case running time using the load factor α. This lesson goes deeper than D08 · Collections Internals, which only sketched how Dart's own Map/Set use hashing — here you implement the machinery yourself.

0. The dictionary problem

A dictionary (in the computer-science sense: a lookup structure, not a list of word meanings) supports three operations: insert a key (and maybe a value attached to it), search for a key, and delete a key. Picture a cloakroom with a million numbered pegs where only 500 coats will ever be checked in. Given a ticket number you want to find, hang or remove the right coat almost instantly — without owning a million physical pegs (one per possible ticket) and without walking past every hung coat.

A plain linked list can act as a dictionary, but search costs Θ(n): you may have to walk the whole list. A sorted array with binary search gets search down to Θ(lg n), but insert and delete cost Θ(n) because elements must shift. A hash table brings all three operations down to O(1) on average — not by magic, but by using a function that computes where a key belongs, so no sequential hunt is needed.

This lesson builds hash tables in stages: direct addressing (perfect, but needs a huge array), chaining (collisions are handled with lists), good hash functions (division, multiplication, universal hashing), open addressing (no lists — everything lives in the array itself) and perfect hashing (worst-case O(1) for fixed key sets). The worst case of ordinary hashing is always Θ(n) — every key could collide — and a large part of the lesson is why that worst case essentially never happens in practice.

1. Direct-address tables

Imagine a hotel with exactly 16 rooms, numbered 0 through 15, and every guest is given the room whose number equals their reservation number (reservation 5 always goes to room 5). No front-desk lookup is needed — the reservation number is the room number. That is direct addressing: if every possible key k in the universe U = {0, 1, ..., m-1} owns a dedicated slot t[k], then storing, finding and removing a key is a single array read or write — O(1), always, no exceptions.

Each slot t[k] either holds the item whose key is k or the empty marker NIL. Three procedures, one line each:

The same three procedures in Dart — t is a plain List, NIL is null:

Input size → what is feasible. Θ(1) per operation, but memory is Θ(|U|): |U| = 10⁶ keys is a 1 MB-class table and fine; keys up to 10⁹ would need 10⁹ slots (several GB) and 64-bit keys are impossible, so switch to hashing (section 2) once |U| ≫ n.

All three operations are Θ(1) in the worst case — there is no chain to walk, no probing, nothing to compare. The catch is big: this only works if the universe U is small enough to allocate an array of size |U|, and you really use a large fraction of those slots. If U is "every possible 64-bit integer" and you store only 500 of them, direct addressing wastes an astronomical amount of memory on empty slots. That gap is exactly what hash tables close.

Three worked examples below: a normal run, an edge-case run (overwriting an occupied slot, deleting a key that was never there, and the two boundary keys 0 and 15), and a box where you type the operations.

Direct addressing needs the key itself to be a small non-negative integer that indexes an array. Real keys are often strings, floating-point numbers or huge IDs. Section 3 shows how to turn a string into a number first (reading its characters as digits in base 128), but no cleverness shrinks a genuinely huge or unbounded universe into a directly addressable array. That is the problem hashing solves.

Direct addressing: O(1) worst case for every operation, but it needs an array of size |U| (every possible key), not just size n (the keys actually stored). Practical only when |U| is small.

Dart implementation

Slot numbers already start at 0, so a Dart List fits directly: t[k] in the pseudocode is table[k] in Dart, with no -1 or +1 adjustment anywhere.

2. Hash tables with chaining

Now shrink the hotel to 9 rooms but allow unlimited guests — reservation numbers can be any non-negative integer, not just 0–8. The trick: give every reservation number k a room through a hash function h(k) (here h(k) = k mod 9, "which room, counting around 9 rooms"). Several reservations can land in the same room — a collision — and when there are more possible keys than rooms it is mathematically guaranteed to happen (the pigeonhole principle: if |U| > n·m, some n keys must share one slot). Chaining handles it the simple way: each room keeps a guest list (a linked list) of everyone assigned there.

A hash function h: U → {0, 1, ..., m-1} maps the (possibly huge) universe of keys down to m table slots. With chaining, slot t[j] holds a list of every stored key that hashes to j.

The same three procedures in Dart — t is a List of m chains, h(k) = k mod m:

Input size → what is feasible. With m ≈ n (α ≤ 1) and n ≤ 10⁶ keys every operation is a handful of steps (10⁶ operations ≈ a few 10⁶ steps, well under a second); with a bad h or m = 1 the same 10⁶ searches cost 10¹² steps, so the guarantee depends on a good h and a bounded α.

chainedHashInsert is always O(1): compute h(k) and put the key at the front of that slot's list — no search is needed because the procedure assumes the key is not already stored (to enforce that you would search first, at extra cost; the animations below skip that check, so inserting the same key twice leaves two copies in the chain). chainedHashSearch and chainedHashDelete must walk the target slot's list — their cost grows with that one list's length, not with the whole table.

A common mistake is to assume hash-table operations are "always O(1)". They are O(1) on average for a reasonable hash function; the worst case is Θ(n): if every key hashed to the same slot, chainedHashSearch would degrade into a plain linked-list scan. That is why choosing a good h (section 3) matters so much.

Dart implementation

The table slots need no index translation. The only adaptation is the chain itself: each linked list becomes a Dart List<MapEntry<K,V>> used like a stack (insert and remove at index 0 mean "the head of the list"), since Dart needs no hand-built linked-list node type here.

Dart's own hash tables. A Map/Set literal in Dart is a LinkedHashMap/LinkedHashSet, and HashMap/HashSet are plain hash tables of the kind built here. How they really store buckets, resize and use hashCode/== is the subject of D27 · Set & Map (Hash / Linked / SplayTree internals). The panel shows the rule that makes any key type work in them:

Load factor and the two chaining facts

Define the load factor α = n/m — the average number of keys per slot, where n is the number of stored keys and m the number of slots. Assume simple uniform hashing: every key is equally likely to hash to any of the m slots, independently of the other keys. Then:

Fact 1 (unsuccessful search) — looking for a key that is not stored takes Θ(1 + α) expected time: Θ(1) to compute h(k), plus the walk down the whole chain, whose expected length is α.
Fact 2 (successful search) — finding a stored key also takes Θ(1 + α) expected time. The argument is a little subtler because the key you look for helped build the chain you walk, but the answer is the same order of growth.

The practical punchline: if n is kept proportional to m (so α = O(1)), every dictionary operation runs in O(1) expected time however large n becomes, as long as you grow m along with it — the same doubling idea as a dynamic array's capacity, applied to the number of slots.

In code: α is the division n / m; Fact 1 says an unsuccessful search examines α keys on average; Fact 2 says a successful search examines 1 + α/2 − α/(2n) keys. The panel computes both formulas and measures them with a seeded simulation of simple uniform hashing (n = 3000 keys in m = 997 slots, α ≈ 3.01):

Input size → what is feasible. α ≤ 1–3 keeps every operation near 1 + α ≈ 2–4 steps; α = 100 (n = 10⁵ keys, m = 10³ slots) makes each search scan ~100 keys, so resize (double m) when α passes a threshold.

Why Fact 2 works: define an indicator variable X_ij = 1{h(k_i)=h(k_j)} for every pair of keys, with E[X_ij] = 1/m under simple uniform hashing. A successful search for key k_i examines k_i itself plus every key that was inserted later into the same chain (new keys go to the front). Add up the expected number of such later keys, then average over which of the n keys is the target; the total is exactly 1 + α/2 − α/(2n) = Θ(1+α) — the same growth rate as the simpler unsuccessful-search argument, with a smaller constant.

Load factor α = n/m. Chaining: unsuccessful search Θ(1+α), successful search Θ(1+α), insert always Θ(1). Keep α = O(1) (for example, resize when α crosses a threshold) and every operation is O(1) on average.

3. Hash functions

A good hash function behaves like a fair, unpredictable lottery: every key lands in a slot that looks random and independent of every other key's slot (the simple uniform hashing assumption the facts above rely on). A bad hash function is a lottery machine secretly biased toward certain numbers — still legal, but it quietly wrecks the Θ(1+α) guarantee by clustering keys into a few unlucky slots.

The methods below assume keys are natural numbers. Strings are converted first by reading each character code as a digit in base 128: the string "go" becomes 103·128 + 111 = 13295 (103 and 111 are the character codes of g and o).

The division method

h(k) = k mod m. Simple, fast (one machine division), and the default choice — if m is chosen carefully.

Avoid m = 2^p (a power of 2): then h(k) is just the low p bits of k, ignoring every higher bit — if your keys do not vary uniformly in their low bits (very common, for example memory addresses that are always multiples of 4), most of each key's information is wasted. The usual advice: pick m to be a prime not close to an exact power of 2. For example, about 3000 keys in a table with m = 997 give an average chain length of about 3, close to the ideal α ≈ 3.01.

The multiplication method

h(k) = ⌊m · (k·A mod 1)⌋ for a constant 0 < A < 1. Its big advantage: m does not need to be prime. Choosing m = 2^p makes the arithmetic fast on real hardware: let w be the machine word size, compute s = ⌊A · 2^w⌋ once, then for each key multiply k · s, keep only the low w bits (r₀), and take the top p bits of r₀ as the hash. Knuth's suggested constant is A ≈ (√5 − 1)/2 ≈ 0.6180339887 (the reciprocal of the golden ratio), which tends to spread consecutive keys well.

The three formulas as Dart. The real-number version is the formula itself; the integer version is what production code uses, and the panel shows both give the same slot for an example key:

Input size → what is feasible. Division needs one % (keys up to 2⁶³−1 fit Dart's native 64-bit int); the multiplication method needs k·s to fit in 64 bits, so keys must be < 2³¹ for the 32-bit-word version used here (2³¹·2.65·10⁹ ≈ 5.7·10¹⁸ < 9.2·10¹⁸).

Universal hashing

Division and multiplication use one fixed formula, so an adversary who knows it could choose n keys that all collide on purpose, turning your O(1) average into a Θ(n) worst case. Universal hashing defeats this by randomly picking the hash function itself, fresh each time the table is built, from a whole family of candidates — so nobody can predict which one you will use.

A family H of hash functions is universal if, for any two distinct keys k ≠ l, at most a 1/m fraction of the functions in H map them to the same slot. A classic construction: pick a prime p larger than every possible key; for any a ∈ {1,...,p-1} and b ∈ {0,...,p-1} define h_a,b(k) = ((ak+b) mod p) mod m. This family H_pm has p(p-1) functions and is provably universal.

In code: ((a * k + b) % p) % m. The panel counts, for every pair of distinct keys in a small universe, exactly how many of the p(p−1) functions collide, and checks the universal bound "at most 1/m of the family" (here p(p−1)/m).

Input size → what is feasible. For keys < 2³¹ pick a prime p ≈ 2³¹: then a·k + b < 2⁶² stays inside a 64-bit int. The exhaustive count in the panel is O(p²) per pair, so only use it for p ≲ 10³.

What universality buys you: with a randomly chosen universal h and chaining, the expected chain length examined for a key not in the table is at most α, and for a key in the table at most 1+α — and crucially this holds for any sequence of operations, because the adversary must commit to their keys before knowing which random h you will draw. There is no fixed worst-case input anymore, only bad luck on one random draw; any sequence of n operations (with O(m) insertions) then runs in expected Θ(n) total time.

Division method: fast, but needs m prime and not near a power of 2. Multiplication method: m can be any power of 2, fast on real hardware. Universal hashing: randomizes the hash function itself so no fixed input can force worst-case behavior — the strongest guarantee of the three.

Dart implementation

All three hash functions are pure arithmetic — there is no array to index, so no index translation applies. The one Dart-specific detail: the multiplication method's k · s step must stay within a fixed word size w. This page masks with & 0xFFFFFFFF to emulate a 32-bit word explicitly (Dart's native int is 64-bit, so without the mask the "keep only the low w bits" step would silently keep the wrong number of bits).

4. Open addressing

Chaining needs extra memory for list pointers. Open addressing stores every key directly inside the array itself — no chains at all. When a slot is already occupied, the key tries another slot, then another, following a fixed probe sequence h(k,0), h(k,1), h(k,2), ... until it finds an empty one. Picture a full parking lot: if your assigned spot is taken, you follow a fixed rule ("try the next spot", or something fancier) until you find an open one.

Because every key must fit inside the table, α ≤ 1 always (you cannot store more keys than slots). The probe sequence for a key should be a permutation of {0,...,m-1}, so that if the table is not full the key can eventually reach every slot. The procedures below call a helper probe(k, i) that returns the i-th slot to try (for i = 0, 1, ..., m − 1):

Three probing schemes

All three build on the division-method auxiliary hash h₁(k) = k mod m:

Linear probing: h(k,i) = (h₁(k) + i) mod m. Simple, but it suffers primary clustering: once a run of occupied slots forms, it only grows, because any key that hashes into (or just before) the run must probe through all of it.
Quadratic probing: h(k,i) = (h₁(k) + c₁i + c₂i²) mod m (this page uses c₁=1, c₂=3). Milder secondary clustering: two keys with the same first probe follow the same sequence afterwards, but keys with different first probes interfere far less than in linear probing. Not every choice of m, c₁, c₂ reaches all slots, so the constants must be picked carefully.
Double hashing: h(k,i) = (h₁(k) + i·h₂(k)) mod m. The best of the three in practice — up to Θ(m²) distinct probe sequences (against only m for the other two), so it comes closest to the ideal "uniform hashing" assumption (every one of the m! orderings equally likely). h₂(k) must be relatively prime to m: this page uses the standard recipe m prime, h₁(k)=k mod m, h₂(k)=1+(k mod (m-1)). Otherwise the sequence only ever visits m/gcd(m,h₂(k)) slots and silently wastes the rest.

Each scheme below gets three worked examples: a normal insert+search run (nine keys into m = 11 slots, the same keys for all three schemes), an edge case that fills the table completely, deletes a key, re-inserts into the resulting DELETED slot, and then forces a genuine "hash table overflow" error, and a box where you type your own I<k> / S<k> / D<k> operations.

All three schemes plus hashInsert, hashSearch and hashDelete as Dart (t is a List<int> holding keys, with two sentinel values for NIL and DELETED):

Input size → what is feasible. Keep α ≤ 0.5–0.7: expected probes 1/(1−α) = 2–3.3. At α = 0.99 it is 100 probes per operation, so n = 10⁶ keys would need m ≥ 1.5·10⁶ slots (not 10⁶ + 1). m must be prime for double hashing so that h₂(k) is coprime to m.

Naively deleting by writing NIL back into the slot is a correctness bug, not just an inefficiency: if a later search for a different key k' would have probed past the deleted slot, a plain NIL makes the search stop early and report "not found" although k' is still in the table, further along its own probe sequence. The fix is a special DELETED marker: hashSearch treats it as "occupied, keep probing", while hashInsert treats it as "free, reuse me". The price: once DELETED markers exist, search times no longer depend only on the load factor α, which is why chaining is the usual choice when keys are deleted often. The edge-case animations above show both this reuse AND the "hash table overflow" error (hashInsert's final error row) that fires once every slot is genuinely full.

Dart implementation

The probe index i runs 0..m-1 and slot numbers are already valid List indexes, so nothing needs translating. The pseudocode's "use a special value DELETED" becomes explicit here with a small _Slot class carrying both the key and a deleted flag, plus a shared probe(k,i) method that switches between all three schemes above.

Expected number of probes (uniform hashing assumption)

Fact 3 (unsuccessful search and insert): an unsuccessful search examines at most 1/(1−α) slots on average; an insertion costs the same, since it is an unsuccessful search followed by a write into the empty slot it found. Fact 4 (successful search): a successful search examines at most (1/α)·ln(1/(1−α)) slots on average.

The two probe bounds are one-line formulas in Dart. The panel evaluates them at α = 0.5 (2 and < 1.387 probes) and α = 0.9 (10 and < 2.559) and then measures them: a 1000-slot table filled to α = 0.9 where every key gets a random probe permutation.

Half-full table (α=0.5): unsuccessful search ≤ 2 probes, successful search < 1.387 probes. Table 90% full (α=0.9): unsuccessful ≤ 10 probes, successful < 2.559 probes. Both bounds blow up as α → 1 — open addressing degrades badly when nearly full, which is why real implementations resize well before that point.

5. Perfect hashing

Everything above gives good average-case time, but a Θ(n) worst case is always theoretically possible. If your key set is static — known in advance and never changing (a compiler's table of reserved words, a fixed list of blocked domains) — you can do better: perfect hashing guarantees O(1) worst-case search, with no collisions at all among the stored keys.

The idea is two levels of hashing. Level 1: a universal hash h maps the n keys into m = n slots — collisions are still allowed here. Level 2: each slot j that received n_j keys gets its own secondary table of size m_j = n_j², with its own randomly chosen universal hash h_j — sized so that a collision-free secondary hash is easy to find.

Two numbers make perfect hashing work, and the panel computes both exactly by trying every function of H_pm (p = 1009, 10 keys): the level-1 cost E[Σ n_j²] stays below 2n, and a level-2 table of size m = n² has a collision under fewer than half of the functions.

Input size → what is feasible. n ≤ 10⁶ static keys: expected total secondary space < 2n = 2·10⁶ slots and O(n) expected build time; each lookup is exactly two hash evaluations. Rebuild from scratch if the key set changes.

The birthday-paradox trick: if you hash n keys into a table of size m = n² with a random universal hash, the probability of any collision is less than 1/2. The expected number of colliding pairs is at most C(n,2)/m < 1/2, and Markov's inequality turns that into a probability bound. So: pick a random secondary hash, check for collisions, and if there are any, throw it away and retry — on average fewer than 2 tries are needed. Space bound: with m=n at level 1, the expected total secondary storage Σnⱼ² stays below 2n, so the whole structure uses only O(n) space despite the squaring.

Perfect hashing trades "static key set only" and "more setup work" for a hard guarantee: O(1) worst-case search and O(n) expected space. It is not used for dictionaries that need insert/delete at runtime — chaining or open addressing (sections 2 and 4) are the right tools there.

Dart implementation

No index translation is needed here either. The interesting step is turning the informal "for each slot, build a secondary table" into two explicit classes: PerfectHashBucket (one slot's secondary table plus its own random hash) and PerfectHashTable (the level-1 hash plus the list of buckets), with the retry loop written as an ordinary bounded for loop.

Quiz

Interview questions

Cheat sheet

Structure / method	Search (avg)	Insert (avg)	Delete (avg)	Search (worst)	Space	When to use
Direct addressing	Θ(1)	Θ(1)	Θ(1)	Θ(1)	Θ(\|U\|)	Only when the key universe itself is small
Chaining (division/multiplication hash)	Θ(1+α)	Θ(1)	Θ(1) given the node and doubly linked chains; Θ(1+α) when you must search by key first	Θ(n)	Θ(n+m)	Default choice; simplest deletion; α can exceed 1
Chaining + universal hashing	O(1+α) expected, any input	Θ(1)	O(1) given the node (doubly linked); O(1+α) expected by key	Θ(n)	Θ(n+m)	When keys might be adversarial (security-sensitive tables)
Open addressing, linear probing	≤1/(1−α)	≤1/(1−α)	needs DELETED marker	Θ(n)	Θ(m), α≤1	Cache-friendly, but primary clustering at high α
Open addressing, quadratic probing	≤1/(1−α)*	≤1/(1−α)*	needs DELETED marker	Θ(n)	Θ(m), α≤1	Milder clustering than linear; m and constants must be chosen carefully
Open addressing, double hashing	≈1/(1−α)	≈1/(1−α)	needs DELETED marker	Θ(n)	Θ(m), α≤1	Closest to ideal uniform hashing among the three; needs gcd(m,h₂(k))=1
Perfect hashing (two-level)	Θ(1)	not supported (static)	not supported (static)	Θ(1)	O(n) expected	Static key sets needing a hard worst-case guarantee

*The probe bounds (Facts 3 and 4) are proven under the idealized uniform hashing assumption; linear and quadratic probing only approximate it (they have far fewer distinct probe sequences than the m! that true uniform hashing would allow), so their real-world numbers are usually a bit worse than these bounds when clustering sets in.