Probability of Collisions

Abstract

Collisions are the primary bottleneck for Hash Table performance. By applying probability theory—specifically the mathematical framework of the Birthday Paradox—we can calculate exactly how quickly collisions manifest, allowing us to determine the optimal Hash Table Capacity ($M$) and Load Factor ($\alpha$) needed to maintain true $O(1)$ operational speeds.

• Category: Probability & Performance Optimization
• Solves: Mathematical modeling of index collision boundaries.
• Typical use cases: Capacity dimensioning, threshold tuning for dynamic array resizers, hash function distribution verification.

---

The Mathematical Probability of a Collision

To evaluate the mathematical probability of an indexing conflict occurring, it is simpler to calculate the probability that no collision occurs ($P(\text{no collision})$) and subtract that target value from 1:

$$P(\text{at least 1 collision})=1-P(\text{no collision})$$

When sequentially introducing $N$ unique keys into an array containing $M$ slots, the probability that each successive key successfully avoids landing on an occupied coordinate relies on a conditional chain:

• 1st Key: $P_1=\frac{M}{M}=1\text{(100\% chance of isolated placement)}$
• 2nd Key: $P_2=\frac{M-1}{M}\text{(One slot is already occupied)}$
• 3rd Key: $P_3=\frac{M-2}{M}\text{(Two slots are already occupied)}$
• $N$-th Key: $P_N=\frac{M-(N-1)}{M}$

Combining these parameters yields the exact probability profile for a clean collision-free deployment:

$$P(\text{no collision})=\frac{M}{M}\times \frac{M-1}{M}\times \frac{M-2}{M}\times \cdots \times \frac{M-N+1}{M}=\frac{M!}{M^N(M-N)!}$$

---

The Hashing Birthday Paradox

A classic illustration of this probability curve is the Birthday Paradox. Even though there are $M=365$ discrete calendar days available inside a year, the group size required to likely trigger a shared birthday collision is paradoxically small:

• With a tiny cohort of only 23 people, the probability of a collision crosses the 50% mark.
• Expanding that cohort to 60 people causes the collision probability to spike past 99%.

Collision Likelihood Scale (M = 365 Slots)
[ 1 Person  ] ---> 0% Probability
[ 23 People ] ---> 50% Probability (Table is only 6.3% full!)
[ 60 People ] ---> 99% Probability (Table is only 16.4% full!)

Key Idea

Index collisions manifest significantly sooner than human intuition assumes. A Hash Table tracking 365 slots that is only 16% saturated is already mathematically near-guaranteed to contain a collision, proving that resolution algorithms are mandatory from day one.

---

Optimal Load Factor ($\alpha$) Bounds

The Load Factor is defined as the structural density ratio of elements to available slots:

$$\alpha =\frac{N}{M}$$

As $\alpha$ scales upward, the expected number of operations required to resolve collisions grows, causing performance to degrade.

The 0.75 Rule of Thumb

• The Threshold Performance Wall: Empirical profiling indicates that lookup speeds remain flat and fast until $\alpha \approx 0.75$. Past this tipping point, crowding causes search speeds to degrade rapidly toward linear scans.
• The Sizing Strategy: To maintain predictable average constant-time performance, design tables to ensure capacity tracks to approximately $M\approx 1.3N$.
• Resizing Maintenance: If $\alpha$ crosses the 0.75 threshold during the table’s execution lifecycle, the backing array must instantly expand (typically doubling its allocation) and rehash every element into the new index space.

---

Why Table Capacities Must Be Prime Numbers

Our mathematical probability models assume a uniform hash distribution where every array slot has an equal probability of being selected. However, if an item’s hash function output shares common factors with the table capacity $M$, massive structural “dead zones” can emerge inside the array.

Mathematical Factorization Failure Case

Suppose a structured data generator outputs keys yielding multiples of 3 ($h(k)=3k$) and maps them into an array of capacity $M=6$:

$$\text{Resolved Indices}=3k(\mathrm{mod}6)$$

• $\text{Key}=1\to \text{Index}=3(\mathrm{mod}6)=3$
• $\text{Key}=2\to \text{Index}=6(\mathrm{mod}6)=0$
• $\text{Key}=3\to \text{Index}=9(\mathrm{mod}6)=3$
• $\text{Key}=4\to \text{Index}=12(\mathrm{mod}6)=0$

Under this arrangement, elements loop back and forth between indices 0 and 3 forever. Slots 1, 2, 4, and 5 stay entirely empty, instantly inducing artificial clusters and severe early collisions.

The Prime Solution

Always enforce prime numbers for the table capacity $M$. Forcing modulo arithmetic against a prime number automatically breaks common factor loops, compelling even heavily patterned or clustered hash outputs to distribute uniformly across the full array spectrum.

---

Summary of Optimized Table Design

Design Control Parameter	Optimal Selection Target	Engineering Operational Justification
Capacity ($M$)	$\approx 1.3\times N$	Keeps the average count of probe evaluations near constant.
Load Factor ($\alpha$)	$\le 0.75$	Forestalls the performance cliff seen in saturated tables.
Array Sizing Logic	Prime Numbers	Prevents pattern factor loops to secure uniform distribution.
Dynamic Maintenance	Full Rehash on Resize	Updates every existing item to its new valid modulo index.

---

Related Notes

• Hash Tables
• Hash Functions
• Collision Resolution Strategies