Quadratic Probing for Collision Resolution in Hash Tables

Introduction to Open Addressing

In hash table design, hash collisions are mathematically inevitable due to the pigeonhole principle: we are mapping a vast, potentially infinite application key space into a finite table of size $m$.

There are two primary paradigms for conflict resolution:

1. Separate Chaining (Closed Addressing): Each bucket points to an auxiliary data structure (such as a linked list or balanced binary search tree) containing all keys that map to that index.
2. Open Addressing: All elements reside directly within the hash table array itself. If a collision occurs at a key’s primary hash slot, the table deterministically probes alternative slots until an empty bucket is found.

Open addressing is exceptionally space-efficient because it avoids pointer overhead and the auxiliary memory allocations required by linked lists. However, the performance of open addressing hinges critically on the probing function used to locate alternate slots.

+-------------------------------------------------------------+
|                        Open Addressing                      |
|                                                             |
| Key k ----> Hash Function h(k) ----> Primary Slot: h(k)     |
|                                                             |
| If Slot Occupied:                                           |
|   Attempt 0: P(k, 0) -> Primary Slot                        |
|   Attempt 1: P(k, 1) -> Alternate Slot 1                    |
|   Attempt 2: P(k, 2) -> Alternate Slot 2                    |
|   ...                                                       |
|   Attempt i: P(k, i) -> (h(k) + f(i)) mod m                 |
+-------------------------------------------------------------+

A probing function takes the key $k$ and the attempt count $i$ (where $i \in \{0, 1, 2, \dots, m - 1\}$) and outputs a deterministic index in the table:

$\text{Index} = P(k, i) \pmod m$

---

The Pitfall of Linear Probing: Primary Clustering

In linear probing, the offset function is strictly linear with respect to the attempt number:

$P(k, i) = (h(k) + i) \pmod m$

When a collision occurs at index $h(k)$, linear probing checks $h(k) + 1$, then $h(k) + 2$, and so on, wrapping around the end of the array.

Why Linear Probing Suffers

Linear probing suffers severely from cascading collisions, commonly termed primary clustering:

• If key $K_1$ hashes to index 2, it occupies slot 2.
• If key $K_2$ also hashes to index 2, it finds slot 2 occupied and claims slot 3.
• If key $K_3$ arrives and naturally hashes to index 3, it finds slot 3 occupied by $K_2$ (even though $K_3$ never originally collided with $K_1$). $K_3$ is forced to spill over into slot 4.

Slot Index:   [0]    [1]    [2]    [3]    [4]    [5]
Entries:      ---    ---   [K1]   [K2]   [K3]    ---
                           ^      ^      ^
                           |      |      |
                 Primary Slot     |      Cascaded collision
                         Collided with K1

Any collision creates a contiguous block of occupied slots. As this block grows, the probability that a new, randomly hashed key lands within or immediately adjacent to this block increases proportionally to the block’s length. This causes clusters to snowball, degrading average lookup, insertion, and deletion times from $O(1)$ to $O(n)$.

---

Mechanics of Quadratic Probing

To break up contiguous clusters, quadratic probing replaces the unit increment with a quadratic polynomial of the attempt counter $i$:

$P(k, i) = \left( h(k) + c_1 \cdot i + c_2 \cdot i^2 \right) \pmod m$

Where:

• $h(k)$ is the primary hash function.
• $i$ is the collision attempt index ($0, 1, 2, \dots$).
• $c_1$ and $c_2$ are tuning constants.
• Constraint: $c_2 \neq 0$. If $c_2 = 0$, the function degrades into linear probing.

In its standard form (where $c_1 = 0$ and $c_2 = 1$ or $c_1 = 1$ and $c_2 = 1$), successive probes take quadratic leaps:

Attempt ($i$)	Quadratic Offset ($i^2$)	Target Slot Index
$i = 0$	$0$	$h(k)$ (Primary slot)
$i = 1$	$1$	$(h(k) + 1) \pmod m$
$i = 2$	$4$	$(h(k) + 4) \pmod m$
$i = 3$	$9$	$(h(k) + 9) \pmod m$
$i = 4$	$16$	$(h(k) + 16) \pmod m$
$i = 5$	$25$	$(h(k) + 25) \pmod m$

How Quadratic Leaps Prevent Clustering

Because the leap distance grows exponentially with each attempt, successive collisions do not occupy immediately adjacent buckets. Instead, keys are dispersed across widely separated indices in the hash table.

Even if multiple keys experience collisions, their consecutive probe steps leap over contiguous runs of elements. As a result, large monolithic blocks of occupied cells do not form, drastically curtailing primary clustering.

graph TD
    subgraph Linear Probing (Step Size = 1)
        L0[h(k)] --> L1[+1] --> L2[+2] --> L3[+3] --> L4[+4]
    end
    subgraph Quadratic Probing (Step Size = i^2)
        Q0[h(k)] --> Q1[+1] --> Q2[+4] --> Q3[+9] --> Q4[+16]
    end

---

The Fundamental Trade-off: Cache Locality vs. Collision Distribution

Choosing between linear probing and quadratic probing involves a direct architectural trade-off between spatial cache locality and clustering susceptibility.

Linear Probing and Hardware Cache Lines

Modern CPUs do not fetch single words from main memory; they fetch entire cache lines (typically 64 bytes) into L1/L2/L3 caches.

• When linear probing accesses slot $A[2]$, the memory subsystem loads a block containing $A[2], A[3], A[4], A[5], \dots$ into the CPU cache line.
• If $A[2]$ is occupied, probing $A[3]$ or $A[4]$ results in an immediate cache hit, executing in single-digit clock cycles without a main memory stall.
• Therefore, linear probing has nearly ideal spatial locality of reference.

Quadratic Probing’s Cache Behavior

Quadratic probing trades away some cache locality to eliminate clustering:

• For small $i$ ($i=1, 2$): The offset values ($+1, +4$) are still relatively small. If array elements are small, the first couple of collision probes may still land within the same memory page or even the same CPU cache line.
• For larger $i$ ($i \ge 3$): The offsets ($+9, +16, +25, \dots$) cause the CPU to jump across cache lines and memory pages, resulting in frequent cache misses and pipeline stalls.

Memory Page / Cache Line [A[0] ... A[7]]
+-------+-------+-------+-------+-------+-------+-------+-------+
| A[0]  | A[1]  | A[2]  | A[3]  | A[4]  | A[5]  | A[6]  | A[7]  |
+-------+-------+-------+-------+-------+-------+-------+-------+
                  ^       ^                       ^
                  |       |                       |
                 i=0     i=1                     i=2
                 (h)    (+1)                     (+4)
                 [------- Stays inside Cache Line ------]

Next Probe (i=3, offset +9): Lands at A[11] ---> CACHE MISS

Quadratic probing retains reasonable cache locality during initial collisions while providing far better dispersion than linear probing when collision rates increase.

---

Limitations of Quadratic Probing

While quadratic probing solves primary clustering, it introduces two distinct challenges that system implementers must handle:

1. Secondary Clustering

Quadratic probing eliminates primary clustering, but it remains susceptible to secondary clustering.

• If two distinct keys, $K_A$ and $K_B$, happen to produce the exact same primary hash ($h(K_A) = h(K_B)$), they will traverse the exact same probe sequence: $\{h(k)+1, h(k)+4, h(k)+9, \dots\}$
• While not as destructive as primary clustering (unrelated keys that hash to adjacent buckets do not coalesce into the cluster), secondary clustering can still create long probe chains when the hash function creates hotspots.

(Note: Eliminating secondary clustering requires techniques like Double Hashing, where the step size is dictated by a second hash function $h_2(k)$ rather than a fixed polynomial).

2. Table Coverage and Cycle Guarantees

With linear probing, incrementing by $1$ guarantees that every single slot in the hash table will be inspected before returning to the start, provided the table is not $100\%$ full.

With quadratic probing, because the indices jump non-linearly, the sequence of probes might enter a mathematical cycle that visits only a fraction of the table’s slots, potentially reporting that the table is full even when empty slots exist.

To ensure that quadratic probing visits at least $\lceil m/2 \rceil$ distinct slots (or the entire table), specific mathematical constraints must be met:

• Theorem: If table size $m$ is a prime number and the probing function is $P(k, i) = (h(k) + i^2) \pmod m$, the first $\lceil m / 2 \rceil$ probes will always visit distinct locations, provided the load factor $\alpha < 0.5$.
• Alternative Formulation: If the table size is a power of two ($m = 2^p$) and constants are chosen such that $c_1 = c_2 = 1/2$, the probe sequence $P(k, i) = (h(k) + \frac{i + i^2}{2}) \pmod m$ is guaranteed to visit all $m$ buckets.

---

Comparison: Linear Probing vs. Quadratic Probing

Property	Linear Probing	Quadratic Probing
Probe Formula	$P(k, i) = (h(k) + i) \pmod m$	$P(k, i) = (h(k) + c_1 i + c_2 i^2) \pmod m$
Primary Clustering	High (forms monolithic blocks)	Very Low (broken up by quadratic leaps)
Secondary Clustering	Present	Present (identical hashes follow identical paths)
CPU Cache Performance	Exceptional (sequential memory access)	Moderate (initial probes hit cache; later probes miss)
Full Table Traversal	Guaranteed (if $\gcd(\text{step}, m) = 1$)	Requires careful selection of $c_1, c_2$, and $m$
Optimal Load Factor ($\alpha$)	Typically $\le 0.5$ to $0.7$	Typically $\le 0.5$

---

Summary

• Open Addressing stores all entries in the backing array, avoiding pointer overhead but requiring a robust collision resolution strategy.
• Linear Probing features optimal cache locality but degrades rapidly under heavy load due to primary clustering.
• Quadratic Probing introduces non-linear step sizes ($i^2$), dispersing collisions across the array and effectively mitigating primary clustering.
• Hardware Trade-offs: Quadratic probing maintains acceptable cache line locality for the first 2–3 collision attempts while protecting the data structure from catastrophic degradation when minor collision clusters form.