Table of contents
1.
Introduction
2.
What is Quadratic Probing?
2.1.
Here's how it works
2.2.
Code Implementation
2.3.
Python
2.4.
C++
2.5.
C#
2.6.
JavaScript
2.7.
Java
3.
How Quadratic Probing is Done
3.1.
Initial Hash Calculation
3.2.
Collision Detection
3.3.
Quadratic Probing
3.4.
Finding a Free Slot
3.5.
Insertion
3.6.
Python
3.7.
C++
3.8.
C#
3.9.
JavaScript
3.10.
Java
3.11.
Time & Space Complexity of Quadratic Probing
3.12.
Time Complexity
3.13.
Space Complexity
4.
Frequently Asked Questions
4.1.
What makes Quadratic Probing better than Linear Probing?
4.2.
How does the size of the hash table affect Quadratic Probing?
4.3.
Can Quadratic Probing lead to infinite loops?
4.4.
Is quadratic probing faster than linear probing?
4.5.
What is probing in DSA?
5.
Conclusion
Last Updated: Jan 2, 2025
Easy

Quadratic Probing in Data Structure

Author Sinki Kumari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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. 

Quadratic Probing in Data Structure

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. 

What is Quadratic Probing?

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.

Code Implementation

  • Python
  • C++
  • C#
  • JavaScript
  • Java

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}")

# Example usage
hash_table = QuadraticProbingHashTable(10)
hash_table.insert(23)
hash_table.insert(33)
hash_table.insert(43)
You can also try this code with Online Python Compiler
Run Code

C++

#include <iostream>
#include <vector>
using namespace std;

class QuadraticProbingHashTable {
private:
vector<int> table;
int capacity;
int size;

int hash(int key) {
return key % capacity;
}

int quadraticProbe(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != -1) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (hashValue == originalHash) {
throw runtime_error("Hash table is full");
}
}
return hashValue;
}

public:
QuadraticProbingHashTable(int cap) : capacity(cap), size(0), table(cap, -1) {}

void insert(int key) {
if (size == capacity) {
throw runtime_error("Hash table is full");
}
int hashValue = quadraticProbe(key);
table[hashValue] = key;
size++;
cout << "Inserted " << key << " at index " << hashValue << endl;
}
};

// Example usage
int main() {
QuadraticProbingHashTable hashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

C#

using System;

public class QuadraticProbingHashTable
{
private int?[] table;
private int capacity;
private int size;

public QuadraticProbingHashTable(int capacity = 10)
{
this.capacity = capacity;
table = new int?[capacity];
size = 0;
}

private int Hash(int key)
{
return key % capacity;
}

private int QuadraticProbe(int key)
{
int originalHash = Hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue].HasValue)
{
hashValue = (originalHash + i * i) % capacity;
i++;
if (hashValue == originalHash)
{
throw new Exception("Hash table is full");
}
}
return hashValue;
}

public void Insert(int key)
{
if (size == capacity)
{
throw new Exception("Hash table is full");
}
int hashValue = QuadraticProbe(key);
table[hashValue] = key;
size++;
Console.WriteLine($"Inserted {key} at index {hashValue}");
}
}

// Example usage
public class Program
{
public static void Main()
{
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.Insert(23);
hashTable.Insert(33);
hashTable.Insert(43);
}
}

JavaScript

class QuadraticProbingHashTable {
constructor(capacity = 10) {
this.capacity = capacity;
this.table = Array(this.capacity).fill(null);
this.size = 0;
}

hash(key) {
return key % this.capacity;
}

quadraticProbe(key) {
const originalHash = this.hash(key);
let hashValue = originalHash;
let i = 1;
while (this.table[hashValue] !== null) {
hashValue = (originalHash + i * i) % this.capacity;
i++;
if (hashValue === originalHash) {
throw new Error("Hash table is full");
}
}
return hashValue;
}

insert(key) {
if (this.size === this.capacity) {
throw new Error("Hash table is full");
}
const hashValue = this.quadraticProbe(key);
this.table[hashValue] = key;
this.size++;
console.log(`Inserted ${key} at index ${hashValue}`);
}
}

// Example usage
const hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
You can also try this code with Online Javascript Compiler
Run Code

Java

public class QuadraticProbingHashTable {
private Integer[] table;
private int capacity;
private int size;

public QuadraticProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Integer[capacity];
this.size = 0;
}

private int hash(int key) {
return key % capacity;
}

private int quadraticProbe(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != null) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (hashValue == originalHash) {
throw new RuntimeException("Hash table is full");
}
}
return hashValue;
}

public void insert(int key) {
if (size == capacity) {
throw new RuntimeException("Hash table is full");
}
int hashValue = quadraticProbe(key);
table[hashValue] = key;
size++;
System.out.println("Inserted " + key + " at index " + hashValue);
}

public static void main(String[] args) {
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);
}
}
You can also try this code with Online Java Compiler
Run Code


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.

Quadratic Probing

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
  • C++
  • C#
  • JavaScript
  • Java

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:
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:
return None
return hash_value if self.table[hash_value] == key else 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 usage
hash_table = QuadraticProbingHashTable(10)
hash_table.insert(23)
hash_table.insert(33)
hash_table.insert(43)

hash_table.search(33)
hash_table.search(44)
You can also try this code with Online Python Compiler
Run Code

C++

#include <iostream>
#include <vector>
using namespace std;

class QuadraticProbingHashTable {
private:
vector<int> table;
int capacity;
int size;

int hash(int key) {
return key % capacity;
}

int quadraticProbeForInsert(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != -1) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw runtime_error("Hash table is full");
}
return hashValue;
}

int quadraticProbeForSearch(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != -1 && table[hashValue] != key) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return -1;
}
return table[hashValue] == key ? hashValue : -1;
}

public:
QuadraticProbingHashTable(int cap) : capacity(cap), size(0), table(cap, -1) {}

void insert(int key) {
if (size == capacity) throw runtime_error("Hash table is full");
int hashValue = quadraticProbeForInsert(key);
table[hashValue] = key;
size++;
cout << "Inserted " << key << " at index " << hashValue << endl;
}

void search(int key) {
int hashValue = quadraticProbeForSearch(key);
if (hashValue != -1) {
cout << key << " found at index " << hashValue << endl;
} else {
cout << key << " not found in the hash table" << endl;
}
}
};

// Example usage
int main() {
QuadraticProbingHashTable hashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);

hashTable.search(33);
hashTable.search(44);
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

C#

using System;

public class QuadraticProbingHashTable
{
private int?[] table;
private int capacity;
private int size;

public QuadraticProbingHashTable(int capacity = 10)
{
this.capacity = capacity;
table = new int?[capacity];
size = 0;
}

private int Hash(int key)
{
return key % capacity;
}

private int QuadraticProbeForInsert(int key)
{
int originalHash = Hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue].HasValue)
{
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw new Exception("Hash table is full");
}
return hashValue;
}

private int? QuadraticProbeForSearch(int key)
{
int originalHash = Hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue].HasValue && table[hashValue] != key)
{
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return null;
}
return table[hashValue] == key ? hashValue : (int?)null;
}

public void Insert(int key)
{
if (size == capacity) throw new Exception("Hash table is full");
int hashValue = QuadraticProbeForInsert(key);
table[hashValue] = key;
size++;
Console.WriteLine($"Inserted {key} at index {hashValue}");
}

public void Search(int key)
{
int? hashValue = QuadraticProbeForSearch(key);
if (hashValue.HasValue)
{
Console.WriteLine($"{key} found at index {hashValue}");
}
else
{
Console.WriteLine($"{key} not found in the hash table");
}
}
}

// Example usage
public class Program
{
public static void Main()
{
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.Insert(23);
hashTable.Insert(33);
hashTable.Insert(43);

hashTable.Search(33);
hashTable.Search(44);
}
}

JavaScript

class QuadraticProbingHashTable {
constructor(capacity = 10) {
this.capacity = capacity;
this.table = Array(this.capacity).fill(null);
this.size = 0;
}

hash(key) {
return key % this.capacity;
}

quadraticProbeForInsert(key) {
const originalHash = this.hash(key);
let hashValue = originalHash;
let i = 1;
while (this.table[hashValue] !== null) {
hashValue = (originalHash + i ** 2) % this.capacity;
i++;
if (i > this.capacity) throw new Error("Hash table is full");
}
return hashValue;
}

quadraticProbeForSearch(key) {
const originalHash = this.hash(key);
let hashValue = originalHash;
let i = 1;
while (this.table[hashValue] !== null && this.table[hashValue] !== key) {
hashValue = (originalHash + i ** 2) % this.capacity;
i++;
if (i > this.capacity) return null;
}
return this.table[hashValue] === key ? hashValue : null;
}

insert(key) {
if (this.size === this.capacity) throw new Error("Hash table is full");
const hashValue = this.quadraticProbeForInsert(key);
this.table[hashValue] = key;
this.size++;
console.log(`Inserted ${key} at index ${hashValue}`);
}

search(key) {
const hashValue = this.quadraticProbeForSearch(key);
if (hashValue !== null) {
console.log(`${key} found at index ${hashValue}`);
} else {
console.log(`${key} not found in the hash table`);
}
}
}

// Example usage
const hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);

hashTable.search(33);
hashTable.search(44);
You can also try this code with Online Javascript Compiler
Run Code

Java

public class QuadraticProbingHashTable {
private Integer[] table;
private int capacity;
private int size;

public QuadraticProbingHashTable(int capacity) {
this.capacity = capacity;
this.table = new Integer[capacity];
this.size = 0;
}

private int hash(int key) {
return key % capacity;
}

private int quadraticProbeForInsert(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != null) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) throw new RuntimeException("Hash table is full");
}
return hashValue;
}

private Integer quadraticProbeForSearch(int key) {
int originalHash = hash(key);
int hashValue = originalHash;
int i = 1;
while (table[hashValue] != null && !table[hashValue].equals(key)) {
hashValue = (originalHash + i * i) % capacity;
i++;
if (i > capacity) return null;
}
return table[hashValue] != null && table[hashValue].equals(key) ? hashValue : null;
}

public void insert(int key) {
if (size == capacity) throw new RuntimeException("Hash table is full");
int hashValue = quadraticProbeForInsert(key);
table[hashValue] = key;
size++;
System.out.println("Inserted " + key + " at index " + hashValue);
}

public void search(int key) {
Integer hashValue = quadraticProbeForSearch(key);
if (hashValue != null) {
System.out.println(key + " found at index " + hashValue);
} else {
System.out.println(key + " not found in the hash table");
}
}

public static void main(String[] args) {
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(23);
hashTable.insert(33);
hashTable.insert(43);

hashTable.search(33);
hashTable.search(44);
}
}
You can also try this code with Online Java Compiler
Run Code

 

Output

Inserted 23 at index 3
Inserted 33 at index 4
Inserted 43 at index 7
33 found at index 4
44 not found in the hash table


Explanation
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.

Frequently Asked Questions

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.

Can Quadratic Probing lead to infinite loops?

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.

Is quadratic probing faster than linear probing?

Quadratic probing can be faster than linear probing in certain cases because it reduces clustering by spreading out the probe sequence. However, its performance depends on factors like load factor and hash table size. Linear probing can suffer more from primary clustering.

What is probing in DSA?

Probing in Data Structures and Algorithms (DSA) refers to the technique used to resolve collisions in hash tables. When two keys hash to the same index, probing helps find the next available slot using methods like linear, quadratic, or double hashing.

Conclusion

In this article, we learned about Quadratic Probing in hash tables. We explored what Quadratic Probing is and how it works. Later, we discussed how Quadratic Probing is done, with a brief explanation of the required steps. We also looked at its implementation in multiple languages and concluded by understanding the time and space complexities of Quadratic Probing.

Live masterclass