Intuition The one core ideaA hash table is just a row of numbered boxes , and a hash function is a rule that turns a key into a box number . When two keys are sent to the same box, open addressing solves the fight with a second rule — a probe sequence — that says "if this box is taken, here is the next box to try, and the next, until you find an empty one."
Everything on the parent page is built from four humble ingredients: a key , a table of slots , the mod operationsequence of tries . This page earns each of them from scratch.
Before any symbol, look at the object we are storing things in.
Definition Slot, index, tableA table is a fixed-length row of boxes. Each box is a slot . Each slot has an address called its index — a whole number counting from 0
The picture shows 7 0 , 1 , 2 , 3 , 4 , 5 , 6
"Index 0 first box, not the second. Computers count from zero.
We will call the number of slots m m = 7
Intuition Why count from zero?Because the wrap-around trick (next section) uses remainders, and remainders naturally live in the range 0 , 1 , … , m − 1 0 same set of numbers — no awkward off-by-one.
A key k 85 700
Picture: a luggage tag with a number written on it. We must decide which slot this tag belongs in.
The whole game is a function from keys (possibly huge numbers) to slots (only m
Everything uses mod
a mod m a mod m remainder left over when you divide a m
50 mod 7 7 50 7 49 1 50 mod 7 = 1 700 mod 7 7 700 0 700 mod 7 = 0
The picture that makes mod obvious is a clock .
mod = a circular ruler
Lay the numbers 0 , 1 , 2 , … m wraps back to 0 . A clock is exactly mod 12 11 2 ( 11 + 3 ) mod 12 = 2 why hash tables use mod: no matter how large the key, mod m folds it back into the range 0 … m − 1 valid slot index . It is the tool that squeezes infinitely many keys into finitely many boxes.
mod gives the quotient."
No. mod gives the remainder . 50 mod 7 = 1 50 ÷ 7 = 7
Now we name the rule that turns a key into its home slot.
Definition Base hash functionh 1 ( k ) h 1 ( k ) where does key k " On the parent page it is the division method :
h 1 ( k ) = k mod m .
h 1 ( 85 ) = 85 mod 7 = 1 85 home slot is 1 Picture: an arrow from the luggage tag 85 1
The little subscript 1 hash number one " — we keep the name free because double hashing will introduce a second hash, h 2 Hash functions — division & multiplication methods .)
Intuition Why do we even need a hash function?Without one, finding a key means scanning the whole table (m directly to the likely slot in one step. That is the entire speed advantage of hashing.
Collisions are the entire reason open addressing exists. The parent contrasts two cures:
Hashing — chaining Open addressing — keep everyone inside the table, using a probe rule (next section).
i i try counter : i = 0 i = 1
Picture: footprints numbered 0 , 1 , 2 , …
Definition Offset functionf ( i ) f ( i ) how far from home to jump on try i . It must satisfy f ( 0 ) = 0 try zero is always the home slot .
Linear: f ( i ) = i 0 , 1 , 2 , 3 , …
Quadratic: f ( i ) = i 2 0 , 1 , 4 , 9 , …
Double: f ( i ) = i h 2 ( k )
Worked example Reading the template out loud (linear,m = 7 85 h 1 ( 85 ) = 1 1
i = 0 ( 1 + 0 ) mod 7 = 1 i = 1 ( 1 + 1 ) mod 7 = 2 85 2
Definition Probe sequenceThe probe sequence is the ordered list of slots the template visits as i = 0 , 1 , 2 , … h ( k , 0 ) , h ( k , 1 ) , h ( k , 2 ) , …
Picture: the numbered footprints from figure s04, in order.
This is precisely why the parent worries about h 2 ( k ) coprime to m and about m prime — those conditions are what force the sequence to be a full permutation. (Coprime = "share no common factor except 1 Prime table sizes .)
α ≈ α 1/ ( 1 − α ) α alone . As α → 1 rehash into a bigger table before it fills — see Load factor and rehashing .
The parent derives expected probes with a ∑
i = 0 ∑ ∞ t i S ("sigma") means "add up a list of terms." The i = 0 ∞ ∑ i = 0 ∞ α i = α 0 + α 1 + α 2 + ⋯ = 1 + α + α 2 + ⋯
Picture: stacking bars of heights 1 , α , α 2 , … α < 1 finite total .
Probe index i and offset f
Read it as: the table , modkey combine into the base hash ; a base hash makes collisions possible; collisions demand a probe rule ; the probe rule must form a permutation ; and separately, α ∑
Cover the right side. If you can answer every one, you are ready for the parent topic .
What does index 0 m The very first slot; computers count from zero, so valid indices are 0 m − 1
Compute 85 mod 7 1 7 × 12 = 84 1
Why does a hash function use mod m? mod m folds any key into the range 0 … m − 1
What is a collision? Two different keys map to the same home slot: h 1 ( k 1 ) = h 1 ( k 2 )
What must f ( 0 ) f ( 0 ) = 0 i = 0 h 1 ( k )
Write the general probe template. h ( k , i ) = ( h 1 ( k ) + f ( i )) mod m
What does "permutation of all m Every slot is eventually visited, so an insert never fails while an empty slot still exists.
Define the load factor α α = n / m 0 ≤ α < 1
What does ∑ i = 0 ∞ α i 0 ≤ α < 1 1 − α 1
Why start counting slots at 0 1 So slot indices and mod m remainders are the exact same set of numbers 0 … m − 1