SME
Data Structures & Algorithms · Problem type
Hash table probes
Use this for “750 keys sit in a hash table of 1000 slots. How many probes does a search take on average?”
Chart
This is an example. Type your own values to start a new problem.
α
=
n
m
Sₕᵢₜ
=
1
+
1
1
−
÷
2
Sₘᵢₛₛ
=
1
+
1
(1
−
)
2
÷
2
Schain
Chaining, hit
calculated
Formulas
α
=
n
m
0.75
=
750
1,000
Sₕᵢₜ
=
1 + 1 ÷ (1 −
α
)
2
2.5
=
1 + 1 ÷ (1 − 0.75)
2
Sₘᵢₛₛ
=
(1
+
(
1
1 −
α
)²)
÷
2
8.5
=
(1
+
(
1
1 − 0.75
)²)
÷
2
Schain
=
1
+
α
2
1.375
=
1
+
0.75
2
Assumptions
•
The hash function spreads keys evenly and independently over the m slots (uniform hashing).
•
Linear probing tries the next slot on a collision, so it needs an empty slot: fewer keys than slots (α < 1).
•
Separate chaining keeps a list at each slot, so it works at any load factor; a hit probes half the other keys in its list on average.
•
These are Knuth’s averages for a large table; a small table can differ a little.
Step-by-step
WE KNOW
n = 750, m = 1,000
FIND
load factor (α), probing, hit (Sₕᵢₜ), probing, miss (Sₘᵢₛₛ), chaining, hit (Schain)
Step 1 · Find load factor (α)
Use α = n ÷ m
The load factor is the share of slots in use: keys per slot.
α
=
750
1,000
α
=
0.75
Step 2 · Find probing, hit (Sₕᵢₜ)
Use Sₕᵢₜ = (1 + 1 ÷ (1 − α)) ÷ 2
A hit finds its key after half the run of full slots ahead of it, plus the slot it sits in.
Sₕᵢₜ
=
1 + 1 ÷ (1 − 0.75)
2
Sₕᵢₜ
=
1 + 1 ÷ 0.25
2
Sₕᵢₜ
=
1 + 4
2
Sₕᵢₜ
=
5
2
Sₕᵢₜ = 2.5
Step 3 · Find probing, miss (Sₘᵢₛₛ)
Use Sₘᵢₛₛ = (1 + (1 ÷ (1 − α))²) ÷ 2
A miss runs to the next empty slot, and full slots cluster, so its cost grows as the square.
Sₘᵢₛₛ
=
(1
+
(
1
1 − 0.75
)²)
÷
2
Sₘᵢₛₛ
=
(1
+
(
1
0.25
)
2
)
÷
2
Sₘᵢₛₛ
=
1 +
4
2
2
Sₘᵢₛₛ
=
1 + 16
2
Sₘᵢₛₛ
=
17
2
Sₘᵢₛₛ = 8.5
Step 4 · Find chaining, hit (Schain)
Use Schain = 1 + α ÷ 2
A
list
holds
α
keys
on
average;
a
hit
reads
its
own
key
and
half
of
the
others
before
it.
Schain
=
1
+
0.75
2
Schain = 1 + 0.375
Schain = 1.375
Check
Put the numbers back in. Both sides should match.
0.75
=
750
1,000
✓
2.5
=
1 + 1 ÷ (1 − 0.75)
2
✓
8.5
=
(1
+
(
1
1 − 0.75
)²)
÷
2
✓
1.375
=
1
+
0.75
2
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Sorting and searching
Main lesson
Comparisons: quadratic sorts vs merge sort
Use this for “How many comparisons does selection sort make on 1000 items, and at most how many does merge sort make?”
Merge sort pass by pass
Use this for “Show the passes of merge sort on 5 2 8 1 9 3 7 4. How many comparisons does it make?”