Quadratic Probing: How It Works and When to Use It

Quadratic probing is a method used in hash tables to resolve collisions by checking positions at intervals that grow quadratically (like 1, 4, 9, 16, etc.). Instead of moving linearly, it jumps in increasing steps to find an empty slot, reducing clustering and improving search efficiency.

How It Works

Imagine you have a row of mailboxes (a hash table) and you want to put letters (data) into specific boxes based on their address (hash value). Sometimes, two letters want the same mailbox, causing a collision. Quadratic probing solves this by checking mailboxes at increasing distances: first 1 step away, then 4 steps, then 9, and so on, following a square number pattern.

This means if the first mailbox is taken, you don't just check the next one, but jump further away each time. This helps spread out the data more evenly and avoids long chains of filled boxes next to each other, which can happen with simple linear probing.

Example

This example shows how quadratic probing inserts values into a hash table and resolves collisions by jumping in square steps.

python

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

    def hash(self, key):
        return key % self.size

    def insert(self, key):
        index = self.hash(key)
        i = 1
        while self.table[index] is not None:
            index = (self.hash(key) + i * i) % self.size
            i += 1
        self.table[index] = key

    def __str__(self):
        return str(self.table)

# Create a hash table of size 7
hash_table = QuadraticProbingHashTable(7)

# Insert keys that cause collisions
keys = [10, 24, 31, 17]
for key in keys:
    hash_table.insert(key)

print(hash_table)

Output

[None, 24, None, 10, 31, None, 17]

When to Use

Use quadratic probing when you want to handle collisions in a hash table efficiently without clustering many items together. It works well when the table size is prime and the load factor (how full the table is) is kept below about 50% to avoid infinite loops.

Real-world uses include implementing fast lookup tables in databases, caches, and memory management systems where quick access and fewer collisions improve performance.

Key Points

• Quadratic probing uses square numbers to find the next slot after a collision.
• It reduces clustering compared to linear probing.
• Works best with prime-sized tables and low load factors.
• May fail to find a slot if the table is too full.

Key Takeaways

Quadratic probing resolves hash collisions by jumping in square-number steps.

It helps reduce clustering and spreads data more evenly in the table.

Best used with prime-sized tables and moderate load factors.

Not suitable for very full tables due to possible infinite loops.

Common in hash table implementations needing efficient collision handling.