Hashing - DSA | Chapter: Open Addressing II: Quadratic Probing Mechanics

This chapter explores the mechanics of Quadratic Probing, an advanced collision resolution technique in open-addressed hash tables. We analyze the limitations of Linear Probing—specifically the performance-degrading phenomenon known as Primary Clustering—and demonstrate how Quadratic Probing resolves this by using non-linear, quadratic step sizes to disperse keys uniformly across the hash table.

1. The Problem with Linear Probing: Primary Clustering

In Linear Probing, when a collision occurs at a hash index, we search for the next available slot sequentially (i.e., index by index: $i + 1, i + 2, i + 3, \dots$ ). While simple to implement, this sequential search strategy introduces a major performance bottleneck known as Primary Clustering.

What is Primary Clustering?

Primary Clustering is the tendency for occupied slots in a hash table to form continuous, dense blocks (clusters) over time. Once a cluster forms, the probability of subsequent keys hashing into or near that cluster increases. This causes a cascading effect where collisions become increasingly frequent, and resolving them requires longer search paths.

Structure & Concept Flow

Index: 0 1 2 3 4 5 6 7 8 9

Table: [ ][ ][72][ ][84][95][96][97][ ][ ]

^------------------^

Continuous Cluster

The Cost of Primary Clustering

When a large cluster forms, inserting a new element that hashes into the cluster requires traversing the entire block of occupied slots before finding an empty space.

Time Complexity Degradation: The average-case time complexity of insertion and search operations degrades from $O(1)$ toward $O(N)$ (where $N$ is the number of elements in the table).
Inefficient Traversals: To insert a single element, the system must perform multiple sequential lookups, wasting CPU cycles and destroying cache locality benefits due to prolonged search paths.

2. Real-Life Analogy: The Parking Lot Bottleneck

💡 Real-Life Analogy

Imagine a popular shopping mall parking lot with numbered spaces from 0 to 9.

Under a Linear Probing strategy, drivers are instructed: "If your preferred spot is taken, check the very next spot, then the next, and so on." If spots 4, 5, 6, and 7 are occupied, a new driver wanting spot 4 must slowly drive past spots 5, 6, and 7 before finally parking in spot 8. This creates a massive traffic bottleneck (a cluster) around that specific section of the parking lot.

Under a Quadratic Probing strategy, the instruction changes: "If your preferred spot is taken, don't crawl space-by-space. Instead, jump ahead by $1^2$ (1 spot), then $2^2$ (4 spots), then $3^2$ (9 spots)." This disperses the cars across different sections of the parking lot, preventing traffic jams and distributing the cars evenly.

3. Introduction to Quadratic Probing

To eliminate the primary clustering bottleneck, we transition from linear search steps to quadratic search steps. Instead of checking the immediate next slot, we use a quadratic function of the collision iteration variable $i$ to determine the next probe position.

The Core Mental Model

If our initial hash index is occupied, we probe the table at progressively larger intervals:

Probe 0 ( $i = 0$ ): Base Hash Index
Probe 1 ( $i = 1$ ): Base Hash Index $+ 1^2$
Probe 2 ( $i = 2$ ): Base Hash Index $+ 2^2$ (4 slots away)
Probe 3 ( $i = 3$ ): Base Hash Index $+ 3^2$ (9 slots away)

By squaring the step index ( $i^2$ ), we "jump" over potential clusters, ensuring that keys hashing to nearby locations do not merge into a single continuous block of occupied slots.

4. Mathematical Formulation & Hash Function

The hash function for Quadratic Probing is defined mathematically as:

h(k, i) = (h'(k) + i^2) \pmod m

Where:

$k$ : The key being inserted or searched.
$i$ : The probe number (collision iteration index), starting at $0, 1, 2, \dots, m-1$ .
$h'(k)$ : The auxiliary/base hash function (typically $k \pmod m$ ).
$m$ : The size of the hash table.
$h(k, i)$ : The resolved slot index in the hash table.

Step-by-Step Probe Sequence Generation

For any key $k$ , the sequence of indices probed will be:

CODE

i = 0:  Index_0 = ( h'(k) + 0 ) % m
i = 1:  Index_1 = ( h'(k) + 1 ) % m
i = 2:  Index_2 = ( h'(k) + 4 ) % m
i = 3:  Index_3 = ( h'(k) + 9 ) % m
i = 4:  Index_4 = ( h'(k) + 16 ) % m

5. Step-by-Step Execution Walkthrough

Let us trace the insertion of a sequence of keys into a hash table of size $m = 10$ (indices $0$ to $9$ ) using Quadratic Probing.

Base Hash Function:

h'(k) = k \pmod{10}

Keys to Insert:

72, 84, 96, 94, 58, 4

Step 1: Insert $72$

$i = 0$ :

h(72, 0) = (72 \pmod{10} + 0^2) \pmod{10} = (2 + 0) \pmod{10} = 2

Status: Slot 2 is empty.
Action: Insert $72$ at index 2.

Step 2: Insert $84$

$i = 0$ :

h(84, 0) = (84 \pmod{10} + 0^2) \pmod{10} = (4 + 0) \pmod{10} = 4

Status: Slot 4 is empty.
Action: Insert $84$ at index 4.

Step 3: Insert $96$

$i = 0$ :

h(96, 0) = (96 \pmod{10} + 0^2) \pmod{10} = (6 + 0) \pmod{10} = 6

Status: Slot 6 is empty.
Action: Insert $96$ at index 6.

Step 4: Insert $94$ (First Collision)

$i = 0$ :

h(94, 0) = (94 \pmod{10} + 0^2) \pmod{10} = 4 \implies \text{Collision! (Slot 4 is occupied by } 84\text{)}

$i = 1$ :

h(94, 1) = (94 \pmod{10} + 1^2) \pmod{10} = (4 + 1) \pmod{10} = 5

Status: Slot 5 is empty.
Action: Insert $94$ at index 5.

Step 5: Insert $58$

$i = 0$ :

h(58, 0) = (58 \pmod{10} + 0^2) \pmod{10} = 8

Status: Slot 8 is empty.
Action: Insert $58$ at index 8.

Step 6: Insert $4$ (Multiple Collisions)

$i = 0$ :

h(4, 0) = (4 \pmod{10} + 0^2) \pmod{10} = 4 \implies \text{Collision! (Slot 4 is occupied by } 84\text{)}

$i = 1$ :

h(4, 1) = (4 \pmod{10} + 1^2) \pmod{10} = 5 \implies \text{Collision! (Slot 5 is occupied by } 94\text{)}

$i = 2$ :

h(4, 2) = (4 \pmod{10} + 2^2) \pmod{10} = (4 + 4) \pmod{10} = 8 \implies \text{Collision! (Slot 8 is occupied by } 58\text{)}

$i = 3$ :

h(4, 3) = (4 \pmod{10} + 3^2) \pmod{10} = (4 + 9) \pmod{10} = 13 \pmod{10} = 3

Status: Slot 3 is empty.
Action: Insert $4$ at index 3.

Final Hash Table State

Index	Key	Insertion Step Details
0	Empty
1	Empty
2	72	Inserted directly ( $i=0$ )
3	4	Resolved at $i=3$ (Probed: 4 $\rightarrow$ 5 $\rightarrow$ 8 $\rightarrow$ 3)
4	84	Inserted directly ( $i=0$ )
5	94	Resolved at $i=1$ (Probed: 4 $\rightarrow$ 5)
6	96	Inserted directly ( $i=0$ )
7	Empty
8	58	Inserted directly ( $i=0$ )
9	Empty

6. Visualizing the Probe Path (Key: 4)

The diagram below illustrates the non-linear, jumping behavior of Quadratic Probing when resolving collisions for key 4:

Structure & Concept Flow

Key 4

|---> Probe 0: Index 4 (Occupied by 84)

| |

| +---[Jump 1^2 = 1 slot]---> Probe 1: Index 5 (Occupied by 94)

| |

| +---[Jump 2^2 = 4 slots from base]---> Probe 2: Index 8 (Occupied by 58)

| |

| +---[Jump 3^2 = 9 slots from base]---> Probe 3: Index 3 (EMPTY - INSERTED)

7. Tabular Synthesis: Linear vs. Quadratic Probing

Feature	Linear Probing	Quadratic Probing
Step Function	$f(i) = i$ (Linear)	$f(i) = i^2$ (Quadratic)
Probe Sequence	$h'(k) + 1, + 2, + 3, \dots$	$h'(k) + 1, + 4, + 9, \dots$
Clustering Type	Suffers severely from Primary Clustering.	Suffers mildly from Secondary Clustering.
Cache Performance	Excellent (due to spatial locality of sequential slots).	Moderate (jumps can cause cache misses).
Table Coverage	Guaranteed to find an empty slot if one exists.	Not guaranteed to find an empty slot unless table size $m$ is prime and load factor $\alpha < 0.5$ .

8. Implementation in Code

Below is a complete, production-grade Python implementation of a Hash Table utilizing Quadratic Probing for collision resolution.

PYTHON

class QuadraticProbingHashTable:
    def __init__(self, size: int):
        self.size = size
        self.table = [None] * self.size
        self.keys_count = 0

    def _hash(self, key: int) -> int:
        return key % self.size

    def insert(self, key: int) -> bool:
        if self.keys_count >= self.size:
            raise OverflowError("Hash Table is full")

        base_index = self._hash(key)
        
        for i in range(self.size):
            # Quadratic probing formula: (base_index + i^2) % size
            probe_index = (base_index + (i * i)) % self.size
            
            # If slot is empty or contains a deleted placeholder
            if self.table[probe_index] is None or self.table[probe_index] == -1:
                self.table[probe_index] = key
                self.keys_count += 1
                print(f"Key {key} inserted at index {probe_index} (Probe {i})")
                return True
            
            print(f"Collision at index {probe_index} for key {key} (Probe {i})")
            
        print(f"Failed to insert key {key} due to probing cycle limits.")
        return False

    def display(self):
        for idx, val in enumerate(self.table):
            print(f"Index {idx}: {val if val is not None else 'Empty'}")

# --- Execution Walkthrough ---
if __name__ == "__main__":
    ht = QuadraticProbingHashTable(10)
    keys = [72, 84, 96, 94, 58, 4]
    
    for k in keys:
        ht.insert(k)
        
    print("\nFinal Hash Table State:")
    ht.display()

9. Real-World Pitfalls & Edge Cases

While Quadratic Probing successfully mitigates Primary Clustering, it introduces its own set of unique engineering challenges:

1. Secondary Clustering

If two keys have the same initial hash value ( $h'(k_1) = h'(k_2)$ ), they will traverse the exact same quadratic probe sequence:

\text{Sequence: } h'(k_1) + 1^2, h'(k_1) + 2^2, h'(k_1) + 3^2 \dots

This is known as Secondary Clustering. While much less severe than Primary Clustering, it can still cause minor performance degradation.

2. The "Infinite Loop" / Unreachable Slots Problem

Unlike Linear Probing, which guarantees that every single slot in the table will be checked, Quadratic Probing can get stuck in a cyclic loop, probing the same subset of indices repeatedly while completely missing empty slots.

Note: To guarantee that the quadratic probe sequence visits at least half of the table slots before repeating, two strict conditions must be met:

The table size $m$ must be a Prime Number.

The Load Factor ( $\alpha = \frac{N}{m}$ ) must be kept strictly below 0.5 (less than 50% full).

Summary and Key Takeaways

Primary Clustering is a major drawback of Linear Probing where consecutive occupied slots form large blocks, degrading search and insertion times to $O(N)$ .
Quadratic Probing resolves primary clustering by replacing the linear step size with a quadratic step size ( $i^2$ ).
The mathematical formula for Quadratic Probing is $h(k, i) = (h'(k) + i^2) \pmod m$ .
As the probe index $i$ increases, the search interval grows quadratically ( $1, 4, 9, 16, \dots$ ), allowing the algorithm to jump over dense clusters.
Secondary Clustering occurs when keys with the same initial hash value follow the same probe path, though its performance impact is significantly lower than primary clustering.
To prevent infinite loops and ensure that empty slots are always found, the hash table size $m$ should be a prime number and the load factor should be kept under 50%.