1.
Introduction
2.
2.1.
Here's how it works
2.2.
Code Implementation
2.3.
Python
3.
3.1.
Initial Hash Calculation
3.2.
Collision Detection
3.3.
3.4.
Finding a Free Slot
3.5.
Insertion
3.6.
Python
4.
Time & Space Complexity of Quadratic Probing
4.1.
Time Complexity
4.2.
Space Complexity
5.
5.1.
What makes Quadratic Probing better than Linear Probing?
5.2.
How does the size of the hash table affect Quadratic Probing?
5.3.
6.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Quadratic Probing in Data Structure

Sinki Kumari
0 upvote

## Introduction

When we talk about making our data management efficient & snappy, Quadratic Probing is a technique that often comes to the rescue, especially in the context of hash tables. It's a method used to resolve collisions â€“ those awkward situations where different data elements want to occupy the same slot.

This article will look into Quadratic Probing, from its basics to its complexities. We'll explore how it's executed, its time & space complexities, & provide examples to solidify your understanding.

Quadratic Probing is a strategy to deal with collisions within hash tables. Imagine you've got a shelf for your books, & each book is supposed to go into a specific slot. But sometimes, two books might be assigned the same slot. Now, where do you put the second book? In hash tables, this is a collision, & Quadratic Probing helps us find a new spot for that second book.

### Here's how it works

When a collision happens, Quadratic Probing uses a quadratic function (hence the name) to find another slot. For the math-savvy, it's like saying, "Okay, the first spot is taken, let's try a spot that's 1^2 away. Oh, that's taken too? How about 2^2 spots away?" And so on, until it finds an empty slot.

This method ensures that we're not just randomly jumping around looking for a free spot, but following a systematic approach. It reduces the chances of forming clusters of filled slots, which can slow things down. So, Quadratic Probing keeps our data retrieval quick & efficient, just like flipping to the right page in your notebook without having to sift through every single page.

Let's look at a simple example to illustrate this. Suppose we're trying to insert values into a hash table, and our hash function is pretty straightforward: it assigns each value to a slot equal to the value mod 10. If we try to insert 23 & 33, both would initially aim for slot 3 (because 23 mod 10 and 33 mod 10 both equal 3). With Quadratic Probing, if slot 3 is occupied by 23 when we try to insert 33, we'll then check slot 4 (3 + 1^2), then slot 6 (3 + 2^2), and so on, until we find an open slot.

• Python

### Python

``class QuadraticProbingHashTable:    def __init__(self, capacity=10):        self.capacity = capacity        self.table = [None] * self.capacity        self.size = 0    def hash(self, key):        return key % self.capacity    def quadratic_probe(self, key):        original_hash = self.hash(key)        hash_value = original_hash        i = 1        while self.table[hash_value] is not None:            hash_value = (original_hash + i ** 2) % self.capacity            i += 1            if hash_value == original_hash:  # Table is full                raise Exception("Hash table is full")        return hash_value    def insert(self, key):        if self.size == self.capacity:            raise Exception("Hash table is full")        hash_value = self.quadratic_probe(key)        self.table[hash_value] = key        self.size += 1        print(f"Inserted {key} at index {hash_value}")# Create a hash table and insert some values using Quadratic Probinghash_table = QuadraticProbingHashTable(10)hash_table.insert(23)hash_table.insert(33)hash_table.insert(43)``

Output

``````Inserted 23 at index 3
Inserted 33 at index 4
Inserted 43 at index 7``````

In this example:

• We have a class QuadraticProbingHashTable with a simple hash function based on modulo (hash method).

• The quadratic_probe method implements Quadratic Probing to find an empty slot for a given key if its initial hash index is already occupied.

• The insert method inserts a new key into the hash table using Quadratic Probing to resolve any collisions.

When running this code, if you try to insert keys 23, 33, and 43, you'll see how Quadratic Probing finds different slots for each key, even if their initial hash index collides. This way, the data structure efficiently handles collisions, maintaining fast access times.

## How Quadratic Probing is Done

Understanding how Quadratic Probing is done is key to grasping its efficiency in collision resolution in hash tables. It's like finding a parking spot in a crowded lot; if your usual spot is taken, you try the next one a little further away, then maybe one further still, but in a predictable pattern. Here's the step-by-step breakdown.

### Initial Hash Calculation

First, we calculate the initial hash of the item (let's call this hash_value). This is often done using a simple modulo operation with the hash table size. Think of this as your first choice for a parking spot.

### Collision Detection

We check the slot at hash_value. If it's empty, great! We insert the item there. If not, it means there's a collision, just like if your parking spot was already taken.

This is where Quadratic Probing comes into play. We don't just move to the next slot. Instead, we add a quadratic function of the number of tries to the original hash_value. So, for the 1st collision, we check hash_value + 1^2, for the 2nd, hash_value + 2^2, and so on.

### Finding a Free Slot

We repeat step 3 until we find an empty slot or realize the table is full (like circling the parking lot until you find a spot or realize it's completely full).

### Insertion

Once a free slot is found, the item is inserted into that slot.

This method ensures that we spread out the items evenly across the hash table, reducing the likelihood of clustering and thus maintaining efficient access times.

It's important to note that the size of the hash table should be chosen carefully to ensure that it can accommodate the quadratic probing sequence without too many overlaps, much like a parking lot needs to be big enough to handle the cars coming in at peak times.

For a more practical understanding, let's go through a coding example that demonstrates the execution of Quadratic Probing when handling collisions in a hash table. We'll extend our previous Python example to include a method for searching elements, which will also utilize Quadratic Probing.

• Python

### Python

``class QuadraticProbingHashTable:    def __init__(self, capacity=10):        self.capacity = capacity        self.table = [None] * self.capacity        self.size = 0    def hash(self, key):        return key % self.capacity    def quadratic_probe_for_insert(self, key):        original_hash = self.hash(key)        hash_value = original_hash        i = 1        while self.table[hash_value] is not None:            hash_value = (original_hash + i ** 2) % self.capacity            i += 1            if i > self.capacity:  # Avoid infinite loop                raise Exception("Hash table is full")        return hash_value    def quadratic_probe_for_search(self, key):        original_hash = self.hash(key)        hash_value = original_hash        i = 1        while self.table[hash_value] is not None and self.table[hash_value] != key:            hash_value = (original_hash + i ** 2) % self.capacity            i += 1            if i > self.capacity:  # Key not found                return None        if self.table[hash_value] == key:            return hash_value        else:            return None    def insert(self, key):        if self.size == self.capacity:            raise Exception("Hash table is full")        hash_value = self.quadratic_probe_for_insert(key)        self.table[hash_value] = key        self.size += 1        print(f"Inserted {key} at index {hash_value}")    def search(self, key):        hash_value = self.quadratic_probe_for_search(key)        if hash_value is not None:            print(f"{key} found at index {hash_value}")        else:            print(f"{key} not found in the hash table")# Example usagehash_table = QuadraticProbingHashTable(10)hash_table.insert(23)hash_table.insert(33)hash_table.insert(43)hash_table.search(33)  # Should find 33hash_table.search(44)  # Should not find 44``

Output

``````Inserted 23 at index 3
Inserted 33 at index 4
Inserted 43 at index 7
33 found at index 4

In this example:

• The quadratic_probe_for_insert method is used for finding a free slot for insertion using Quadratic Probing.

• The quadratic_probe_for_search method utilizes Quadratic Probing to search for an existing key in the hash table.

• The insert method inserts a key using Quadratic Probing to resolve collisions.

• The search method searches for a key in the hash table, again using Quadratic Probing to navigate through potential collisions.

This code provides a basic framework to understand how Quadratic Probing can be implemented for both inserting and searching keys in a hash table, demonstrating its utility in managing collisions effectively.

## Time & Space Complexity of Quadratic Probing

When it comes to understanding any data structure or algorithm, knowing about its time & space complexity is crucial. It's like assessing how much time & room a task will take up. For Quadratic Probing in hash tables, these complexities tell us how efficient the method is under different scenarios.

### Time Complexity

The time complexity of operations in a hash table using Quadratic Probing, such as insertion, deletion, & search, can vary. Ideally, when the hash table is sparse & collisions are few, these operations can be incredibly swift, nearly O(1), meaning they take a constant amount of time regardless of the number of items in the table.

However, as the table gets filled & collisions increase, the efficiency can drop. In the worst case, where every potential slot needs to be checked, the time complexity can approach O(n), where n is the number of slots in the table. But remember, due to the systematic nature of Quadratic Probing, this worst-case scenario is less likely compared to other methods like linear probing.

### Space Complexity

The space complexity for a hash table using Quadratic Probing is O(n), where n is the size of the table. This is because, regardless of the number of items actually stored, the table allocates space for 'n' possible entries from the get-go. It's like having a bookshelf with a fixed number of slots; the space taken up by the shelf remains the same, no matter how many books you actually put on it.

It's important to note that while Quadratic Probing improves on the clustering issue seen in simpler probing methods, it requires careful table size selection & load factor management to maintain efficiency. The load factor, which is the ratio of the number of stored entries to the table size, significantly influences performance. Keeping the load factor below a certain threshold (often around 0.5 to 0.7) helps in keeping operations efficient.

### What makes Quadratic Probing better than Linear Probing?

Quadratic Probing reduces clustering, a common issue in Linear Probing where a group of consecutive slots gets filled, slowing down the performance. By jumping over slots in a quadratic sequence, it spreads out the entries more evenly, leading to better performance in many cases.

### How does the size of the hash table affect Quadratic Probing?

The size of the hash table is crucial for Quadratic Probing. Ideally, the table size should be a prime number to maximize the efficiency of the probing sequence. A prime number size helps ensure that all slots can be probed, reducing the chance of an unresolvable collision.

If not implemented correctly, especially in a full or nearly full table, Quadratic Probing can lead to infinite loops. To prevent this, it's important to ensure the table size is appropriate and to include a mechanism to stop the probe after a certain number of attempts, signaling the table is full or needs resizing.

## Conclusion

In this article, we learned the concept of Quadratic Probing in hash tables, starting from its basic definition, moving through how it's executed, to understanding its time and space complexities. Quadratic Probing stands out as a method for resolving collisions by employing a quadratic function to find the next slot, offering a balanced trade-off between performance and complexity.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.