Expected probes and collision probabilities

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Linear probing slot sequence? from Lesson 2.2.2
• Chaining: expected keys examined in an unsuccessful search? from Lesson 2.2.1
• Θ(1 + 1/2 + … + 1/n)? from Lesson 0.1.2

1 · The Hook

🎣

Open-addressing performance collapses as the table fills: at 50% full an unsuccessful search expects 2 probes; at 90% full, 10. And collisions begin surprisingly early: with only 23 keys in 365 slots, a collision is more likely than not. GATE asks both kinds of number.

2 · Predict First

🤔

An open-addressing table is 75% full (α = 0.75), with uniform hashing (every probe sequence equally likely). Roughly how many probes does an unsuccessful search expect?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1 / (1 − α) = 1 / 0.25 = 4 probes.

Expected probes, open addressing (uniform hashing, α < 1)

• Unsuccessful search (and insertion): at most 1 / (1 − α).
• Successful search: at most (1/α) · ln(1 / (1 − α)).

(Linear probing is worse because of clustering: about ½(1 + 1/(1 − α)²) for unsuccessful search.)

Chaining, for comparison

Unsuccessful Θ(1 + α); successful about 1 + α/2.

Collision probabilities (simple uniform hashing, m slots)

• n keys, no collision at all: P = m(m − 1)(m − 2)…(m − n + 1) / mⁿ.
• A specific slot stays empty after n insertions: (1 − 1/m)ⁿ. k specific slots all empty: (1 − k/m)ⁿ.
• Expected number of empty slots: m(1 − 1/m)ⁿ.
• Expected number of colliding pairs: C(n, 2) / m.

Example: 100 slots, chaining. Probability that slots 0, 1, 2 are all still empty after 3 insertions: (97/100)³ ≈ 0.9127.

4 · Visual

Expected probes for an unsuccessful search (open addressing, uniform hashing)

alpha: 0.1  0.3  0.5  0.7  0.8  0.9  0.95
probes:1.1  1.4  2    3.3  5    10   20      -> blows up as alpha -> 1

5 · Worked Examples

Example 1 Easy

α = 0.8, open addressing with uniform hashing. Expected probes for an unsuccessful search?

Solution

1 / 0.2 = 5.

Example 2 Medium

Simple uniform hashing into 10 slots. Probability that 3 keys all land in different slots?

Solution

(10 × 9 × 8) / 10³ = 0.72.

Example 3 GATE

Chaining, 100 slots, 3 insertions, simple uniform hashing. Probability that the first 3 slots (0, 1, 2) are unfilled?

Solution

(97/100)³ = 0.9127 (to 4 decimals).

6 · GATE Traps

⚠️

• 1/(1 − α) is for open addressing; chaining is 1 + α.
• These formulas assume uniform hashing; linear probing does worse.
• "No collision" multiplies decreasing counts (m, m − 1, …).
• Expected colliding pairs: C(n, 2)/m, not n/m.

7 · Memory Hook

🧠

"Miss costs 1/(1 − α); hit costs (1/α)ln(1/(1 − α))."

8 · Connect the Dots

Phase 2 is complete: searching by comparisons and by hashing. Phase 3 turns to sorting: from the simple quadratic sorts to merge sort, quicksort, heapsort, and the limits of comparison sorting.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markUnsuccessful probes

Open addressing, uniform hashing, α = 0.6. Expected probes for an unsuccessful search?

Numerical answer: ________

Q2NAT2 marksSuccessful probes

Open addressing, uniform hashing, α = 0.5. Expected probes for a successful search (2 decimals)?

Numerical answer: ________

Q3NAT2 marksNo collision

Simple uniform hashing into 20 slots. Probability that 3 keys go to 3 different slots?

Numerical answer: ________

Q4NAT2 marksExpected pairs

50 keys hashed uniformly into 1,000 slots. Expected number of colliding pairs?

Numerical answer: ________

Q5MCQ1 markComparison

At α = 0.9, which needs fewer expected probes for an unsuccessful search (uniform hashing)?

• (A) It depends on m only
• (B) They are equal
• (C) Open addressing (about 10)
• (D) Chaining (about 1.9)

10 · Rule Card

• Open addressing (uniform): unsuccessful ≤ 1/(1−α); successful ≤ (1/α)ln(1/(1−α)).
• Chaining: unsuccessful Θ(1 + α); successful ≈ 1 + α/2.
• P(no collision) = m(m−1)…(m−n+1)/mⁿ; P(k given slots empty) = (1 − k/m)ⁿ.
• E[empty slots] = m(1 − 1/m)ⁿ; E[colliding pairs] = C(n,2)/m.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

uniform hashingexpected probes 1/(1 − α)successful-search probesprobability of no collisionprobability a slot stays emptyexpected empty slotsexpected colliding pairs

12 · Answer Vault